概要

長さ \(M\) の連続区間を左から順に見て、各区間の 1（晴れ）の日数が \(K\) 未満かどうかを数える問題です。
毎回区間を作り直さず、スライドしながら晴れ日数を更新すると高速に解けます。

考察

重要な観察は、「隣り合う区間はほとんど同じ」という点です。

例えば区間 \([i, i+M-1]\) から \([i+1, i+M]\) へ移るとき、

• 先頭の \(S[i]\) が区間から抜ける
• 新しい末尾の \(S[i+M]\) が区間に入る

だけが変化します。
つまり、前の区間の晴れ日数が分かっていれば、次の区間の晴れ日数は定数時間で更新できます。

---

素朴に「各区間ごとに \(M\) 文字を数える」と、

• 区間数は \(N-M+1\)
• 各区間で \(O(M)\)

なので合計 \(O((N-M+1)M)\)、最悪で \(O(NM)\) になり、\(N \le 10^6\) では間に合いません。

そこで、最初の1区間だけ数えて、その後は1文字出して1文字入れる更新（スライディングウィンドウ）を使えば、全体を \(O(N)\) で処理できます。

アルゴリズム

1. 最初の区間 S[0:M] の 1 の個数を current とする。
   
2. current < K なら答え ans を 1 増やす。
3. 右端を1つずつ進める（i = M ... N-1）:
   • 区間から抜ける文字は S[i-M]。これが '1' なら current -= 1
   • 区間に入る文字は S[i]。これが '1' なら current += 1
   • 更新後、current < K なら ans += 1
4. ans を出力する。

この処理で、すべての長さ \(M\) の区間を漏れなく1回ずつ判定できます。

計算量

• 時間計算量: \(O(N)\)
  
• 空間計算量: \(O(1)\)（入力文字列を除く）

実装のポイント

• Pythonでは区間の最初の個数を S[:M].count('1') で簡潔に求められます。

• インデックスの対応に注意：

  • 抜ける文字: S[i - M]
  • 入る文字: S[i]

• 制約が大きいので input() より sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    S = input().strip()

    current = S[:M].count('1')
    ans = 1 if current < K else 0

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

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。