概要

長さ \(N\) の 0/1 列に対し、長さ \(K\) の区間反転（0↔1）を好きなだけ行って、全てを 1 にできるか判定し、できるなら最小操作回数を求めます。

考察

重要な気づき（左から貪欲に決めてよい）

照明 \(i\) を見たとき、今後の操作で照明 \(i\) の状態を変えられるのは「左端が \(i\) 以下の区間反転」だけです。
特に、位置 \(i\) を含む区間反転の左端 \(l\) は \(l \le i \le l+K-1\) なので、\(l \le i\) が必要です。

したがって、左から順に見ていき、

• 現時点で照明 \(i\) が 0 なら、照明 \(i\) を 1 にするには 左端がちょうど \(i\) の反転を行うしかない（それより左の選択は過去に決まっているため）。
• 現時点で照明 \(i\) が 1 なら、ここで余計な反転をすると 0 になってしまうので行わない。

という貪欲が成立します。これにより「最小回数」も自動的に保証されます（各 \(i\) で必要なら1回、不要なら0回しか選択肢がないため）。

素朴法が遅い理由

操作を行うたびに長さ \(K\) 区間の各ビットを反転すると、1回 \(O(K)\)。最悪で \(O(N)\) 回操作が起こり得るため、合計 \(O(NK)\) となり、\(N \le 5\times 10^5\) では間に合いません。

どう解決するか（「今までの反転回数の偶奇」だけ管理）

反転は「偶数回なら元のまま、奇数回なら反転」と考えられるので、各位置 \(i\) について必要なのは - 位置 \(i\) にかかっている反転回数の 偶奇（0/1） だけです。

これを高速に管理するために「いつ反転の影響が終わるか」を記録する差分配列（いわゆる imos）を使います。

アルゴリズム

左から \(i=0,1,\dots,N-1\) と見ていきます（以下 0-index で説明）。

• parity：現在位置 \(i\) にかかっている反転回数の偶奇（0=偶数回, 1=奇数回）
• end[t]：位置 \(t\) に来たときに parity を反転させる必要があるか（区間反転の効果が \(t\) で終わる印）

手順： 1. 各 \(i\) でまず parity ^= end[i] を行い、期限切れの反転効果を反映する。 2. 現在の実際のビットは
$\( \text{bit} = S[i] \oplus \text{parity} \)\( で求まる（`parity=1` なら反転して見える）。 3. もし `bit == 0` なら、ここで照明 \)i\( を 1 にするには左端 \)i\( の操作が必須。 - ただし区間 \)[i, i+K-1]\( が作れない（\)i+K>N\(）なら不可能なので `-1`。 - 可能なら操作回数 `ops += 1`。 - 反転が始まるので `parity ^= 1`。 - 反転が \)i+K$ で終わる印として end[i+K] ^= 1 を立てる。 4. 最後まで処理できれば ops が最小回数。

具体例

\(N=5, K=3, S=00101\) とします。

• \(i=0\): 現在 0 → 操作（0..2反転）。ops=1
• \(i=1\): 反転が効いているので見かけが変わる。必要なら操作…というように、 各位置で「今0ならここで反転するしかない」を繰り返し、無駄な操作が入りません。

計算量

• 時間計算量: \(O(N)\)（各位置で定数回の更新のみ）
• 空間計算量: \(O(N)\)（end 配列）

実装のポイント

• 文字 S[i] は '0'/'1' なので、ord(S[i]) - 48 で 0/1 に変換しています（int(S[i]) でも可）。

• end は長さ N+1 にして、i+K == N のときでも end[N] に安全に書けるようにします。

• 反転回数そのものではなく「偶奇」だけ使うため、更新は全て XOR（^= 1）で済みます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = input().strip()

    end = [0] * (N + 1)
    parity = 0
    ops = 0

    for i in range(N):
        parity ^= end[i]
        bit = (ord(S[i]) - 48) ^ parity
        if bit == 0:
            if i + K > N:
                print(-1)
                return
            ops += 1
            parity ^= 1
            end[i + K] ^= 1

    print(ops)

if __name__ == "__main__":
    main()

---

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