概要

出席番号順に並んだ生徒のテスト結果から、点数が合格点 \(K\) 以上の連続した区間の数を数える問題。

考察

この問題では、点数が合格点 \(K\) 以上である生徒を「合格者」と呼び、連続する合格者たちを1つのグループとして扱います。例えば、点数が \([60, 70, 40, 80, 90]\) で合格点が \(70\) の場合、合格者のインデックスは \(1, 3, 4\)（0-indexedなら）となりますが、連続しているのは \([3, 4]\) のみなので、グループ数は2になります。

このように、連続する区間の数を数えるには、その区間の開始点だけを検出すれば良いです。つまり、「前の生徒が不合格で、今の生徒が合格」になった瞬間に新しいグループが始まったと判断できます。

愚直に区間を探索してグループを数えると、最悪ケースで \(O(N^2)\) かかる可能性があり、制約 \(N \leq 2 \times 10^5\) に対しては時間内に解けません。しかし、上記のように「区間の開始タイミング」だけを見ることで、1回の走査で答えを求めることができます。

アルゴリズム

1. 生徒の点数リスト \(A\) を先頭から順に見ていきます。
2. 各生徒について、点数 \(A_i \geq K\) かどうかを判定します。
3. 「直前の生徒が不合格」かつ「現在の生徒が合格」であれば、新しい連続区間が始まったとみなしてカウントを増やします。
4. この判定のために、「現在連続区間に入っているか」を管理するフラグ in_streak を使います。
5. 最後にカウントされた値を出力します。

具体例

入力:

5 70
60 80 90 40 70

• 点数: [60, 80, 90, 40, 70]
• 合格者: x, o, o, x, o （o が合格）

連続区間は： - [80, 90] → 1グループ - [70] → 1グループ

合計2回の表彰式が必要です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力の配列を除く）

実装のポイント

• フラグ変数 in_streak を使うことで、連続区間の開始点を正確に捉えることができます。
• 最初の要素から順に処理するので、境界条件も特に気にしなくて大丈夫です。
• 合格者が全くいない場合でも、カウントは増えないので自然と答えが \(0\) になります。

## ソースコード

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

count = 0
in_streak = False

for i in range(N):
    if A[i] >= K:
        if not in_streak:
            count += 1
            in_streak = True
    else:
        in_streak = False

print(count)

---

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