この問題の操作には、以下の重要な性質があります。

• 操作の順番を入れ替えても結果が変わらない。
• 同じ操作を \(2\) 回掛けると元の状態に戻る。

その結果、左端 \(l=1,2,\dots,N-K+1\) を \(0\) 回掛けたか \(1\) 回掛けたかが問題となります。

計算量を気にせず考えると、以下のように操作を確定させられます。

• \(i=1,2,\dots,N-K+1\) について、以下を繰り返す。
  • 現時点で、電灯 \(i\) の状態を変更できる、行う回数が確定していない操作は、 \(i\) を左端する操作しかないことに注意する。
    • 現時点で電灯 \(i\) が点灯していれば、 \(i\) を左端とした操作を \(0\) 回掛ける必要があるため、そう決める。
    • 現時点で電灯 \(i\) が消灯していれば、 \(i\) を左端とした操作を \(1\) 回掛ける必要があるため、そう決めて操作を掛ける。
• 全て終わった時点で全ての電灯が点灯していればそれが操作回数の最小で、そうでなければ全ての電灯を点灯させることができないと分かる。

愚直に操作を掛けた場合、時間計算量が \(O(NK)\) となり実行時間制限に間に合いません。

これを解消するにはいくつかの方法があります。

• 遅延 segment tree を活用して時間計算量 \(O(N \log N)\) に落とす。詳細は省略します。
• imos 法 の要領で時間計算量 \(O(N)\) に落とす。

後者を詳説します。

• 配列 \(f=(0,0,\dots,0)\) を用意する。
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • 現時点での \(f[i]\) が電灯 \(i\) の状態を切り替えた回数である。
  • 電灯 \(i\) を左端とする操作が必要になったと分かった時に、以下を行う。
    • \(i+K-1 > N\) ならそのような操作は行えないので、全ての電灯を点灯させることが不可能であると分かる。
    • そうでないなら \(f[i]\) に \(1\) 加算し、 \(f[i+K]\) から \(1\) 減算する。
  • \(f[i+1]\) に \(f[i]\) を加算する。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  string S;
  cin >> S;

  int res=0;
  vector<int> flip(N+1,0);
  for(int i=0;i<N;i++){
    if((S[i]=='0') ^ (flip[i]%2==1)){
      if((i+K) > N){
        cout << "-1\n";
        return 0;
      }
      res++;
      flip[i]++;
      flip[i+K]--;
    }
    flip[i+1]+=flip[i];
  }
  cout << res << "\n";
  return 0;
}