概要

高橋君の解答と正解が与えられるので、書き換える回数を最小限にして不正解の問題数を \(K\) 以下にする必要があります。

考察

まず、初期状態での高橋君の解答 \(S\) と正解 \(T\) を比較することで、どの問題が不正解であるかを確認できます。
例えば、\(S = "010"\)、\(T = "110"\) の場合、1問目だけが不正解です。

このとき、もし不正解の問題数がすでに \(K\) 以下であれば、何も書き換える必要はありません。
そうでない場合、不正解の問題をいくつか「正解に書き換える」ことで不正解の数を減らす必要があります。

重要な観察として、「不正解の問題を1つ正解に書き換える」＝「書き換え回数が1増える」となります。
逆に、「正解の問題を不正解に書き換える」ことは無意味で、書き換え回数は増えるだけで不正解数も増えてしまいます。

したがって、初期の不正解数を \(W\) としたとき、
不正解数を \(K\) 以下にするためには、少なくとも \(W - K\) 問の不正解を正解に書き換える必要があることがわかります。
この操作がまさに最小の書き換え回数となります。

たとえば： - \(N = 5\), \(K = 1\) - \(S = "00000"\) - \(T = "11111"\) - 初期の不正解数は 5、目標は 1 以下なので、\(5 - 1 = 4\) 回書き換えればよい。

アルゴリズム

1. 文字列 \(S\) と \(T\) を比較し、各問題が不正解かどうかを判定する。
2. 不正解の問題数 \(W\) を数える。
3. もし \(W \leq K\) ならば、書き換え不要なので答えは \(0\)。
4. そうでなければ、\(W - K\) が最小の書き換え回数となる。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 各問題の正誤判定は、単純に文字列の各位置を比較すれば良い。

• True/False のリストを作ると扱いやすい。

• 最終的な答えは負にならないように、\(W - K\) と \(\max(0, W - K)\) のどちらを使うか注意するが、問題文より常に可能なので考慮不要。

  ソースコード

N, K = map(int, input().split())
S = input().strip()
T = input().strip()

# 各問題の比較結果をリストにする
# different[i] = (S[i] != T[i]) つまり初期状態で不正解かどうか
different = [S[i] != T[i] for i in range(N)]

# 初期の不正解数
initial_wrong = sum(different)

# すでに不正解がK以下なら書き換え不要
if initial_wrong <= K:
    print(0)
else:
    # 不正解を修正するために必要な最小書き換え回数
    # つまり、現在不正解になっている問題のうち、どれだけ書き換える必要があるか
    # → (initial_wrong - K) 個の不正解を修正する必要がある
    print(initial_wrong - K)

この解説は qwen3-coder-480b によって生成されました。