概要

\(N\) 人の生徒の得票数の中から最大値を求め、その最大値を持つ生徒が「ただ一人」であるかどうかを判定する問題です。唯一の最多得票者がいればその番号（1-indexed）を、そうでなければ \(-1\) を出力します。

考察

この問題を解くためには、以下の2つのステップが必要です。

1. 最多得票数（最大値）がいくつかを知る
2. その最多得票数を得た生徒が何人いるかを確認する

例えば、得票数が \([3, 5, 2]\) の場合、最大値は \(5\) です。\(5\) 票獲得した生徒は生徒 2 の一人だけなので、答えは 2 となります。 一方で、得票数が \([4, 4, 1]\) の場合、最大値は \(4\) です。\(4\) 票獲得した生徒は生徒 1 と生徒 2 の二人いるため、答えは -1 となります。

生徒数 \(N\) は最大で \(2 \times 10^5\) であるため、リストを端から順番に確認するような \(O(N)\) のアルゴリズムであれば、制限時間内に十分に正解することができます。

アルゴリズム

以下の手順で実装します。

1. 最大値の特定: 与えられた得票数のリスト \(A\) を走査し、最大値 max_votes を見つけます。
2. 人数のカウントと番号の保持: もう一度リストを走査し、得票数が max_votes と等しい生徒の数をカウントします。
   • 同時に、その生徒の番号（インデックス + 1）を記録しておきます。
   • もしカウントが 2 以上になったら、その時点で唯一ではないことが確定するため、探索を打ち切っても構いません。
3. 条件分岐:
   • カウントがちょうど 1 であれば、記録しておいた生徒の番号を出力します。
   • カウントが 1 以外（2以上）であれば、-1 を出力します。

計算量

• 時間計算量: \(O(N)\) リストの走査を数回行うだけなので、生徒数 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\) 入力された \(N\) 人分の得票数をリストに格納するために必要なメモリ量です。

実装のポイント

• 1-indexed への変換: プログラミング言語の配列（リスト）は通常 0 から始まりますが、問題文の生徒番号は 1 から始まります。出力する際は インデックス + 1 をすることを忘れないようにしましょう。

• 最大値の初期化: 最大値を探す際の初期値は、得票数の最小値である \(0\) 以下の値（\(-1\) など）に設定しておくとスムーズです。

• 早期終了: 最多得票者が 2 人見つかった時点で、答えが -1 になることは確定します。大きなデータに対して少しでも効率的に動かすために、カウントが 1 を超えたらループを抜ける（break）処理を入れるのが定石です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（生徒数）と A（各生徒の得票数）を取得
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # 最多得票数を求める
    max_votes = -1
    for x in a:
        if x > max_votes:
            max_votes = x
            
    # 最多得票の生徒をカウントし、その番号を保持する
    count = 0
    winner_idx = -1
    for i in range(n):
        if a[i] == max_votes:
            count += 1
            winner_idx = i + 1
            # 2人以上見つかった時点で -1 確定なので打ち切る
            if count > 1:
                break
                
    # 最多得票の生徒が1人ならその番号を、そうでなければ -1 を出力
    if count == 1:
        print(winner_idx)
    else:
        print(-1)

if __name__ == "__main__":
    solve()

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