概要

合格点以上の生徒が連続して並んでいる区間（グループ）の個数を数える問題です。

考察

問題の言い換え

この問題は、数列の中で「条件を満たす要素が連続している区間」が何個あるかを数える問題です。

具体例で理解する

例えば、\(N=7\)、\(K=60\)、点数が [80, 70, 50, 90, 85, 40, 75] の場合を考えます。

• 生徒1: 80点 ≥ 60 → 合格 ✓
• 生徒2: 70点 ≥ 60 → 合格 ✓
• 生徒3: 50点 < 60 → 不合格
• 生徒4: 90点 ≥ 60 → 合格 ✓
• 生徒5: 85点 ≥ 60 → 合格 ✓
• 生徒6: 40点 < 60 → 不合格
• 生徒7: 75点 ≥ 60 → 合格 ✓

合格者を ○、不合格者を × で表すと：○○×○○×○

連続する合格者のグループは： 1. 生徒1, 2（1つ目のグループ） 2. 生徒4, 5（2つ目のグループ） 3. 生徒7（3つ目のグループ）

よって、表彰式は 3回 必要です。

重要な気づき

新しいグループが始まるのは、「直前が不合格（またはグループ外）で、今回が合格」 のときだけです。この「グループの開始点」を数えればよいのです。

アルゴリズム

1. 変数 count（グループ数）を 0 に初期化
2. 変数 in_group（現在グループ内にいるか）を False に初期化
3. 各生徒を順番に見ていく：
   • 合格の場合（\(A_i \geq K\)）：
     • まだグループ内にいなければ（in_group = False）、新しいグループが始まるので count を 1 増やす
     • in_group = True にする
   • 不合格の場合（\(A_i < K\)）：
     • in_group = False にする（グループが途切れる）
4. 最終的な count が答え

この方法は、配列を1回走査するだけで済むため効率的です。

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(N)\)（入力の配列を格納する分。追加の変数は \(O(1)\)）

実装のポイント

1. フラグ変数の活用: in_group という真偽値変数を使うことで、「現在、連続する合格者の区間内にいるかどうか」を管理できます。

2. グループの開始を検知: not in_group かつ A[i] >= K のときだけカウントを増やすことで、グループの開始点だけを正確に数えられます。

3. 別解: 「合格」を 1、「不合格」を 0 に変換した後、隣り合う要素で「0 → 1」に変化する回数を数える方法もあります。これも本質的には同じアルゴリズムです。

   ソースコード

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

count = 0
in_group = False

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

print(count)

---

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