概要

点数が \(K\) 以上の生徒（合格者）が並びの中で「連続している区間」の個数を数え、それが必要な表彰式の回数になります。

考察

表彰は「出席番号が連続している合格者のまとまり」ごとに 1 回で済みます。つまり求めたいのは、配列 \(A_1,\dots,A_N\) を左から見たときに

• 合格（\(A_i \ge K\)）が続く部分を 1 つの区間とみなす
• その区間がいくつあるか

という「連続する真（True）の区間数」です。

たとえば \(K=60\)、判定結果（合格なら T）が
F T T F T F T T T なら、連続する T の塊は 3 個なので答えは 3 です。

素朴に「合格者の全ての区間を列挙する」などをすると \(O(N^2)\) になり得て、\(N \le 2\times 10^5\) では間に合いません。
しかしこの問題は、各位置 \(i\) が「新しい合格区間の開始点かどうか」だけ分かれば十分で、1 回の走査で数えられます。

重要な観察は以下です：

• 位置 \(i\) が合格で、かつ直前 \(i-1\) が不合格（または \(i=1\)）なら、そこは新しい合格区間の開始
• それ以外（合格が続いているだけ）なら表彰式の回数は増えない

アルゴリズム

1. ans = 0（表彰式回数）、prev_ok = False（直前が合格だったか）を用意する。
2. \(i=1\) から \(N\) まで順に点数 \(A_i\) を読む。
3. ok = (A_i >= K) とする。
4. ok が真、かつ prev_ok が偽なら、ここは「合格区間の開始」なので ans += 1。
5. prev_ok = ok に更新して次へ進む。
6. 最後に ans を出力する。

これで合格区間の開始回数＝合格区間数＝表彰式回数を数えられます。

計算量

• 時間計算量: \(O(N)\)（1 回走査するだけ）
• 空間計算量: \(O(1)\)（追加で持つのは定数個の変数のみ）

実装のポイント

• 「合格で、直前が不合格なら +1」という条件が本質です（境界 \(i=1\) も prev_ok=False で自然に扱える）。

• 入力が大きいので、Python では sys.stdin.buffer.read() のような高速入力を使うと安全です。

• 合格者が 1 人もいない場合も、この数え方なら自然に ans=0 のままになります。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    K = int(next(it))
    ans = 0
    prev_ok = False
    for _ in range(N):
        a = int(next(it))
        ok = a >= K
        if ok and not prev_ok:
            ans += 1
        prev_ok = ok
    print(ans)

if __name__ == "__main__":
    main()

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