Overview

Given a record of weather over \(N\) days, we extract all contiguous intervals of \(M\) days and count how many of them are “bad weather periods” — intervals where the number of sunny days (1) is less than \(K\).

Analysis

First, let’s consider a naive approach (brute-force implementation). For all \(N-M+1\) intervals, if we count the number of sunny days over \(M\) days each time, the computational complexity becomes \(O((N-M) \times M)\). Given the constraints where \(N\) can be up to \(10^6\), in the worst case (such as when \(M\) is around \(N/2\)), the number of operations exceeds \(10^{11}\), which will not fit within the time limit.

To solve this problem efficiently, we need a technique for “quickly computing the sum of an interval.” When computing sums over contiguous ranges, by using a technique called Prefix Sum, we can calculate the sum of any interval in \(O(1)\).

Algorithm

We proceed with the following steps:

1. Conversion to numbers: Treat 1 in the string \(S\) as the number \(1\), and 0 as the number \(0\).
2. Building the prefix sum: Create an array \(P\), where \(P[i]\) represents “the total number of sunny days in the first \(i\) days.”
   • \(P[0] = 0\)
   • \(P[i] = P[i-1] + (\text{weather on day } i)\) With this, the number of sunny days in any interval \([i, i+M-1]\) (the \(M\) days starting from day \(i\)) can be obtained with a single subtraction: \(P[i+M] - P[i]\).
3. Evaluating each interval: Iterate \(i\) from \(0\) to \(N-M\), check whether the number of sunny days \(P[i+M] - P[i]\) in each interval is less than \(K\), and count the intervals that satisfy the condition.

Complexity

• Time complexity: \(O(N)\) Building the prefix sum takes \(O(N)\), and evaluating each interval (\(N-M+1\) times in total) takes \(O(N)\), so the overall complexity is \(O(N)\). This runs sufficiently fast even for \(N=10^6\).
• Space complexity: \(O(N)\) We use \(O(N)\) memory to store the prefix sum array of length \(N+1\).

Implementation Notes

• Fast I/O: In Python, when the data volume is large, using sys.stdin.read().split() instead of input() makes input faster.

• Prefix sum computation: Using itertools.accumulate allows for concise and fast prefix sum computation.

• Utilizing iterators: By combining islice and zip, we compute the difference for each interval without creating list copies (slices), achieving memory efficiency. This ensures low memory usage even for large \(N\).

  Source Code

import sys
from itertools import accumulate, islice

def main():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 日数, M: 確認する連続日数, K: 晴れの日数の基準
    n = int(input_data[0])
    m = int(input_data[1])
    k = int(input_data[2])
    # S: 天気を表す文字列 ('1'は晴れ、'0'は晴れ以外)
    s = input_data[3]
    
    # 累積和を計算して、ある期間内の晴れの日数を高速に求められるようにする
    # map(int, s) で '0'/'1' を数値の 0/1 に変換
    # accumulate(..., initial=0) により [0, s[0], s[0]+s[1], ..., s[0]+...+s[N-1]] というリストを作成
    # p[i] は最初の i 日間における晴れの日数の合計
    p = list(accumulate(map(int, s), initial=0))
    
    bad_weather_count = 0
    
    # i 日目から i+M-1 日目までの M 日間の区間の晴れの日数は p[i+M] - p[i] で求められる
    # zip と islice を使用して、p[M]-p[0], p[M+1]-p[1], ..., p[N]-p[N-M] を効率的に計算
    # zip は短い方のイテラブルに合わせて終了するため、ちょうど N-M+1 回ループする
    p_start = p
    p_end = islice(p, m, None)
    
    for val_end, val_start in zip(p_end, p_start):
        # 晴れの日数が K 日未満である場合、悪天候期間としてカウント
        if val_end - val_start < k:
            bad_weather_count += 1
            
    # 結果を出力
    sys.stdout.write(str(bad_weather_count) + '\n')

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3-flash-thinking.