概要

横一列に並んだ \(N\) 個の照明に対し、連続する \(K\) 個の照明の状態を一括で切り替える操作を繰り返して、すべてを点灯状態にするための最小操作回数を求める問題です。貪欲法と差分配列を用いて効率的に解きます。

考察

重要な気づき：左から貪欲に決める

操作は「位置 \(l\) から \(K\) 個連続して反転」というものです。ここで、左端から順番に見ていき、消灯している照明を見つけたら、その位置を起点に操作するという貪欲法が最適であることに気づきます。

なぜなら、ある位置 \(i\) の照明が消灯しているとき、それを点灯にできる操作の起点は \(i - K + 1\) 以上 \(i\) 以下の範囲に限られます。左から順に処理する場合、位置 \(i\) より左側はすでに点灯状態に確定しているので、\(i\) より前を起点にすると確定済みの照明を崩してしまいます。したがって、起点を \(i\) にする（つまり位置 \(i\) から右に \(K\) 個を反転する）のが唯一の選択肢です。

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

操作のたびに \(K\) 個の要素を実際に反転すると、最悪で \(O(N \times K)\) の計算量になり、\(N\) が最大 \(5 \times 10^5\) の場合は TLE になる可能性があります。

差分配列による高速化

各操作で「位置 \(i\) から位置 \(i+K-1\) まで反転回数を \(+1\)」する代わりに、差分配列（いもす法） を使います。差分配列 flip_diff を用意し、操作時に flip_diff[i] += 1, flip_diff[i+K] -= 1 とするだけで、累積和を取れば各位置の反転回数が \(O(1)\) で分かります。

アルゴリズム

1. 差分配列 flip_diff と累積反転回数 current_flips を初期化する。
2. 位置 \(i = 0, 1, \ldots, N-1\) を左から順に走査する：
   • current_flips += flip_diff[i] で現在の累積反転回数を更新する。
   • 照明 \(i\) の実効的な状態を (S[i] + current_flips) % 2 で計算する。元の状態に反転回数の偶奇を加味したものです。
   • 実効状態が \(0\)（消灯）ならば：
     • \(i + K > N\) の場合、起点 \(i\) からの操作は範囲外にはみ出すため不可能。-1 を出力して終了。
     • そうでなければ、操作回数を \(+1\) し、current_flips += 1, flip_diff[i + K] -= 1 と更新する。
3. 全位置を処理し終えたら、操作回数を出力する。

具体例

\(N = 5, K = 3, S = \) 01010 の場合：

位置	0	1	2	3	4
初期	0	1	0	1	0
\(i=0\): 消灯 → 位置0から反転	1	0	1	1	0
\(i=1\): 消灯 → 位置1から反転	1	1	0	0	0
\(i=2\): 消灯 → 位置2から反転	1	1	1	1	1

操作回数は 3 回です。

計算量

• 時間計算量: \(O(N)\) — 各位置を1回ずつ走査し、各位置で \(O(1)\) の処理を行う
• 空間計算量: \(O(N)\) — 状態配列と差分配列に \(O(N)\) を使用

実装のポイント

• 差分配列（いもす法） により、区間への加算操作を \(O(1)\) で実現している点が最大のポイントです。

• 実効状態の計算では (state[i] + current_flips) % 2 を使います。反転回数が奇数回なら状態が反転し、偶数回なら元のままという性質を利用しています。

• \(K = N\) の場合は操作の起点が \(l = 1\) のみに限られるため、全体を反転するか何もしないかの2択になりますが、このアルゴリズムは特別な場合分けなしに正しく処理します。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    S = input_data[2].decode()
    
    # We need all lights to be 1. 
    # Each operation flips K consecutive lights starting at position l.
    # This is a classic greedy problem with difference array technique.
    
    # If K == N, we can only flip all lights at once.
    # If K == 1, each light can be toggled independently.
    
    # Greedy approach: scan from left to right.
    # Whenever we encounter a light that is currently off (after accounting for previous flips),
    # we must flip starting at that position (if possible).
    
    # We use a difference array to track flips efficiently.
    # flip_count tracks the cumulative number of flips affecting position i.
    
    # State array: 0 means needs to be flipped (currently off), 1 means on
    state = [0] * N
    for i in range(N):
        state[i] = int(S[i])
    
    # diff array for tracking flips: flip_diff[i] means the change in flip count at position i
    flip_diff = [0] * (N + 1)
    current_flips = 0
    operations = 0
    
    for i in range(N):
        current_flips += flip_diff[i]
        # Current effective state: original XOR (current_flips % 2)
        effective = (state[i] + current_flips) % 2
        
        if effective == 0:
            # Need to flip starting at position i
            if i + K > N:
                # Cannot flip, impossible
                print(-1)
                return
            operations += 1
            current_flips += 1
            flip_diff[i + K] -= 1
    
    print(operations)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。