概要

長さ \(N\) の天気の記録から、連続する \(M\) 日間の区間をすべて調べ、晴れの日数が \(K\) 日未満である「悪天候期間」の個数を数える問題です。スライディングウィンドウ（尺取り法）を用いて効率的に解きます。

考察

素朴なアプローチとその問題点

最も単純な方法は、\(N - M + 1\) 個の各区間について、毎回 \(M\) 日分の晴れの日数を数えることです。この場合、計算量は \(O(N \times M)\) となります。

\(N\) が最大 \(10^6\)、\(M\) も最大 \(10^6\) になりうるため、最悪 \(10^{12}\) 回の操作が必要になり、TLE（時間超過） になります。

重要な気づき

隣り合う2つの区間を比較すると、大部分が重なっていることに気づきます。

例えば \(S = \) 110100、\(M = 3\) の場合： - 区間1: 110（1日目〜3日目）→ 晴れ2日 - 区間2: 101（2日目〜4日目）→ 晴れ2日 - 区間3: 010（3日目〜5日目）→ 晴れ1日 - 区間4: 100（4日目〜6日目）→ 晴れ1日

区間1 → 区間2 への移動では、左端の1日目が抜け、右端の4日目が加わるだけです。つまり、毎回 \(M\) 日分を数え直す必要はなく、差分（抜ける1要素と加わる1要素）だけ更新すれば十分です。

アルゴリズム

スライディングウィンドウ（尺取り法） を使います。

1. 初期ウィンドウの計算: 1日目から \(M\) 日目までの晴れの日数 count を数える。
2. 判定: count \(< K\) なら結果を1増やす。
3. ウィンドウをスライド: \(i = 1, 2, \ldots, N - M\) について以下を繰り返す：
   • 左端を除去: \(S[i-1]\) が 1 なら count を1減らす。
   • 右端を追加: \(S[i+M-1]\) が 1 なら count を1増やす。
   • 判定: count \(< K\) なら結果を1増やす。
4. 最終的な結果を出力する。

上の例（\(S = \) 110100、\(M = 3\)、\(K = 2\)）で確認すると： - 初期: 110 → count=2、\(2 < 2\) は偽 - スライド1: 1を除去、0を追加 → count=1+0=1…ではなく、1除去で count=1、1追加で count=2 → 101 count=2、偽 - スライド2: 1除去で count=1、0追加で count=1 → 010 count=1、\(1 < 2\) で真 → result=1 - スライド3: 0除去で count=1、0追加で count=1 → 100 count=1、\(1 < 2\) で真 → result=2

答えは 2 となります。

計算量

• 時間計算量: \(O(N)\) — 初期ウィンドウの計算に \(O(M)\)、スライドに \(O(N - M)\) で、合計 \(O(N)\)
• 空間計算量: \(O(N)\) — 文字列 \(S\) の保持に必要

実装のポイント

• sys.stdin.buffer.read() を使って高速に入力を読み込んでいます。\(N\) が最大 \(10^6\) と大きいため、Python では入力の高速化が重要です。

• ウィンドウ内の晴れの日数を変数 count 1つで管理し、スライドのたびに差分更新するだけなので、追加の配列は不要です。

• 累積和を使う方法でも \(O(N)\) で解けますが、スライディングウィンドウの方がメモリ効率が良く、実装もシンプルです。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    S = input_data[3].decode()
    
    # Calculate sum of first window
    count = 0
    for i in range(M):
        if S[i] == '1':
            count += 1
    
    result = 0
    if count < K:
        result += 1
    
    for i in range(1, N - M + 1):
        # Remove element going out of window
        if S[i - 1] == '1':
            count -= 1
        # Add element coming into window
        if S[i + M - 1] == '1':
            count += 1
        if count < K:
            result += 1
    
    print(result)

main()

---

この解説は claude4.6opus-thinking によって生成されました。