概要

高速道路の各区間の渋滞状況が与えられ、連続する渋滞区間の長さが \(K\) 以上の場合に緊急報告が発生するので、合計報告回数を求める問題です。

考察

問題の本質は、連続する渋滞区間（\(S_i = 1\) の連続部分）を検出し、その長さが閾値 \(K\) 以上かどうかを判定することです。素朴なアプローチとしては、すべての連続する渋滞区間を検出して長さを計算し、\(K\) 以上かどうかを判定すれば十分です。

この問題は、入力サイズが最大 \(2 \times 10^5\) と大きいため、効率的なアルゴリズムが必要です。しかし、連続する渋滞区間を一度だけ走査すればよいので、線形時間で処理できます。

アルゴリズム

1. 入力から \(N\), \(K\), 各区間の状態リスト \(S\) を読み取る
2. 現在の連続渋滞区間の長さを保持する変数 current_length と、報告回数を保持する変数 report_count を初期化
3. 各区間を順番に走査：
   • 渋滞区間（\(S_i = 1\)）の場合：current_length を1増加
   • 通常区間（\(S_i = 0\)）の場合：現在の連続渋滞区間の長さが \(K\) 以上なら報告回数を1増加し、current_length をリセット
4. 走査終了後、最後の区間が渋滞で終わっている場合に備え、残っている current_length が \(K\) 以上かチェック
5. 報告回数を出力

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 渋滞区間が連続して終わったとき（\(S_i = 0\) に出会ったとき）にのみ報告判定を行う

• 最後の区間まで渋滞が続く場合があるので、ループ終了後に残りの長さをチェックする必要がある

• 入力の読み取りは一度に行い、リストとして保持することで効率的に処理できる

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    s_list = list(map(int, data[2:2+n]))
    
    count = 0
    current_length = 0
    report_count = 0
    
    for i in range(n):
        if s_list[i] == 1:
            current_length += 1
        else:
            if current_length >= k:
                report_count += 1
            current_length = 0
    
    if current_length >= k:
        report_count += 1
        
    print(report_count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。