概要

連続する \(K\) 個の電球を反転させる操作を繰り返して、すべての電球を点灯状態にできるかを判定し、可能な場合は最小操作回数を求める問題です。貪欲法と差分配列を組み合わせて効率的に解きます。

考察

重要な気づき

1. 操作順序は結果に影響しない

どの順番で操作を行っても、各位置が「奇数回反転されたか偶数回反転されたか」だけが最終状態を決めます。これはXOR演算の性質によるものです。

2. 左から順に決定できる（貪欲法）

位置 \(i\) の電球を反転させられる操作は、位置 \(i-K+1\) から位置 \(i\) までのどこかから始まる操作です。左端から見ていくと、位置 \(i\) に影響を与える「新しい操作」は位置 \(i\) から始まる操作だけになります。

したがって、左から順に見て： - 電球 \(i\) が消灯 → 位置 \(i\) から始まる操作を必ず行う - 電球 \(i\) が点灯 → 操作は行わない

これが最適解を与えます。

3. 素朴な実装の問題点

操作のたびに \(K\) 個の電球を実際に反転させると、1回の操作に \(O(K)\) かかり、最悪 \(O(NK)\) となってTLEの可能性があります。

解決策：差分配列（いもす法）

「位置 \(i\) から \(K\) 個を反転」という区間更新を効率化するため、差分配列を使います。

• flip[i] : 位置 \(i\) で反転効果が始まる
• flip[i+K] : 位置 \(i+K\) で反転効果が終わる（-1を加える）

累積和を取りながら進むことで、各位置での「現在の累積反転回数」が \(O(1)\) で分かります。

アルゴリズム

1. 差分配列 flip と累積反転回数 current_flip を初期化
2. 左から順に各位置 \(i\) を処理：
   • current_flip += flip[i] で累積反転回数を更新
   • 実際の状態 = \((A[i] + \text{current\_flip}) \mod 2\)
   • 状態が \(1\)（消灯）なら：
     • \(i + K > N\) の場合、操作不可能なので -1 を出力
     • そうでなければ、操作を行う：

          - `operations += 1`
          - `current_flip += 1`（位置 $i$ から反転開始）
          - `flip[i + K] -= 1`（位置 $i+K$ で反転効果終了）
       

3. 全位置を処理できたら operations を出力

具体例

\(N=5, K=3, A=[1,0,1,0,0]\) の場合：

位置	元の状態	累積反転	実際の状態	操作
0	1	0	1	操作実行
1	0	1	1	操作実行
2	1	2	1	操作実行
3	0	2	0	なし
4	0	1	1	操作不可（範囲外）→ -1

計算量

• 時間計算量: \(O(N)\)
  • 各位置を1回ずつ処理し、各処理は \(O(1)\)
• 空間計算量: \(O(N)\)
  • 入力配列 \(A\) と差分配列 flip に \(O(N)\)

実装のポイント

• 差分配列のサイズ: flip[i + K] にアクセスするため、サイズは \(N+1\) 以上必要

• 状態の計算: (A[i] + current_flip) % 2 で、偶数回反転なら元の状態、奇数回反転なら反転した状態

• 境界チェック: \(i + K > N\) のとき操作できないことを忘れずに確認

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 目標: すべての電球を点灯状態(0)にする
    # 操作: 位置iから始まる連続K個の電球を反転させる (i = 0, 1, ..., N-K)
    
    # 貪欲法: 左から順に見ていき、消灯(1)の電球を見つけたら
    # その位置から始まる操作を行う
    
    # 差分配列を使って効率的に反転を管理する
    # flip[i] = 位置iで反転が「始まる」回数
    # 累積和を取ることで、各位置での実際の反転回数がわかる
    
    flip = [0] * (N + 1)  # flip[i]は位置iで反転効果が始まる
    current_flip = 0  # 現在の位置までの累積反転回数
    operations = 0
    
    for i in range(N):
        # 位置iでの反転効果を更新
        current_flip += flip[i]
        
        # 現在の電球の状態を計算
        # A[i]が元の状態、current_flip回反転されている
        actual_state = (A[i] + current_flip) % 2
        
        if actual_state == 1:  # 消灯している
            # この位置から操作を行う必要がある
            if i + K > N:
                # 操作できない（範囲外）
                print(-1)
                return
            
            # 位置iからKの範囲を反転
            operations += 1
            current_flip += 1  # 位置iから反転開始
            flip[i + K] -= 1   # 位置i+Kで反転効果終了
    
    print(operations)

solve()

---

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