概要

受験生の得点データから、指定された得点範囲内にある合格者のうち、得点が最も高く、かつ出席番号が最も小さい生徒の番号を求めます。

考察

この問題では、各生徒の得点が与えられ、ある範囲 \([L, R]\) 内にある得点の生徒が「合格」となります。
合格した生徒の中から「最も高い得点」を持つ生徒を見つけ、その出席番号を出力します。
もし、同じ最高得点の生徒が複数いる場合、出席番号が最も小さいものを選ぶ必要があります。
また、誰も合格していない場合は -1 を出力します。

素朴な方法としては、全生徒を見て、合格者をリストアップし、その中で得点最大・出席番号最小の者を選ぶことが考えられます。
しかし、この問題では生徒数 \(N\) が最大で \(2 \times 10^5\) なので、効率的に処理する必要があります。幸い、得点の範囲は \(0\) から \(100\) と非常に小さいので、得点ごとに生徒を管理するなど、別の工夫も可能ですが、単純な線形探索でも十分間に合います。

この解法では、全員を一度だけ見て、条件を満たす生徒の中で、現時点で最も良い候補を常に更新していけば良いです。
具体的には、合格者の得点が現在の最大得点より大きければ更新し、同じ得点なら出席番号が小さい方を選ぶようにします。

アルゴリズム

1. 入力から生徒数 \(N\) と合格範囲 \([L, R]\)、各生徒の得点 \(P_i\) を受け取る。
2. 最大得点 max_score を \(-1\)、結果の出席番号 result_index も \(-1\) で初期化する。
3. 各生徒について以下を行う：
   • 得点 \(P_i\) が \(L\) 以上 \(R\) 以下であれば合格者。
   • このとき、以下の条件で更新を行う：
     • 現在の得点が max_score より大きい場合 → 更新
     • 得点が同じで、出席番号が現在の result_index より小さい場合 → 更新
4. 全探索後、result_index を出力（誰も合格しなければ \(-1\) のまま）。

例

入力例：

5 60 90
50 80 70 90 80

• 合格者は出席番号2（80点）、3（70点）、4（90点）、5（80点）
• 最高得点は90点で、出席番号4が該当 → 出力：4

もう一つの例：

3 50 60
70 80 90

• 合格者なし → 出力：-1

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （得点リストの保持）

実装のポイント

• 出席番号は1-indexed（1から始まる）であることに注意（配列のインデックスは0からなので、i + 1を使う）
• 同じ得点の場合、出席番号が小さい方を選ぶ条件を正しく実装すること
• 合格者がいない場合に -1 を返すことを忘れない

ソースコード

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

max_score = -1
result_index = -1

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

print(result_index)

---

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