概要

連続する \(K\) 個の電球を反転できるとき、左から順に「その位置を確定させる」貪欲法で、全てを点灯（\(0\)）にできるかと最小操作回数を求めます。

考察

重要な観察

• 電球の状態は \(0/1\) の2値で、反転操作は「\(0 \leftrightarrow 1\)」なので、各電球に対して「何回反転されたか（偶数回か奇数回か）」だけが重要です。
• 左から順に見ていくと、位置 \(i\) の電球に影響を与えられる操作は「開始位置が \(i-K+1\) から \(i\) のどこか」の操作ですが、特に \(i\) を含む操作をこれ以上後ろから開始して \(i\) を直すことは不可能です（開始位置が \(i+1\) 以降だと \(i\) を含まない）。

このため、左から順に見ていき、 - その時点での「実際の状態」が \(1\)（消灯）なら、必ず位置 \(i\) から反転を開始する
という貪欲が成り立ちます。これが最小回数にもなります（必要なときにしか押さないため）。

素朴な方法がダメな理由

操作を行うたびに区間 \([i, i+K)\) を実際に反転すると、1回の操作が \(O(K)\) かかり、最悪で \(O(NK)\) になって \(N=2\times 10^5\) では間に合いません。

解決策

「今の位置がこれまでの操作で何回（奇偶）反転されているか」だけを管理します。 - 反転の影響が「いつ始まり、いつ終わるか」を差分的に持てば、各位置を \(O(1)\) で処理できます。

アルゴリズム

左から \(i=0,1,\dots,N-1\) と走査します（0-indexで説明）。

1. cur を「現在位置にかかっている反転回数の奇偶（0:偶数, 1:奇数）」とする。
2. diff を長さ \(N+1\) の配列として用意し、diff[x]=1 なら「位置 \(x\) で反転の影響（cur）を切り替える」ことを表す（差分配列）。
3. 各位置 \(i\) で
   • cur ^= diff[i] により、「ここで影響が終わる反転」を反映する
   • 実際の見かけの状態は \(A[i] \oplus cur\)
     • これが \(1\) なら消灯なので、ここを直すには 位置 \(i\) から長さ \(K\) の反転を開始するしかない

          - もし $i+K > N$ なら区間がはみ出すので不可能 → `-1`
          - そうでなければ操作回数を増やし、反転開始を反映：
       

       • cur ^= 1（今から先 \(K\) 個は反転が1回増える）
       • diff[i+K] ^= 1（位置 \(i+K\) でその反転の影響が終わる）

この手順で最後まで矛盾なく進めば、得られた操作回数が最小です。

（例） - ある位置 \(i\) で見かけが \(1\) なら、その位置を含む操作を後から開始して直すことはできないため、その場で押す以外に選択肢がありません。

計算量

• 時間計算量: \(O(N)\)（各位置で定数回の処理）
• 空間計算量: \(O(N)\)（差分配列 diff）

実装のポイント

• cur と diff は「奇偶」だけ分かればよいので、加算ではなく XOR（^=）で管理すると簡潔です。

• diff は i+K にアクセスするため長さを \(N+1\) にします（i+K == N も合法）。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読むと高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    diff = [0] * (N + 1)
    cur = 0
    ans = 0

    for i in range(N):
        cur ^= diff[i]
        if (A[i] ^ cur) == 1:
            if i + K > N:
                print(-1)
                return
            ans += 1
            cur ^= 1
            diff[i + K] ^= 1

    print(ans)

if __name__ == "__main__":
    main()

---

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