概要

\(N\) 個の電球の状態（点灯・消灯）を、連続する \(K\) 個一斉に反転させる操作を繰り返して、すべてを「点灯」状態にするために必要な最小操作回数を求める問題です。

考察

1. 操作の性質

この問題には、以下の重要な性質があります。 - 操作の順番は関係ない: どの範囲を先に反転させても、最終的な状態は変わりません。 - 同じ範囲を2回反転させる意味はない: 2回反転させると元の状態に戻るため、各範囲について「操作する」か「操作しない」かの2択だけを考えれば十分です。

2. 端から決めていく「貪欲法」

左端の電球（電球 \(1\)）に注目します。この電球の状態を変化させることができる操作は、「電球 \(1\) から \(K\) までの範囲を反転させる」という 1種類のみ です。 したがって、もし電球 \(1\) が消灯しているなら、すべての電球を点灯させるためには、この操作を必ず行う必要があります。

電球 \(1\) の状態を確定させた後は、電球 \(2\) に注目します。電球 \(2\) の状態を変化させられる操作のうち、まだ「やるかやらないか」が決まっていないのは「電球 \(2\) から \(K+1\) までを反転させる」操作のみです。

このように、左から順番に「今の電球が消灯していたら、そこを起点とする \(K\) 個を反転させる」という判断を繰り返す 貪欲法 で最適解（最小回数）が求まります。

3. 高速化の工夫

愚直に「\(K\) 個を反転させる」という処理を行うと、1回の操作に \(O(K)\) かかり、全体で \(O(NK)\) の時間がかかってしまいます。\(N, K \le 2 \times 10^5\) であるため、これでは制限時間に間に合いません。

そこで、「今見ている電球が合計で何回反転されたか」 を効率的に管理する必要があります。 ある電球 \(i\) の現在の状態は、以下の情報の組み合わせで決まります。 - 初期状態 \(A_i\) - インデックス \(i\) より左側で開始された操作のうち、電球 \(i\) を含んでいるものの個数

これは「いもす法」のような差分の考え方、または「反転状態を管理するキュー」を用いることで、各ステップ \(O(1)\)、全体で \(O(N)\) で計算できるようになります。

アルゴリズム

1. 差分配列（またはフラグ管理用の配列） diff を用意し、現在かかっている反転の累積状態を current_flips (0 または 1) として保持します。
2. 左端から順に電球 \(i\) (\(1\) から \(N-K+1\) まで) を見ていきます。
   • diff[i] を参照し、その地点で終了する操作があれば current_flips を更新（XOR）します。
   • 電球 \(i\) の現在の状態を A[i] ^ current_flips で求めます。
   • もし状態が \(1\)（消灯）であれば：
     • 操作回数を \(+1\) する。
     • current_flips を反転させる。
     • この操作の影響が切れる地点 i + K に印を付ける（diff[i + K] を更新）。
3. 操作が開始できない残りの電球（\(N-K+2\) 以降）について、同様に現在の状態を確認します。
   • もし一つでも \(1\)（消灯）の電球が残っていれば、すべての電球を点灯させることは不可能なので -1 を出力します。
4. 最後まで矛盾がなければ、カウントした操作回数を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の電球を左から右へ 1 回走査するだけで済むため、非常に高速です。
• 空間計算量: \(O(N)\)
  • 入力データと、反転状態を管理するための配列 diff の分が必要です。

実装のポイント

• XOR演算 (^) の活用: 「反転の反転は元通り」という性質は、ビット演算の XOR と相性が非常に良いです。current_flips ^= 1 とすることで、0 と 1 を簡単に切り替えられます。

• 範囲外の参照: \(i+K\) が \(N\) を超える場合の処理に注意が必要ですが、今回のアルゴリズムでは \(N-K+1\) までしか操作を開始しないため、適切に配列サイズを確保すれば問題ありません。

  ソースコード

import sys

def solve():
    # Fast I/O to read all input at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of bulbs, K is the number of consecutive bulbs to flip
    N = int(input_data[0])
    K = int(input_data[1])
    # A[i] = 0 means ON, A[i] = 1 means OFF
    A = [int(x) for x in input_data[2:]]
    
    # diff array to track where a flip operation ends.
    # diff[i] is flipped when an operation started at i-K ends.
    diff = [0] * (N + 1)
    
    # current_flips keeps track of the cumulative flip state (XOR sum) 
    # for the bulb at the current index i.
    current_flips = 0
    ans = 0
    
    # Greedy strategy: process from left to right.
    # To turn all bulbs ON, we must flip the leftmost bulb if it is currently OFF.
    # The only way to flip bulb i without affecting bulbs j < i is to start 
    # a flip operation at index i.
    for i in range(N - K + 1):
        # Apply the toggle marker for an operation that was started at i-K.
        current_flips ^= diff[i]
        
        # (A[i] ^ current_flips) gives the current state of the i-th bulb.
        # If the result is 1, the bulb is OFF.
        if (A[i] ^ current_flips) == 1:
            # We must perform a flip starting at index i.
            ans += 1
            # Update the current flip state for the following bulbs.
            current_flips ^= 1
            # Mark the end of this flip operation at index i + K.
            if i + K <= N:
                diff[i + K] ^= 1
    
    # After the greedy pass, we check if the remaining bulbs (where no new
    # flip operations could be started) are all ON.
    for i in range(N - K + 1, N):
        current_flips ^= diff[i]
        if (A[i] ^ current_flips) == 1:
            # It's impossible to turn this bulb ON.
            print("-1")
            return
    
    # If all bulbs are ON, output the minimum operation count.
    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。