概要

\(N\) 日間の天気の記録から、連続する \(M\) 日間の区間をすべて取り出し、その中で晴れ（1）の日数が \(K\) 日未満である「悪天候期間」がいくつあるかを数える問題です。

考察

まず、素朴な方法（愚直な実装）を考えてみます。 \(N-M+1\) 個あるすべての区間について、毎回 \(M\) 日間の晴れの日数を数えると、計算量は \(O((N-M) \times M)\) となります。今回の制約では \(N\) が最大 \(10^6\) であるため、最悪の場合（\(M\) が \(N/2\) 程度のときなど）に計算回数が \(10^{11}\) を超えてしまい、実行制限時間に間に合いません。

この問題を効率よく解くためには、「ある区間の合計値を高速に求める」手法が必要です。 連続する範囲の和を求める際、累積和（Prefix Sum）という手法を用いることで、どの区間の和も \(O(1)\) で計算できるようになります。

アルゴリズム

以下の手順で解を進めます。

1. 数値への変換: 文字列 \(S\) の 1 を数値の \(1\)、0 を数値の \(0\) とみなします。
2. 累積和の構築: 配列 \(P\) を作成します。ここで \(P[i]\) は「最初の \(i\) 日間における晴れの日数の合計」とします。
   • \(P[0] = 0\)
   • \(P[i] = P[i-1] + (i \text{日目の天気})\) これにより、任意の区間 \([i, i+M-1]\)（\(i\) 日目から \(M\) 日間）に含まれる晴れの日数は、\(P[i+M] - P[i]\) という引き算ひとつで求められます。
3. 区間の判定: \(i = 0\) から \(N-M\) まで順に動かし、各区間の晴れの日数 \(P[i+M] - P[i]\) が \(K\) 未満であるかを判定し、条件を満たすものをカウントします。

計算量

• 時間計算量: \(O(N)\) 累積和の作成に \(O(N)\)、各区間の判定（計 \(N-M+1\) 回）に \(O(N)\) かかるため、全体で \(O(N)\) です。\(N=10^6\) でも十分に高速に動作します。
• 空間計算量: \(O(N)\) 長さ \(N+1\) の累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonではデータ量が多い場合、input() よりも sys.stdin.read().split() などを用いると入力が高速になります。

• 累積和の計算: itertools.accumulate を使うと、累積和を簡潔かつ高速に計算できます。

• イテレータの活用: islice と zip を組み合わせることで、リストのコピー（スライス）を作らずにメモリ効率よく各区間の差分を計算しています。これにより、大きな \(N\) に対しても省メモリで動作します。

  ソースコード

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()

---

この解説は gemini-3-flash-thinking によって生成されました。