整数 \(i\) を選んで行う操作を操作 \(i\) と呼ぶことにします。

操作の順序を入れ替えても結果に影響しません。また、どの操作も同じ操作を \(2\) 回行うと、操作を行わなかった場合と同じ結果になります。よって、どの \(i\) についても操作 \(i\) を行う回数は \(0\) か \(1\) です。

電球 \(1\) の状態を変化させることができるのは、 操作 \(1\) を行ったときのみです。よって初期状態で電球 \(1\) が点灯しているときは操作 \(1\) を行い、消灯しているときは操作 \(1\) は行いません。
電球 \(1\) を消灯させたあと、他の操作は電球 \(1\) に影響を及ぼさないため、電球 \(1\) のことは忘れて残った \(N-1\) 個の電球に対して再び同じ問題を考えればよいです。

よって電球 \(1,2,3,\dots\) の順に電球の状態を見ながら操作 \(1,2,3,\dots\) を行うかどうかを決めるのが最適です。しかし実際に電球の状態を変化させる操作を行うと、操作 \(1\) 回あたり \(\Omega(K)\) の時間がかかるため、最悪ケースでは全体で \(\Omega(NK)\) となり、実行時間制限に間に合わせることは困難です。

そこで、各電球の隣との差に注目します。消灯している電球 \(0,N+1\) を追加し、「電球 \(i-1\) と電球 \(i\) の点灯/消灯の状態が異なるような \(i\) 」全体からなる集合を用意します。
操作 \(i\) を行うと、「電球 \(i-1\) と電球 \(i\)」「電球 \(i+K-1\) と電球 \(i-K\)」の差だけが変化します。よって、高々 2 個の要素の出し入れにより操作をシミュレートすることができます。全ての電球が消灯していることは、この集合が空であることと同値になります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int>a(n+2);
  for(int i=1; i<=n; i++) cin >> a[i];

  set<int>s;
  for(int i=1;i<=n+1; i++){
    if(a[i-1] != a[i]){
      s.insert(i);
    }
  }

  int count = 0;
  for(int i=1; i<=n-k+1; i++){
    if(s.contains(i)){
      count++;
      s.erase(i);
      if(s.contains(i+k)){
        s.erase(i+k);
      }else{
        s.insert(i+k);
      }
    }
  }

  if(s.size() == 0){
    cout << count << endl;
  }else{
    cout << -1 << endl;
  }
}

実装例 (Python)

N, K = map(int, input().split())
A = [0] + list(map(int, input().split())) + [0]
S = set()
for i in range(1, N+2):
  if A[i-1] != A[i]:
    S.add(i)

count = 0
for i in range(1, N-K+1+1):
  if i in S:
    count += 1
    S.remove(i)
    if i+K in S:
      S.remove(i+K)
    else:
      S.add(i+K)

if len(S) == 0:
  print(count)
else:
  print(-1)