ABC - 011- A&B&C

AtCoder ABC 011 A&B&C

AtCoder - 011

A - 来月は何月？

• 12月だったら次は1月
• 1月-11月だったら次は+1月

	private void solveA() {
		int n = nextInt();

		out.println(n == 12 ? 1 : n + 1);
	}

B - 名前の確認

	private void solveB() {
		char[] n = next().toCharArray();
		for (int i = 0; i < n.length; i++) {
			if (i == 0) {
				n[i] = Character.toUpperCase(n[i]);
			} else {
				n[i] = Character.toLowerCase(n[i]);
			}

		}

		out.println(new String(n));
	}

C - 123引き算

再帰

	private void solveC2() {
		int n = nextInt();
		int ng1 = nextInt();
		int ng2 = nextInt();
		int ng3 = nextInt();

		Map<String, Boolean> memo = new HashMap<String, Boolean>();
		boolean res = recursiveC2(ng1, ng2, ng3, 0, n, memo);
		out.println(res ? "YES" : "NO");
	}

	private boolean recursiveC2(int ng1, int ng2, int ng3, int currentI, int currentNum, Map<String, Boolean> memo) {
		if (currentNum == ng1 || currentNum == ng2 || currentNum == ng3) {
			return false;
		}
		if (currentNum == 0) {
			return true;
		}
		if (currentI == 100) {
			return false;
		}
		if (memo.containsKey(currentI + ":" + currentNum)) {
			return memo.get(currentI + ":" + currentNum);
		}
		boolean res = false;
		res = res || recursiveC2(ng1, ng2, ng3, currentI + 1, currentNum - 1, memo);
		res = res || recursiveC2(ng1, ng2, ng3, currentI + 1, currentNum - 2, memo);
		res = res || recursiveC2(ng1, ng2, ng3, currentI + 1, currentNum - 3, memo);
		memo.put(currentI + ":" + currentNum, res);
		return res;
	}

DP

• 再帰でACできたので練習代わりにDPでも解いてみた
• $n-0$ までの数字 (step[n + 1]) を何手で作ることができるか？
  • パターンは$n-1 , n-2 , n-3$の3つ
  • 途中でNG数字になってしまう場合はそのパターンを採用することはできない
    • coninueで飛ばしている
  • 最終的に100手以下で作成できているなら成功

	private void solveC() {
		int n = nextInt();
		int ng1 = nextInt();
		int ng2 = nextInt();
		int ng3 = nextInt();
		if (n == ng1 || n == ng2 || n == ng3) {
			out.println("NO");
			return;
		}
		long[] step = new long[n + 1];
		Arrays.fill(step, Long.MAX_VALUE / 10);
		step[n] = 0;
		for (int i = n; i >= 0; i--) {
			if (i == ng1 || i == ng2 || i == ng3) {
				continue;
			}
			if (i + 1 <= n) {
				step[i] = Long.min(step[i + 1] + 1, step[i]);
			}
			if (i + 2 <= n) {
				step[i] = Long.min(step[i + 2] + 1, step[i]);
			}
			if (i + 3 <= n) {
				step[i] = Long.min(step[i + 3] + 1, step[i]);
			}
		}

		out.println(step[0] <= 100 ? "YES" : "NO");
	}