ABC - 099- A&B&C

AtCoder ABC 099 A&B&C

AtCoder - 099)]

A問題

• 999回目が境目

	private void solveA() {
		Scanner scanner = null;
		int numN = 0;

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

			if (numN > 999) {
				System.out.println("ABD");
			} else {
				System.out.println("ABC");
			}

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

B問題

• $(1+2+3+4+ ・・・+N)=N*(N+1) / 2$
• 積雪量： $(B-A)=X$ として、$(1+2+3+4+ ・・・+X-1)$ となる

	private void solveB() {
		Scanner scanner = null;
		int numA = 0;
		int numB = 0;

		try {
			scanner = new Scanner(System.in);
			numA = scanner.nextInt();
			numB = scanner.nextInt();

			int wk = numB - numA;

			int res = 0;
			for (int i = 1; i < wk; i++) {
				res += i;
			}

			System.out.println(res - numA);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

C問題：DPの勉強に良い

• コードにコメントで記述している

引き出す金額		1	2	3	4	5	6	7	8	9	10	11	12	-	N
操作回数		1	2	3	4	5	1	2	3	1	2	3	2	-	X

	/**
	 * dp[0] = 0
	 * N = cash/yen
	 * dp[N] = 1 + dp[N-1]
	 *       = 1 + dp[N-6]
	 *       = 1 + dp[N-6^2]
	 *       = 1 + dp[N-6^3]
	 *
	 *       = 1 + dp[N-9^1]
	 */
	private void solveC() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			/*
			 * 1
			 * 6 , 6^2 , 6^3 , 6^4
			 * 9 , 9^2 , 9^3 , 9^4
			 * dp[N]
			 * dp[i] ----- dp[N-1]
			 * 1円を使うパターン
			 * dp[N]= 1 + dp[N-1]
			 *     　  = 1 + dp[N-6]
			 *       　= 1 + dp[N-6^2]
			 *       　= 1 + dp[N-6^3]
			 *
			 *　       = 1 + dp[N-9^1]
			 * 上記最小値
			 *
			 */

			/*
			 * N<=100000　なので、dp[N]は100000以上で取っておく
			 */
			int[] dp = new int[100010];

			/*
			 * dp[N]を求めていく。
			 * minを求めるので大きな値で初期化
			 */
			Arrays.fill(dp, 999999999);

			/*
			 * dpN円引き出すのに必要な操作回数
			 * 0-5は1円での操作
			 * 埋めておく
			 */
			dp[0] = 0;
			dp[1] = 1;
			dp[2] = 2;
			dp[3] = 3;
			dp[4] = 4;
			dp[5] = 5;
			/*
			 * 6円からN円までの操作回数最小
			 */
			for (int dpN = 6; dpN <= numN; dpN++) {

				/*
				 * 6べきのDP
				 */
				int power = 6;
				while (power <= dpN) {
					/*
					 * dpN円とdpN-power(6^?乗)円の比較
					 * dpN：初期値はINFで埋まっている
					 * dp[dpN - power] + 1とは、(dpN-power)円のときの"操作回数"に+1をしたのが今回の操作回数の予定という意味
					 */
					dp[dpN] = Math.min(dp[dpN], dp[dpN - power] + 1);
					power *= 6;
				}

				/*
				 * 9べきのDP
				 */
				power = 9;
				while (power <= dpN) {
					/*
					 * dpN円とdpN-power(9^?乗)円の比較
					 * dpN：初期値はINFまたは6^?での操作回数で埋まっている
					 * dp[dpN - power] + 1とは、(dpN-power)円のときの"操作回数"に+1をしたのが今回の操作回数の予定という意味
					 * 例：dpN=6の場合、現在の6円の操作回数と、(6-6^1)円の操作回数+1との比較
					 * なぜなら、6円とは0円+6^1円で表せるため、0円の時の操作回数に+1をすると6円の時の操作回数になる
					 *
					 */
					dp[dpN] = Math.min(dp[dpN], dp[dpN - power] + 1);
					power *= 9;
				}
			}

			System.out.println(dp[numN]);

		}

	}