概要

照明の状態を切り替える操作を繰り返してすべての照明を点灯状態にする最小回数を求める問題です。連続する \(K\) 個の照明の状態を反転させる操作を利用します。

考察

素朴なアプローチでは、左から順に照明を見ていき、消灯している照明が見つかったらその位置から始まる \(K\) 個の照明を反転させる貪欲法が考えられます。しかし、操作回数が最大で \(O(N)\) 回、各操作で \(K\) 個の照明を反転させるため、計算量が \(O(NK)\) となり、\(N\) が最大 \(500,000\) である本問題では時間制限に間に合いません。

そこで、反転操作の影響を効率的に管理する方法が必要です。反転操作は線形性を持つため、遅延評価を用いることで、各照明の反転回数を差分配列で管理できます。これにより、各照明の現在の状態を \(O(1)\) で計算できるようになります。

アルゴリズム

1. 初期状態の配列 arr を作成します（点灯:1, 消灯:0）。
2. 差分配列 diff を用意し、反転操作の影響を管理します。
3. 現在までの反転回数を保持する変数 flip_count を用意します。
4. 左から右へ各照明 \(i\) についてループします：
   • 差分配列から現在位置 \(i\) までの累積反転回数を flip_count に加算します。
   • 現在の照明の状態を (arr[i] + flip_count) % 2 で計算します。
   • 現在の状態が消灯（0）の場合：
     • 操作を行う必要があります。ただし、操作範囲が \(i\) から \(i+K-1\) までであるため、\(i+K-1 \geq N\) の場合は範囲外となり不可能なので -1 を出力します。
     • 操作回数を増やし、差分配列に操作の影響を記録します（diff[i] += 1, diff[i+K] -= 1）。
     • flip_count を増やし、現在の状態を点灯にします。
5. 最小操作回数を出力します。

この方法では、各照明の状態を定数時間で計算でき、全体として \(O(N)\) 時間で処理できます。

計算量

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

実装のポイント

• 差分配列は \(N+2\) のサイズで確保し、範囲外アクセスを防ぎます。

• 操作を行う前に、操作範囲が配列内に収まるかチェックします。

• 現在の状態は (初期値 + 反転回数) % 2 で計算します。反転操作は2回行うと元に戻るため、mod 2 で十分です。

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
    nk = data[0].split()
    if len(nk) < 2:
        print(-1)
        return
    N = int(nk[0])
    K = int(nk[1])
    S = data[1].strip()
    
    arr = [1 if c == '1' else 0 for c in S]
    diff = [0] * (N + 2)
    flip_count = 0
    res = 0
    
    for i in range(N):
        flip_count += diff[i]
        current = (arr[i] + flip_count) % 2
        if current == 0:
            if i + K - 1 >= N:
                print(-1)
                return
            res += 1
            flip_count += 1
            diff[i] += 1
            diff[i + K] -= 1
            current = 1
    
    print(res)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。