ABC - 114- A&B&C

AtCoder ABC 114 A&B&C

AtCoder - 114

A問題

• 7,5,3だったらYES

	private void solveA() {
		int numN = Integer.parseInt(next());

		switch (numN) {
		case 7:
		case 5:
		case 3:
			out.print("YES");
			break;
		default:
			out.print("NO");
			break;
		}

	}

B問題

• 文字列を前から3文字ずつ切りだして比較
• 頭から全探索

	private void solveB() {
		String strN = next();

		int res = 99999999;
		for (int i = 0; i < strN.length() - 2; i++) {
			String wk = strN.substring(i, i + 3);
			int wkNum = Integer.parseInt(wk);
			res = Math.min(res, Math.abs(wkNum - 753));
		}

		out.println(res);
	}

C問題：幅優先探索

ループだけでなくこういう解法もすぐ思いつくようになりたい

• 3,5,7を足していく
  • 現在の値を*10して3,5,7を足す

1. $35 ; * ; 10 ; = ; 350 $
2. $350 ; + ; 7 ; = ; 357 $

• 生成する数値が753の制約を満たしているかをチェックして満たしていればカウントする

	long resC2 = 0;

	private void solveC2() {
		long numN = Integer.parseInt(next());
		dfsSolveC2(numN, 0);

		out.println(resC2);
	}

	private void dfsSolveC2(long numN, long current) {
		if (current <= numN) {
			char[] wk = Long.toString(current).toCharArray();

			int num7 = 0;
			int num5 = 0;
			int num3 = 0;
			for (int i = 0; i < wk.length; i++) {
				if (wk[i] == '7') {
					num7++;
				} else if (wk[i] == '5') {
					num5++;
				} else if (wk[i] == '3') {
					num3++;
				}
			}
			if (num7 > 0 && num5 > 0 && num3 > 0) {
//				System.out.println(current);
				resC2++;
			}
			/**
			 * 所詮、配列の中に3種の文字が何回現れるのか？という話でしかない。
			 */
			dfsSolveC2(numN, 10 * current + 3);
			dfsSolveC2(numN, 10 * current + 5);
			dfsSolveC2(numN, 10 * current + 7);
		}
	}

C問題：TLE-Version ループで実装したらTLE

• 1以上N以下の数字を全部調べる
  • 1以上ではあるが、最低は357以上
    • 356以下は条件を満たさない
  • 偶数は対象外

	private void solveC() {
		int numN = Integer.parseInt(next());

		int res = 0;
		for (int i = 357; i <= numN; i++) {
			if (i % 2 == 0) {
				continue;
			} else {
				String wk = Integer.toString(i);
				int num7 = 0;
				int num5 = 0;
				int num3 = 0;
				if (wk.contains("9") || wk.contains("8") || wk.contains("6") || wk.contains("4") || wk.contains("2")
						|| wk.contains("1")) {
					continue;
				} else {
					if (wk.contains("7")) {
						num7++;
					}
					if (wk.contains("5")) {
						num5++;
					}
					if (wk.contains("3")) {
						num3++;
					}
				}
				if (num3 > 0 && num5 > 0 && num7 > 0) {
					res++;
				}
			}
		}

		out.println(res);
	}