概要

\(N\) 人の生徒の得点 \(P_i\) の中から、指定された範囲 \([L, R]\) に含まれる得点を持つ生徒のうち、最も高い得点を取った生徒の出席番号を求める問題です。

考察

この問題を解くためには、以下の3つの条件をすべて満たす生徒を見つける必要があります。

1. 得点 \(P_i\) が \(L \le P_i \le R\) を満たしている。
2. 条件1を満たす生徒の中で、得点 \(P_i\) が最大である。
3. 条件2を満たす生徒が複数いる場合、出席番号 \(i\) が最小である。

制約を確認すると、生徒数 \(N\) は最大で \(2 \times 10^5\) です。一人ずつの得点を順番にチェックしていく「線形探索」を行えば、合計 \(N\) 回の判定で済むため、制限時間内に十分間に合わせることができます。

「得点が最大、かつ出席番号が最小」という条件を効率的に処理するには、前から順番に生徒を見ていき、「これまでに見た合格者の中での最高得点」を更新できたときだけ、出席番号を記録するのがポイントです。

アルゴリズム

以下の手順で解を求めます。

1. 「現在の最大得点（max_score）」を -1、「その時の出席番号（ans_id）」を -1 で初期化します。
2. \(i = 1\) から \(N\) まで、各生徒の得点 \(P_i\) を順番に確認します。
   • もし \(L \le P_i \le R\) かつ \(P_i > \text{max\_score}\) であれば：
     • max_score を \(P_i\) で更新する。
     • ans_id を現在の出席番号 \(i\) で更新する。
3. すべての生徒を確認し終えた後、ans_id を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 人の得点を一度ずつ確認するため、生徒数に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 全員の得点をリストに格納して保持する場合、入力サイズに応じたメモリを使用します。（逐次読み込みを行う場合は \(O(1)\) に抑えることも可能です）

実装のポイント

• 更新の条件: score > max_score というように、不等号にイコールを含めない（厳密に大きい場合のみ更新する）ことで、得点が同じ場合には「最初に見つかった（＝出席番号が小さい）生徒」が優先的に保持されます。

• 初期値: 合格者が一人もいない場合に -1 を出力する必要があるため、ans_id の初期値を -1 に設定しておくと、条件分岐を増やすことなくそのまま出力できてスマートです。

• 高速な入出力: Pythonの場合、データ量が多い（\(2 \times 10^5\) 程度）ときは sys.stdin.read().split() などを使って一括で入力を取得すると実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N, L, R を取得
    N = int(input_data[0])
    L = int(input_data[1])
    R = int(input_data[2])
    
    # 生徒の得点リストを取得
    # P_i は input_data[3] から input_data[3 + N - 1] まで
    scores = input_data[3:]
    
    max_score = -1
    ans_id = -1
    
    # 各生徒の得点を順番に確認
    for i in range(N):
        score = int(scores[i])
        
        # 合格範囲内（L以上R以下）か判定
        if L <= score <= R:
            # 現在の最大得点よりも高い場合のみ更新
            # これにより、同じ得点の場合は出席番号が小さい方が優先される
            if score > max_score:
                max_score = score
                ans_id = i + 1
                
    # 結果を出力（合格者がいない場合は初期値の -1 が出力される）
    print(ans_id)

if __name__ == "__main__":
    solve()

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