概要

\(N\) 個の区間からなる道路において、連続する渋滞区間（値が \(1\) の区間）の「かたまり」を特定し、その長さが \(K\) 以上であるものがいくつあるかを数える問題です。

考察

この問題を解くための鍵は、「渋滞がどこで始まり、どこで終わるか」を正確に把握することです。

例えば、\(K=3\) で状態が 1 1 1 0 1 1 1 1 0 1 の場合を考えます。 1. 最初に 1 が \(3\) つ連続しています。長さは \(3\) なので、これは \(K\) 以上であり、緊急報告の対象です。 2. 次に 0 が現れるので、一旦カウントをリセットします。 3. その後に 1 が \(4\) つ連続しています。長さは \(4\) なので、これも \(K\) 以上であり、緊急報告の対象です。 4. 最後に 1 が \(1\) つありますが、長さ \(1\) は \(K\) 未満なので報告しません。

このように、リストを先頭から順に見ていき、「\(1\) が続いている間はカウントを増やし、\(0\) が出たらカウントを判定してリセットする」という処理を繰り返せばよいことが分かります。

注意点として、「最後の区間が \(1\) だった場合」の処理を忘れないようにする必要があります。ループが終了した直後に、残っているカウントが \(K\) 以上かどうかをチェックしなければなりません。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 緊急報告の回数（emergency_reports）と、現在連続している渋滞の数（current_consecutive_count）を \(0\) で初期化します。
2. 各区間の状態 \(S_i\) を \(i=1\) から \(N\) まで順に確認します。
   • \(S_i = 1\) の場合：current_consecutive_count を \(1\) 増やします。
   • \(S_i = 0\) の場合：
     • もし current_consecutive_count が \(K\) 以上なら、emergency_reports を \(1\) 増やします。
     • current_consecutive_count を \(0\) にリセットします。
3. すべての確認が終わった後、最後に current_consecutive_count が \(K\) 以上であれば、emergency_reports を \(1\) 増やします。
4. emergency_reports を出力します。

計算量

• 時間計算量: \(O(N)\)
  • リストを端から端まで \(1\) 回走査するだけなので、区間の数 \(N\) に対して線形時間で処理が完了します。\(N \le 2 \times 10^5\) という制約下でも十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の要素をリストとして保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• データの読み込み: \(N\) が大きいため、sys.stdin.read().split() を使うことで高速に入力を取得しています。

• ループ後の処理: 道路の終端（区間 \(N\)）が渋滞（\(1\)）だった場合、ループ内では 0 に出会わないため報告の判定が行われません。そのため、ループの外側で最後の判定を行う必要があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してトークンのリストを作成します。
    # これにより、改行やスペースに関わらずデータを取得できます。
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 区間の数 N と、緊急報告の閾値 K を取得します。
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各区間の状態 S_1, ..., S_N を取得します。
    # 文字列として比較するため、intへの変換は行わずそのまま扱います。
    s_list = input_data[2:2+n]
    
    emergency_reports = 0
    current_consecutive_count = 0
    
    # 各区間の状態を順番に確認します。
    for s in s_list:
        if s == '1':
            # 渋滞中の場合、現在の連続カウントを増やします。
            current_consecutive_count += 1
        else:
            # 通常の状態に戻った場合、それまでの連続渋滞区間（かたまり）を処理します。
            if current_consecutive_count >= k:
                # かたまりの長さが K 以上であれば、緊急報告を 1 回行います。
                emergency_reports += 1
            # カウントをリセットします。
            current_consecutive_count = 0
    
    # 全区間の確認が終わった後、最後の区間まで渋滞が続いていた場合の処理を行います。
    if current_consecutive_count >= k:
        emergency_reports += 1
        
    # 結果を出力します。
    print(emergency_reports)

if __name__ == '__main__':
    solve()

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