ABC - 118 - A&B&C&D

AtCoder ABC 118 A&B&C&D

AtCoder - 118

A問題

	private void solveA() {

		try (Scanner scanner = new Scanner(System.in)) {
			int lineAB = 0;
			int lineBC = 0;
			lineAB = scanner.nextInt();
			lineBC = scanner.nextInt();

			if (lineBC % lineAB == 0) {
				System.out.println(lineAB + lineBC);
			} else {
				System.out.println(lineBC - lineAB);
			}

			System.out.println("");

		}
	}

B問題

• 読み込んで、料理の番号ごとに数をカウントして、カウントした結果がNと同数の場合は全員がその番号の料理を好き

	private void solveB2() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numN = 0;
			int numM = 0;
			numN = scanner.nextInt();
			numM = scanner.nextInt();

			Map<Integer, Integer> wkMap = new HashMap<Integer, Integer>();

			for (int i = 0; i < numN; i++) {

				int numK = scanner.nextInt();
				for (int j = 0; j < numK; j++) {
					int foodNum = scanner.nextInt();
					wkMap.merge(foodNum, 1, (oldV, newV) -> oldV + newV);
				}
			}

			int count = 0;
			for (Integer wkInt : wkMap.values()) {
				if (wkInt == numN) {
					count++;
				}
			}
			System.out.println(count);

		}
	}

C問題

• 最大公約数を求めればよい

	private void solveC() {

		try (Scanner scanner = new Scanner(System.in)) {
			int monsterNum = 0;
			monsterNum = scanner.nextInt();
			long[] monsters = new long[monsterNum];
			for (int i = 0; i < monsterNum; i++) {
				monsters[i] = scanner.nextInt();
			}
			System.out.println(maximuKouyakuNArgs(monsters[0], monsters, 0));

		}
	}

	public long maximuKouyakuNArgs(long currentKouyaku, long[] nums, int start) {
		long res = currentKouyaku;
		if (start < nums.length) {
			res = maximumKouyaku2Args(nums[start], currentKouyaku);
			return maximuKouyakuNArgs(res, nums, start + 1);
		} else {
			return res;
		}
	}

	public long maximumKouyaku2Args(long num1, long num2) {
		try {
			long wkVal1;
			long wkVal2;
			if (num1 < num2) {
				wkVal1 = num2;
				wkVal2 = num1;
			} else {
				wkVal1 = num1;
				wkVal2 = num2;
			}
			long res = wkVal1 % wkVal2;
			if (res != 0) {
				return maximumKouyaku2Args(wkVal2, res);
			} else {
				return wkVal2;
			}

		} catch (Exception e) {
			System.out.println("num1 : " + num1 + " / num2:" + num2);
			e.printStackTrace();
			return -1;
		}

	}

D問題

• 動的計画法
  • マッチをi本消費したときに、最大の数値は何か？
  • 最大の数値なので
    • 桁が多いほうがいい
      • そのためには、消費マッチ数が少ないものを優先的に選べるとよい
      • 消費マッチ数が同じなら数値が大きいものが良い
  • とはいっても、上記条件を考慮しながら実装するのが難しかった（思いつかなかった）ので以下の方針を採用する
    • 文字列を作成してしまい、その文字列の大小を比べる
      • max(String,String)を実装して文字列を比較してしまう

	private void solveD() {

		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			int[] aA = IntStream.range(0, m).map(i -> scanner.nextInt()).toArray();
			final Map<Integer, Integer> CONST_NUM = new HashMap<Integer, Integer>() {
				{
					put(1, 2);
					put(2, 5);
					put(3, 5);
					put(4, 4);
					put(5, 5);
					put(6, 6);
					put(7, 3);
					put(8, 7);
					put(9, 6);
				}
			};
			String[] dp = new String[10009];
			/*
			 * dp[i]の時に、作られている最大の数値
			 * 配るDPで実装
			 */
			//dp[0]の時は、空
			dp[0] = "";
			for (int i = 0; i < 10000; i++) {
				/*
				 * dp[0]のみ初期化しておいて、その後、aA[]に値がないやつは飛ばす
				 * nullという文字列が入ると文字列の最大値判定上困る
				 * null値だったらいいんだけどね。
				 */
				if (dp[i] == null) {
					continue;
				}
				for (int j = 0; j < aA.length; j++) {
					int syouhiMatch = CONST_NUM.get(aA[j]);
					int inputDigit = aA[j];
					/*
					 * dp[aA[j]の桁を選択した場合のマッチ消費数]
					 * = max(既に格納されている数値 , dp[現在のマッチ消費数]+aA[j]を選択した場合の数値)
					 */
					dp[i + syouhiMatch] = max(dp[i + syouhiMatch], dp[i] + inputDigit);
				}
			}
			System.out.println(dp[n]);
		}
	}

	private String max(String a, String b) {
		if (a == null) {
			return b;
		} else if (b == null) {
			return a;
		} else if (a.length() < b.length()) {
			return b;
		} else if (a.length() > b.length()) {
			return b;
		} else if (a.length() == b.length()) {
			if (a.compareTo(b) < 0) {
				return b;
			} else {
				return a;
			}
		}
		return a;
	}