概要

高橋君の解答 \(S\) を最小回数書き換えて、正解 \(T\) との不一致（不正解）を \(K\) 問以下にする問題です。

考察

重要な気づき：書き換えの2種類を区別する

\(S\) の各位置 \(i\) について、\(S[i]\) と \(T[i]\) の関係は次の2パターンです：

• 一致している位置：\(S[i] = T[i]\)（すでに正解）
• 不一致の位置：\(S[i] \neq T[i]\)（不正解）

不一致の位置の総数を \(W\)（Wrong の数）とします。

書き換えの効果を考える

書き換え操作は「\(S\) の文字を変更する」ことですが、その効果は位置によって異なります：

1. 不一致の位置を書き換える（修正）：\(S[i] \neq T[i]\) の位置で \(S[i]\) を \(T[i]\) に変える → 不正解が 1つ減る、書き換え回数 1
2. 一致の位置を書き換える（改悪）：\(S[i] = T[i]\) の位置で \(S[i]\) を変える → 不正解が 1つ増える、書き換え回数 1
3. 不一致の位置を別の間違いに変える：\(S[i] \neq T[i]\) の位置で \(T[i]\) でもない値に変える → 不正解数は変わらず、書き換え回数 1（意味がない）

不正解数を減らしたいのですから、パターン1（不一致の位置を正解に直す）だけを使えばよいことが分かります。改悪や無意味な変更をする理由はありません。

必要な書き換え回数

現在の不正解数が \(W\) 問で、\(K\) 問以下にしたいので：

• \(W \leq K\) ならば、すでに条件を満たしているので書き換えは 0回
• \(W > K\) ならば、不正解を \(W - K\) 問減らす必要があり、1回の修正で不正解が1つ減るので、書き換え回数は \(W - K\) 回

よって答えは \(\max(0, W - K)\) です。

具体例

\(N = 5, K = 1, S = \) 10110, \(T = \) 01100 の場合：

位置	1	2	3	4	5
\(S\)	1	0	1	1	0
\(T\)	0	1	1	0	0
一致?	✗	✗	✓	✗	✓

不一致は \(W = 3\) 箇所。\(K = 1\) 以下にするには \(3 - 1 = 2\) 回の書き換えが必要です。

アルゴリズム

1. \(S\) と \(T\) を1文字ずつ比較し、不一致の個数 \(W\) を数える
2. \(\max(0, W - K)\) を出力する

計算量

• 時間計算量: \(O(N)\)（文字列を1回走査するだけ）
• 空間計算量: \(O(N)\)（文字列 \(S, T\) の格納分）

実装のポイント

• \(N\) が最大 \(10^6\) と大きいですが、\(O(N)\) で十分間に合います。

• Python では sum(1 for i in range(N) if S[i] != T[i]) のようなジェネレータ式で簡潔に不一致数を数えられます。

• \(W \leq K\) の場合に答えが負にならないよう、max(0, ...) を忘れないようにしましょう。

  ソースコード

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

# Count the number of positions where S and T differ
wrong = sum(1 for i in range(N) if S[i] != T[i])

# We need to reduce wrong to at most K
# Each fix (changing S[i] to T[i] where they differ) reduces wrong by 1 and costs 1 edit
# We need max(0, wrong - K) fixes
print(max(0, wrong - K))

---

この解説は claude4.6opus-thinking によって生成されました。