概要

\(N\) 人の生徒の中から、得点が \(L\) 点以上 \(R\) 点以下の合格者を見つけ、その中で最高得点を取った生徒の出席番号を求める問題です。

考察

この問題を解くために、以下の点に注目します。

問題の整理

1. 合格条件: 得点が \(L\) 以上 \(R\) 以下
2. 求めるもの: 合格者の中で最高得点の生徒の出席番号
3. 同点の場合: 出席番号が最も小さい生徒を選ぶ
4. 合格者がいない場合: -1 を出力

素朴なアプローチで十分か？

\(N\) は最大 \(2 \times 10^5\) です。全生徒を1回ずつ見て判定するだけなら \(O(N)\) で済むため、計算量の問題は発生しません。

同点の場合の処理

「最高得点の生徒が複数いる場合は出席番号が最も小さい生徒」という条件があります。これは、先頭から順に見ていき、より高い得点が見つかったときだけ更新するようにすれば自然と満たされます。

例えば、得点が [70, 80, 80, 60] で \(L=60\), \(R=100\) の場合： - 生徒1（70点）: 現在の最高 → 更新 - 生徒2（80点）: 70より高い → 更新 - 生徒3（80点）: 80と同じ → 更新しない（これにより出席番号2が保持される） - 生徒4（60点）: 80より低い → 更新しない

結果として出席番号 2 が答えになります。

アルゴリズム

1. 変数 max_score を \(-1\)（まだ合格者がいない状態）、result を \(-1\)（答えがない状態）で初期化
2. 生徒を出席番号順（\(i = 0, 1, 2, \ldots, N-1\)）に走査
3. 各生徒について：
   • 得点 \(P_i\) が \(L\) 以上 \(R\) 以下（合格条件を満たす）かつ
   • 得点 \(P_i\) が現在の max_score より大きい場合
   • → max_score を \(P_i\) に更新し、result を \(i + 1\)（出席番号は1始まり）に更新
4. 最終的な result を出力

計算量

• 時間計算量: \(O(N)\)
  • 全生徒を1回ずつ走査するため
• 空間計算量: \(O(N)\)
  • 得点リスト \(P\) を保存するため

実装のポイント

1. 出席番号は1始まり: 配列のインデックスは0から始まるため、答えを出力する際は i + 1 とする必要があります。

2. 更新条件は「より大きい」: P[i] > max_score という条件にすることで、同点の場合は先に見つかった（出席番号が小さい）生徒が保持されます。もし >= にしてしまうと、同点の場合に後の生徒で上書きされてしまいます。

3. 初期値の設定: max_score = -1 としておくことで、得点が0点の合格者も正しく検出できます（得点は \(0\) 以上 \(100\) 以下のため、\(-1\) は取り得ない値）。

   ソースコード

N, L, R = map(int, input().split())
P = list(map(int, input().split()))

max_score = -1
result = -1

for i in range(N):
    if L <= P[i] <= R:
        if P[i] > max_score:
            max_score = P[i]
            result = i + 1

print(result)

---

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