概要

この問題は、与えられた \(N\) 個の点数のうち、合格点 \(K\) 以上の値が連続している区間（グループ）がいくつあるかを数える問題です。

考察

この問題を解く鍵は、「新しい表彰式のグループがいつ始まるか」を正確に捉えることです。

例えば、合格点を \(80\) 点としたとき、点数が \([90, 85, 50, 80, 40]\) と並んでいたとします。 1. 最初の \(90\) 点の人は合格です。ここで新しいグループが始まります（回数：1）。 2. 次の \(85\) 点の人も合格ですが、前の人も合格だったので、同じグループとして扱います（回数は増えません）。 3. 次の \(50\) 点の人は不合格です。ここで一旦グループが途切れます。 4. 次の \(80\) 点の人は合格です。前の人は不合格だったので、ここでまた新しいグループが始まります（回数：2）。 5. 最後の \(40\) 点の人は不合格です。

このように、「不合格者（または列の先頭）の後に、初めて合格者が現れた瞬間」にカウントを増やすことで、グループの総数を求めることができます。

アルゴリズム

「現在、合格者のグループの中にいるかどうか」を管理するフラグ（変数）を用意して、点数を先頭から順番に確認していきます。

1. 表彰式の回数を表す変数 count を \(0\) で初期化します。
2. 「現在グループの中にいるか」を表すフラグ in_group を False で初期化します。
3. 各生徒の点数 score について、以下の処理を繰り返します。
   • もし score が \(K\) 以上（合格）の場合：
     • まだグループの中にいなければ（in_group が False なら）、新しいグループの始まりなので count を \(1\) 増やし、in_group を True にします。
     • すでにグループの中なら、何もしません。
   • もし score が \(K\) 未満（不合格）の場合：
     • グループが途切れるため、in_group を False にします。
4. 最終的な count の値を出力します。

計算量

• 時間計算量: \(O(N)\) 生徒の人数 \(N\) に対して、点数のリストを最初から最後まで \(1\) 回走査するだけなので、非常に高速に動作します。
• 空間計算量: \(O(N)\) 入力をリストとして保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• フラグの切り替え: 合格点以上のときに「カウントしてフラグを立てる」、合格点未満のときに「フラグを倒す」というシンプルなロジックで実装できます。

• 大量の入力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力を受け取る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))

    count = 0
    in_group = False
    
    # 各生徒の点数を確認していく
    for score in a:
        if score >= k:
            # 合格点以上かつ、現在グループのカウント中でなければ新しいグループを開始
            if not in_group:
                count += 1
                in_group = True
        else:
            # 合格点未満なら、連続したグループが途切れたことを示す
            in_group = False
            
    # 結果を出力
    print(count)

if __name__ == "__main__":
    solve()

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