概要

連続する \(K\) 個の照明の状態を一括で反転できる操作を用いて、すべての照明を「点灯」状態にする最小操作回数を求める問題。

考察

この問題の核心は、「操作は区間に対して行われるが、最終的には各照明が点灯しているかどうかだけが重要」という点です。

重要な観察

• 各照明の最終的な状態は、それが何回反転されたかによって決まります。
• 反転回数が偶数回なら状態は変化せず、奇数回なら反転します。
• よって、各照明について「何回操作されたかの parity（偶奇）」だけを考えればよいです。

素朴なアプローチの問題点

例えば、全通りの区間を選ぶ組み合わせを試すのは、\(N\) が最大 \(5 \times 10^5\) なので現実的ではありません（指数時間かかる）。

また、単純に左から順に操作していけばいいのか？という疑問もありますが、これは正しい方針です。理由は： - 操作は区間に対して加算的に作用するので、左から順に見ていくことで、ある照明に影響を与える操作がすべて処理済みになります。 - ある照明がまだ点灯していない場合、それ以降の区間の中で操作を行うことで修正できます。

解決方法

• 区間に操作が何回行われたかを効率的に管理するために、スライドウィンドウ的な差分更新を使います。
• 具体的には、操作開始位置をキューで管理し、その区間が終了したら parity を戻します。
• 各照明について、それが最終的に点灯するように操作を行うべきかを貪欲に判断していきます。

具体例

入力例：

N=5, K=3
S="01000"

初期状態: 0 1 0 0 0

操作1: 区間 [1,3] を反転 → 1 0 1 0 0
操作2: 区間 [2,4] を反転 → 1 1 0 1 0
操作3: 区間 [3,5] を反転 → 1 1 1 0 1
操作4: 区間 [4,6] は範囲外 → 不可 → -1

このように、最後まで点灯できない場合は -1 を出力します。

アルゴリズム

1. 照明の状態を 0 / 1 の配列に変換します。
2. 左から順に照明を見ていき、その時点での「操作回数の偶奇 (flip_parity)」を管理します。
3. 現在位置 \(i\) において、照明の状態が目標（点灯 = 1）になっていない場合：
   • \(i\) から始まる長さ \(K\) の区間が存在すれば、その区間に操作を行います。
   • 操作回数 parity を更新し、開始位置をキューに追加します。
   • 操作回数をカウントアップします。
4. \(i + K > N\) であれば、操作が不可能なので -1 を出力します。
5. 最後に操作回数を出力します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(K)\)（キューのサイズは最大 \(K\)）

実装のポイント

• 各照明の処理時に、操作の影響範囲（直近 \(K\) 個）をキューで管理し、古い操作を削除することで効率よく parity を維持します。

• 現在の照明の状態は state[i] ^ flip_parity で求められます。

• 操作が不可能なケース（区間がはみ出す）は速めに検出し、即 -1 を返す必要があります。

  ソースコード

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    S = data[2]
    
    # 状態を0/1のリストに変換 (0: 消灯, 1: 点灯)
    state = [int(c) for c in S]
    
    # 目標は全て1（点灯）なので、現在の状態と目標の差分を考える
    # 各位置について、その位置が最終的に1になってほしい
    # つまり、操作の結果、各ビットが奇数回反転されたらよい
    
    # 差分配列 diff[i] := 位置 i での操作回数の parity（偶奇）
    # 実際には、操作は区間 [l, l+K-1] に対して行われるので、差分更新が有効
    
    # 初期状態がすべて1になるように操作回数を調整する
    # つまり、初期状態が0なら反転させたい（操作回数を奇数回）、1ならそのまま（偶数回）
    # ただし、操作は区間に対して行われるため、貪欲に左から処理していく
    
    # 各位置で、その位置が最終的に1になるために操作が必要かどうかを判断
    # 操作の影響範囲は K なので、スライドしながら処理する
    
    # flip_count: 現在の位置に影響を与えている操作の回数の parity
    flip_parity = 0
    # 操作を行った位置を記録するキュー（操作開始位置）
    queue = deque()
    operations = 0
    
    for i in range(N):
        # K個前の操作が範囲外に出た場合は parity から除外
        if queue and queue[0] <= i - K:
            queue.popleft()
            flip_parity ^= 1
        
        # 現在の照明の状態（操作による反転を考慮）
        current = state[i] ^ flip_parity
        
        # 目標は1（点灯）なので、current が 0 なら操作が必要
        if current == 0:
            # 操作は i から始まる K 長の区間に対して行う
            # ただし、i 以降 K 個の区間が存在する必要がある
            if i + K > N:
                print(-1)
                return
            # 操作を行う（実際には parity を更新し、queue に記録）
            flip_parity ^= 1
            queue.append(i)
            operations += 1
    
    print(operations)

if __name__ == "__main__":
    main()

---

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