Overview

Given Takahashi’s answers and the correct answers, we need to minimize the number of rewrites to make the number of incorrect problems at most \(K\).

Analysis

First, by comparing Takahashi’s answers \(S\) with the correct answers \(T\) in the initial state, we can determine which problems are incorrect. For example, if \(S = "010"\) and \(T = "110"\), only the 1st problem is incorrect.

In this case, if the number of incorrect problems is already at most \(K\), no rewrites are needed. Otherwise, we need to reduce the number of incorrect answers by “rewriting some incorrect problems to the correct answer.”

A key observation is that “rewriting one incorrect problem to the correct answer” = “the number of rewrites increases by 1.” Conversely, “rewriting a correct problem to an incorrect answer” is meaningless — it only increases the number of rewrites while also increasing the number of incorrect answers.

Therefore, letting the initial number of incorrect answers be \(W\), to make the number of incorrect answers at most \(K\), we need to rewrite at least \(W - K\) incorrect problems to the correct answer. This operation is exactly the minimum number of rewrites.

For example: - \(N = 5\), \(K = 1\) - \(S = "00000"\) - \(T = "11111"\) - The initial number of incorrect answers is 5, and the target is at most 1, so we need \(5 - 1 = 4\) rewrites.

Algorithm

1. Compare strings \(S\) and \(T\) to determine whether each problem is incorrect.
2. Count the number of incorrect problems \(W\).
3. If \(W \leq K\), no rewrites are needed, so the answer is \(0\).
4. Otherwise, \(W - K\) is the minimum number of rewrites.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• To determine correctness of each problem, simply compare each position of the strings.

• Creating a list of True/False values makes it easier to handle.

• Be careful whether to use \(W - K\) or \(\max(0, W - K)\) to ensure the final answer does not become negative, but since the problem guarantees it is always possible, this consideration is unnecessary.

  Source Code

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)

This editorial was generated by qwen3-coder-480b.