概要

出席番号 \(1\) の生徒（現在の委員長）よりリーダーシップ点数が真に高い生徒がいるなら、その中で最も点数が高い（同点なら出席番号が最小の）生徒の番号を出力し、いなければ \(-1\) を出力する問題です。

考察

重要なのは、比較対象が「現在の委員長（出席番号 \(1\)）」の点数 \(A_1\) だけだという点です。
つまり「\(A_i > A_1\) を満たす生徒の中で最大の \(A_i\)（同点なら最小の \(i\)）」を探せばよいです。

このとき、全員を一度ずつ見るだけで十分です。
例えば \(A = [5, 6, 6, 4, 7]\) なら、基準は \(A_1 = 5\) で、\(5\) より大きいのは \(6,6,7\)。最大は \(7\) なので出席番号 \(5\) を出力します。
また \(A = [5, 6, 6, 4]\) なら最大は \(6\) で同点が複数いるため、出席番号が小さい \(2\) を出力します。

素朴に「条件を満たす生徒を全部集めてソートする」などでも解けますが、ソートは \(O(N \log N)\) かかり、今回は最大 \(2 \times 10^5\) なので間に合う場合も多いものの、不要な計算です。1回の走査で \(O(N)\) にできます。

アルゴリズム

1. 基準となる点数 \(base = A_1\) を持つ。
2. 変数 best_score（見つけた中での最高点）と best_idx（その出席番号）を用意し、未発見を表すために -1 で初期化する。
3. \(i = 2\) から \(N\) まで順に見る（0-index 実装なら for i in range(1, N)）。
   • もし \(A_i > base\) なら候補。
   • 候補の点数が best_score より大きければ更新。
   • 同点（\(A_i == best_score\)）なら、出席番号が小さい方を採用（idx < best_idx なら更新）。
4. 最後に best_idx が更新されていればそれを、されていなければ \(-1\) を出力する。

計算量

• 時間計算量: \(O(N)\)（全員を1回見るだけ）
• 空間計算量: \(O(1)\)（入力配列を除けば定数個の変数のみ）

実装のポイント

• 「真に大きい」なので条件は \(A_i > A_1\)（\(A_i \ge A_1\) ではない）に注意します。

• 同点処理では「出席番号が小さい方」を選ぶ必要があるため、最大値だけでなくそのときの番号も一緒に管理します。

• Python では入力が大きいので sys.stdin.buffer.read() を使うと高速に読み込めます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    A = data[1:]

    base = A[0]
    best_score = -1
    best_idx = -1

    for i in range(1, N):
        if A[i] > base:
            idx = i + 1
            if A[i] > best_score or (A[i] == best_score and idx < best_idx):
                best_score = A[i]
                best_idx = idx

    print(best_idx if best_idx != -1 else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。