愚直な方法では \(\Theta(M(N-M))\) となり、実行時間制限に間に合わせるのは非常に困難です。より高速な方法を考えます。

まず、\(1\) 日目から \(M\) 日目までにある晴れの日の日数を求めます。これは \(O(M)\) でできます。その次に \(2\) 日目から \(M+1\) 日目までにある晴れの日の日数を考えると、これは「\(1\) 日目から \(M\) 日目までにある晴れの日の日数」から \(1\) 日目の分を除外し、\(M+1\) 日目の分を追加したものです。よって \(O(1)\) で計算することができます。これを繰り返すことで \(O(N)\) でこの問題を解くことができます。

実装例 (C++)

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

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  string s;
  cin >> s;

  int count = 0;
  for(int i=0; i<m-1; i++){
    if(s[i] == '1'){
      count++;
    }
  }

  int ans = 0;
  for(int i=m-1; i<n; i++){
    if(s[i] == '1'){
      count++;
    }
    if(count < k){
      ans++;
    }
    if(s[i-(m-1)] == '1'){
      count--;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M, K = map(int, input().split())
S = input()

count = S[:M-1].count('1')
ans = 0
for i in range(M-1, N):
  if S[i] == '1':
    count += 1
  if count < K:
    ans += 1
  if S[i-(M-1)] == '1':
    count -= 1

print(ans)