概要

連続して渋滞している区間のかたまりのうち、長さが \(K\) 以上であるものの個数を求めます。

考察

この問題では、「連続して \(1\) が続く区間」（つまり渋滞区間）を一つずつ見つけて、その長さが \(K\) 以上かどうかを判定する必要があります。

素朴な方法として、各インデックスから始まる連続する \(1\) を毎回数えると、最悪の場合で同じ区間を何度も見ることになり、時間計算量が \(O(N^2)\) となってしまいます。特に \(N\) が最大 \(2 \times 10^5\) となるので、これは TLE（時間超過）になります。

そこで、「連続する \(1\) のかたまり」を一度だけ走査する方法を考えます。つまり、\(S_i = 1\) が始まった時点で、そこから連続する \(1\) がどこまで続くかを調べ、その長さを計算します。これにより、全体を高々一度だけ走査すれば良く、効率的に処理できます。

例えば入力が以下のような場合：

N = 10, K = 3
S = [0, 1, 1, 1, 0, 1, 1, 0, 1, 1]

このとき、連続する \(1\) のかたまりは以下の3つです： - 区間2〜4：長さ3 → 緊急報告 - 区間6〜7：長さ2 → 通常対応 - 区間9〜10：長さ2 → 通常対応

したがって、緊急報告は1回だけ発生します。

このように、連続する区間をまとめて扱うことで無駄を省きます。

アルゴリズム

コードでは、while ループを使って配列 S を前から走査しています。

1. 現在位置 i が 1（渋滞中）であれば、その連続の始まりとします。
2. そこからさらに while ループで S[i] == 1 が続く限り i を進めます。
3. 最終的に、始まりのインデックス start から終わりのインデックスまでの長さ length = i - start を求めます。
4. この長さが \(K\) 以上であれば、緊急報告カウントを増やします。
5. S[i] == 0 の場合は単に次に進みます。

このようにして、すべての連続する渋滞区間を一度だけ見て、必要な判定を行います。

計算量

• 時間計算量: \(O(N)\)
  各要素に対して高々1回の操作しか行わないので、線形時間で処理可能です。
• 空間計算量: \(O(1)\)（入力を除く）
  追加の配列などを使わず、定数個の変数のみを使用しています。

実装のポイント

• インデックスの進行を慎重に管理すること（内側のループで i を進めていることに注意）
• start 変数を使って連続区間の開始位置を記録し、長さを正しく計算する
• else 節で S[i] == 0 のときは単に i += 1 するだけでOK

## ソースコード

```python
N, K = map(int, input().split())
S = list(map(int, input().split()))

count = 0
i = 0
while i < N:
    if S[i] == 1:
        start = i
        while i < N and S[i] == 1:
            i += 1
        length = i - start
        if length >= K:
            count += 1
    else:
        i += 1

print(count)

---

この解説は qwen3-coder-480b によって生成されました。