概要

0と1からなる数列において、1が連続するかたまり（ラン）のうち、長さが \(K\) 以上であるものの個数を数える問題です。

考察

この問題のポイントは「連続して渋滞している区間のかたまり」を正しく識別することです。

例えば、\(N = 10\), \(K = 3\) で状態が 1 1 1 0 1 1 0 1 1 1 の場合を考えます。

区間:  1 2 3 4 5 6 7 8 9 10
状態:  1 1 1 0 1 1 0 1 1 1
       -----   ---   -----
       長さ3   長さ2  長さ3

• 最初のかたまり：区間1〜3で長さ3 → \(K = 3\) 以上なので緊急報告 1回
• 次のかたまり：区間5〜6で長さ2 → \(K = 3\) 未満なので報告なし
• 最後のかたまり：区間8〜10で長さ3 → \(K = 3\) 以上なので緊急報告 1回

合計 2回 となります。

素朴に「各かたまりを探して長さを記録する」という方針で十分です。配列を1回走査するだけで解けるため、特別な高速化は不要です。

アルゴリズム

配列を左から右へ1回走査し、連続する1の個数をカウンタ count で管理します。

1. count = 0（現在の連続する1の長さ）、result = 0（緊急報告の回数）で初期化する。
2. 各区間 \(i\) を順に見る：
   • \(S_i = 1\) なら count を1増やす。
   • \(S_i = 0\) なら、そこでかたまりが途切れる。途切れる前の count が \(K\) 以上であれば result を1増やす。その後 count を0にリセットする。
3. ループ終了後、最後のかたまりが配列の末尾まで続いている可能性があるので、改めて count >= K を確認し、条件を満たせば result を1増やす。
4. result を出力する。

なぜループ後にもう一度チェックが必要か？

count のリセットと判定は \(S_i = 0\) に遭遇したときに行われます。しかし配列の末尾が1で終わる場合、最後のかたまりに対して \(S_i = 0\) が現れないため、ループ内では判定されません。そのためループ後に追加のチェックが必要です。

計算量

• 時間計算量: \(O(N)\) — 配列を1回走査するだけ
• 空間計算量: \(O(N)\) — 入力の配列を保持する分（走査自体は \(O(1)\) の変数のみ）

実装のポイント

• ループ後の最終チェックを忘れない: 配列が1で終わる場合、最後の連続かたまりがループ内で処理されないため、ループ後に if count >= K のチェックが必須です。これを忘れるとWAになります。

• カウンタのリセットタイミング: \(S_i = 0\) を見つけたときに判定 → リセットの順で行います。順序を間違えると正しく判定できません。

  ソースコード

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

count = 0
result = 0
for i in range(N):
    if S[i] == 1:
        count += 1
    else:
        if count >= K:
            result += 1
        count = 0
if count >= K:
    result += 1

print(result)

---

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