概要

高橋君の解答文字列 \(S\) と正解文字列 \(T\) を比較し、不正解の問題数を \(K\) 以下にするために必要な最小の書き換え回数を求める問題です。

考察

問題を解くための重要な気づきは、「1回の書き換えで不正解数を最大1つ減らせる」ということです。

書き換え回数を最小にしたいので、すでに正解している（\(S\) と \(T\) で文字が一致している）問題をわざわざ書き換える必要はありません。不正解となっている（\(S\) と \(T\) で文字が異なる）問題だけをピンポイントで正しい解答に書き換えるのが最適な戦略です。

まず、書き換えを行う前の初期状態での不正解数を数えます。これを \(D\) としましょう。 - \(D \leq K\) の場合：すでに不正解数が許容範囲内なので、1回も書き換える必要はありません。答えは \(0\) です。 - \(D > K\) の場合：不正解数が \(K\) 個になるまで、間違っている問題を正しい解答に書き換える必要があります。必要な書き換え回数は \(D - K\) 回です。

したがって、求める答えは \(\max(0, D - K)\) というシンプルな計算で求めることができます。

アルゴリズム

1. 文字列 \(S\) と \(T\) の同じ位置の文字を先頭から順に比較し、異なる文字の個数（初期の不正解数）をカウントします。これを diff_count とします。
2. diff_count - K を計算し、もし値が負であれば \(0\) にします（数式では \(\max(0, \text{diff\_count} - K)\)）。
3. 計算した値を出力します。

計算量

• 時間計算量: \(O(N)\) 長さ \(N\) の文字列 \(S\) と \(T\) を先頭から1回走査して比較するだけなので、\(O(N)\) となります。制約の \(N \leq 10^6\) に対しても余裕で実行時間制限に間に合います。
• 空間計算量: \(O(N)\) 長さ \(N\) の文字列 \(S\) と \(T\) をメモリ上に保持するため、\(O(N)\) の空間を使用します。

実装のポイント

• Pythonでは zip(S, T) を使うことで、2つの文字列の同じ位置の文字を同時に取り出して比較する処理をとても簡潔に書くことができます。

• 入力サイズが最大 \(10^6\) と大きいため、標準の input() の代わりに sys.stdin.read().split() を用いると、入力の読み込みを高速化でき、TLE（実行時間切れ）のリスクを減らすことができます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    S = input_data[2]
    T = input_data[3]
    
    diff_count = sum(s != t for s, t in zip(S, T))
    
    ans = max(0, diff_count - K)
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。