概要

出席番号 1 番の生徒を暫定的な委員長とし、それ以外の生徒（出席番号 2 番以降）の中に、現在の委員長よりもリーダーシップ点数が高い人がいるかを探す問題です。条件を満たす生徒が複数いる場合は、点数が最も高く、かつ出席番号が最も小さい生徒を選出します。

考察

この問題を解くためには、全生徒の点数を順番に確認していく必要があります。

1. 比較の基準: まず、基準となる出席番号 1 番の生徒の点数 \(A_1\) を保持しておきます。
2. 候補の絞り込み: 出席番号 \(2, 3, \dots, N\) の生徒を一人ずつ見ていき、「点数が \(A_1\) より大きい」生徒だけを候補として考えます。
3. 最善の候補の更新: 候補の中で「最も点数が高い」生徒を探します。ここで重要なのは、同じ点数の生徒が複数いた場合にどうするかという点です。
   • ルールには「同じ点数なら出席番号が小さい方を選ぶ」とあります。
   • 出席番号が小さい順（\(2\) から \(N\)）に調べていく場合、「これまでに記録した最大スコアを更新したときだけ」新しい生徒の情報を保存するようにすれば、自然と同じ点数のときは最初に見つけた（出席番号が小さい）生徒が保持されます。

\(N\) が最大 \(2 \times 10^5\) と大きいため、二重ループなどを使わず、一度の走査（ループ 1 回）で答えを求める \(O(N)\) のアルゴリズムが必要です。

アルゴリズム

以下の手順で処理を行います。

1. 出席番号 1 番の点数 \(A_1\) を変数（例：a1）に格納します。
2. 「これまでの最大スコア」を保持する変数 max_found_score を \(-1\) で、「その生徒の出席番号」を保持する変数 best_id を \(-1\) で初期化します。
3. 出席番号 \(i = 2, 3, \dots, N\) について、以下の処理を繰り返します。
   • もし \(A_i > A_1\) かつ \(A_i > max_found_score\) ならば：
     • max_found_score を \(A_i\) に更新する。
     • best_id を \(i\) に更新する。
4. 最終的な best_id を出力します。一度も更新されなかった場合は初期値の \(-1\) がそのまま出力されます。

計算量

• 時間計算量: \(O(N)\) 生徒の人数 \(N\) に対して、一度だけループを回して点数を確認するため、生徒数に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\) 入力されたすべての点数をリストに格納して保持するため、メモリは \(N\) に比例して消費されます。

実装のポイント

• 高速な入出力: Pythonで \(N=2 \times 10^5\) 程度の入力を扱う場合、input() を繰り返すと時間がかかることがあります。sys.stdin.read().split() を使うことで、すべての入力を一括で読み込み、高速に処理することができます。

• 更新条件の不等号: score > max_found_score と「より大きい（真に大きい）」比較演算子を使うことで、点数が同じ場合には best_id が更新されないようにしています。これにより、「点数が同じなら出席番号が最小の生徒」という条件を簡単に満たすことができます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # 大量の入力を高速に処理するために sys.stdin.read().split() を使用します。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 生徒の人数 N を取得します。
    n = int(data[0])
    
    # 出席番号 1 の生徒（現在の委員長）のリーダーシップ点数 A1 を取得します。
    a1 = int(data[1])
    
    # 新しい委員長候補の出席番号と、その中での最大スコアを初期化します。
    best_id = -1
    max_found_score = -1
    
    # 出席番号 2 以降の生徒を順番に確認します。
    # ループの i は 1 から N-1 まで動き、data[i+1] が出席番号 i+1 の生徒の点数に対応します。
    for i in range(1, n):
        score = int(data[i + 1])
        
        # ルール1: 現在の委員長 A1 よりもリーダーシップ点数が真に大きいか確認します。
        if score > a1:
            # その中で最もリーダーシップ点数が高い生徒を選びます。
            # 既に記録されている最大値よりも大きい場合のみ更新することで、
            # 同じ点数の場合は「出席番号が最も小さい生徒」が保持されます。
            if score > max_found_score:
                max_found_score = score
                best_id = i + 1
                
    # 委員長が変更された場合はその出席番号を、変更がない場合は -1 を出力します。
    print(best_id)

if __name__ == "__main__":
    solve()

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