概要

現在の解答 \(S\) と正解 \(T\) の「違っている位置数」を数え、許容される不正解数 \(K\) まで減らすのに最低何回書き換えが必要かを求めます。

考察

各問題（各位置 \(i\)）について、\(S_i\) と \(T_i\) の関係は次の2通りしかありません。

• 一致している（\(S_i = T_i\)）：この位置はすでに正解
  ここを書き換えると必ず \(T_i\) と異なる値になり、不正解が1つ増えるだけで、目的（不正解を減らす）に逆効果です。
  よって最小回数を狙うなら、この位置は 絶対に書き換えないのが得です。
• 不一致（\(S_i \ne T_i\)）：この位置は不正解
  ここを1回書き換えて \(T_i\) に合わせれば、不正解を1つ減らせる。

つまり、やるべきことは - 「不一致な位置（不正解な位置）」の個数 \(m\) を数える - 不正解を \(m\) から \(K\) 以下にするために、最低何個の不一致を直す必要があるかを考える だけです。

不正解数を \(K\) 以下にするには、 - もし \(m \le K\) なら、すでに条件を満たしているので書き換えは 0 回 - もし \(m > K\) なら、不正解を \(K\) まで減らすために \(m-K\) 個の不一致を直す必要があります
（不一致1つを直すたびに不正解が1減るため、これが最小）

したがって答えは
$\(\max(0,\, m - K)\)$

具体例

• \(S=01010,\ T=01100\) のとき不一致は2箇所（\(m=2\)）
  • \(K=1\) なら \(m-K=1\) 箇所だけ直せばよい → 最小1回
  • \(K=3\) なら \(m \le K\) → 最小0回

アルゴリズム

1. \(S\) と \(T\) を同じ位置から順に見て、不一致な位置の数 \(m\) を数える。
2. 答えとして \(\max(0, m-K)\) を出力する。

計算量

• 時間計算量: \(O(N)\)（全ての位置を1回ずつ比較するだけ）
• 空間計算量: \(O(1)\)（カウンタ以外に大きな追加領域を使わない）

実装のポイント

• \(N \le 10^6\) なので、全探索 \(O(N)\) は十分間に合いますが、入力は大きいので sys.stdin.buffer.read() のような高速入力が安全です。

• 文字列同士を zip(S, T) で並べて比較し、不一致数を数えるだけで実装できます。

• 最終的に負にならないよう max(0, mismatches - K) にします。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    K = int(data[1])
    S = data[2]
    T = data[3]

    mismatches = 0
    for a, b in zip(S, T):
        if a != b:
            mismatches += 1

    ans = mismatches - K
    if ans < 0:
        ans = 0
    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。