ABC - 076- A&B&C

AtCoder ABC 076 A&B&C

AtCoder - 076

A問題

	private void solveA() {
		int numR = nextInt();
		int numG = nextInt();

		out.println(numG * 2 - numR);
	}

B問題

• 常に最小の操作をすればよい
  • どちらの操作が最小値になるのかを比較

	private void solveB() {
		final int numN = nextInt();
		final int numK = nextInt();

		int res = IntStream.range(0, numN).reduce(1, (sum, i) -> {
			if (sum * 2 > sum + numK) {
				sum += numK;
			} else {
				sum *= 2;
			}
			return sum;
		});

		out.println(res);
	}

C問題

• 可能性のある文字を全部調べて文字コード順に並べ替える
• ロジックの説明はコメントで記載

	private void solveC() {
		char[] strS = next().toCharArray();
		char[] strT = next().toCharArray();

		if (strS.length < strT.length) {
			out.println("UNRESTORABLE");
			return;
		}

		List<String> memo = new ArrayList<String>();

		//文字列Sの1文字目から開始
		int resT = chkC(strS, strT, 0, memo);

		//memoの文字列をソートする
		Collections.sort(memo);
		//文字列が1つ以上あった場合はソート順で一番先頭の文字を表示
		out.println(resT > 0 ? memo.get(0) : "UNRESTORABLE");
	}

	private int chkC(char[] strS, char[] strT, int indexS, List<String> memo) {
		//文字列Sの開始位置+文字列Tの長さが文字列Sの長さを超えた場合は終了
		if (indexS + strT.length > strS.length) {
			return 0;
		}

		int res = 0;

		int cntT = 0;
		boolean isMatch = false;

		/*
		 * 置き換えた場合の文字列を作成する
		 * ただし、ここで作成した文字列は正しいかどうかはわからない
		 */
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < strS.length; i++) {

			if (i < indexS || i >= indexS + strT.length) {
				//文字列Sの内、文字列Tに置換しないところはそのまま文字列Sをappend
				builder.append(strS[i]);
			} else {
				if (strT[cntT] == strS[i] || strS[i] == '?') {
					//文字列Sと文字列Tが同じ文字または、文字列Sが'?'なら文字列Tの置き換える
					builder.append(strT[cntT]);
					//文字列Tの文字をappendしたカウント
					cntT++;
				} else {
					/*
					 * 文字列Sと文字列Tが違う場合は文字列Sをappend
					 * 基本的にこのルートにきた場合、その文字列は文字列Tを含んでいない
					 */
					builder.append(strS[i]);
				}
			}
		}

		/*
		 * 文字列Tの文字をappendしたカウントと文字列Tの長さが同じなら、
		 * 文字列Tで置き換えることに成功している。
		 */
		isMatch = (cntT == strT.length);
		if (isMatch) {
			//作成した文字列が正しい場合のみmemoにadd
			memo.add(builder.toString().replace("?", "a"));
			/*
			 * ただしい文字列を作成できたので作成カウント+1、
			 * その後indexSを+1して再度マッチングしてほかの文字を探す
			 */
			res += chkC(strS, strT, indexS + 1, memo) + 1;
		} else {
			//ただしい文字列を作成できなかったので、indexSを+1して再度マッチング
			res += chkC(strS, strT, indexS + 1, memo);
		}

		return res;
	}