概要

\(0/1\) で表された区間列を左から見ていき、連続する \(1\) のかたまり（連続区間）の長さが \(K\) 以上のものが何個あるかを数える問題です。

考察

重要なのは「緊急報告は、連続する渋滞区間（極大な連続する \(1\)）ごとに高々 1 回だけ発生する」という点です。
つまり、各区間を個別に数えるのではなく、連続する \(1\) のかたまりの長さだけ分かれば十分です。

例えば \(K=3\) で - \(S = [1,1,1,1]\) は長さ \(4\) のかたまりが 1 つなので報告は \(1\) 回 - \(S = [1,1,0,1,1,1,0]\) は長さ \(2\) と \(3\) のかたまりなので報告は \(1\) 回

素朴に「各位置から右へ伸ばして長さを調べる」などをすると、最悪で同じ区間を何度も見てしまい \(O(N^2)\) になり、\(N \le 2\times 10^5\) では間に合いません。
そこで、左から 1 回走査しながら「今どれだけ \(1\) が連続しているか」を数えることで、重複なく処理できます。

アルゴリズム

左から順に見て、連続する \(1\) の長さ run を管理します。

1. ans = 0, run = 0 で初期化
2. 各 \(S_i\) について
   • \(S_i = 1\) なら run += 1
   • \(S_i = 0\) なら、ここで直前の \(1\) のかたまりが終わったので
     
     • run >= K なら ans += 1
     • run = 0 に戻す
3. 最後が \(1\) で終わる場合に備えて、走査後にも同様に run >= K を判定して ans に加える
4. ans を出力

この方法で、各「極大な連続する \(1\)」をちょうど 1 回だけ判定できます。

計算量

• 時間計算量: \(O(N)\)（1 回の走査のみ）
• 空間計算量: \(O(1)\)（ans と run など定数個の変数のみ）

実装のポイント

• かたまりの判定は「\(0\) に遭遇した瞬間」に行うと簡単です。

• 配列の末尾が \(1\) の場合、最後のかたまりが未処理で終わるので、ループ後にもう一度判定を入れるのを忘れないようにします。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    S = data[2:]

    ans = 0
    run = 0
    for x in S:
        if x == 1:
            run += 1
        else:
            if run >= K:
                ans += 1
            run = 0
    if run >= K:
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

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