概要

連続する \(K\) 個の電球の状態を一斉に反転させることを繰り返して、すべての電球を点灯状態にできるか判定し、できる場合は最小操作回数を求めます。

考察

この問題では、操作によって連続する \(K\) 個の電球の状態が同時に変化します。したがって、ある位置の電球が最終的にどうなるかは、その位置を含むすべての操作の回数に依存します。

素朴な方法として、実際にシミュレーションしながらすべての電球を点灯させていくことを考えますが、単純に毎回 \(K\) 個の要素を反転させると、最悪の場合 \(O(N^2)\) の計算量になり、\(N\) が最大 \(2 \times 10^5\) なので間に合いません。

重要な観察は、操作の影響を累積的に管理することで、現在の電球の状態を高速に求められることです。つまり、ある操作の開始位置と終了位置を記録しておき、範囲の影響を差分更新（imos法のような考え方）で管理すれば、各電球の現在の状態を \(O(1)\) で求めることができます。

また、左から順番に処理していき、ある位置が消灯状態であれば、その位置から始まる長さ \(K\) の区間に操作を行うのが最適です。なぜなら、その区間を後で操作しても結果は変わらないからです。ただし、区間が配列外に出る場合（つまり \(i + K > N\)）は操作できないので、その時点で -1 を出力します。

アルゴリズム

1. 各操作の影響を記録するために flip_count 配列を用意します（imos法風）。これは区間の開始と終了を記録するために使います。
2. current_flip 変数で、現在の位置に影響を与えている操作の回数の偶奇（つまり反転回数の合計のmod 2）を管理します。
3. 左から順番に各電球を見ていき、その時点での状態（初期状態 XOR 現在の反転回数）が 1（消灯）であれば、その位置から始まる長さ \(K\) の区間に操作を行います。
4. 操作を行う際は：
   • operations をインクリメント
   • current_flip を反転
   • flip_count[i + K] に反転操作を記録（区間の終了地点）
5. 区間が範囲外になる場合は -1 を出力して終了。
6. 最後に操作回数 operations を出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• flip_count は区間の終端を記録する場所として \(N+1\) のサイズを確保する必要があります。
• current_flip は、flip_count[i] を反映して毎回更新する必要があります（差分更新）。
• 電球の状態は XOR を使って簡潔に計算できます。

## ソースコード

```python
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 0: 点灯, 1: 消灯 → 目標はすべて0にする
    # 各位置について、操作の影響を管理する
    # 差分更新で効率的にシミュレーション
    
    flip_count = [0] * (N + 1)  # imos法で操作回数を記録
    current_flip = 0
    operations = 0
    queue = deque()

    for i in range(N):
        current_flip ^= flip_count[i]
        current_state = A[i] ^ current_flip
        if current_state == 1:  # 消灯状態なら反転が必要
            if i + K > N:
                print(-1)
                return
            # 区間 [i, i+K) に操作を適用
            operations += 1
            current_flip ^= 1
            if i + K < N + 1:
                flip_count[i + K] ^= 1
    print(operations)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。