概要

\(N\) 人の参加者それぞれについて「味の得点 \(H_i\)」と「盛り付けの得点 \(S_i\)」の合計である実力値 \(H_i + S_i\) を計算し、それが最大となる参加者の番号を求める問題です。

考察

• 各参加者には \(H_i\), \(S_i\), \(D_i\) の3つの値が与えられますが、ボーナス得点 \(D_i\) は実力値の計算に一切関係ありません。これは問題文中の「特別な食材の影響を除いた純粋な料理の腕前を評価したい」という記述に対応しています。
• つまり、\(D_i\) は読み捨てればよい値であり、各参加者について \(H_i + S_i\) だけを見ればよいことが重要な気づきです。
• この問題は「\(N\) 個の値の中から最大値を持つインデックスを求める」という基本的な問題に帰着されます。
• \(N\) は最大 \(2 \times 10^5\) なので、全参加者を1回ずつ見る \(O(N)\) の方法で十分間に合います。特別なアルゴリズムは不要です。

アルゴリズム

1. 「これまでの最大実力値」を保持する変数 best_val と、「そのときの参加者番号」を保持する変数 best_idx を用意する。
2. 参加者 \(i = 1, 2, \dots, N\) について順に以下を行う：
   • \(H_i, S_i, D_i\) を入力から読み取る。
   • 実力値 \(\text{val} = H_i + S_i\) を計算する（\(D_i\) は使わない）。
   • \(\text{val} > \text{best\_val}\) であれば、best_val を \(\text{val}\) に、best_idx を \(i\) に更新する。
3. 最終的な best_idx を出力する。

具体例: \(N = 3\) で以下の入力が与えられたとします。

参加者1は総合得点 \(100+50+200=350\) で最も高いですが、実力値は \(150\) です。実力値が最大なのは参加者2の \(170\) なので、答えは 2 です。このように \(D_i\) に惑わされないことがポイントです。

計算量

• 時間計算量: \(O(N)\) — 各参加者を1回ずつ走査するだけ
• 空間計算量: \(O(1)\) — 最大値とそのインデックスを保持する変数のみ使用（全データを配列に格納する必要はない）

実装のポイント

• best_val の初期値を \(-1\) としていますが、制約より \(H_i \geq 0, S_i \geq 0\) なので実力値は必ず \(0\) 以上となり、最初の参加者で必ず更新されるため問題ありません。

• 参加者の番号は 1-indexed（1から始まる）であることに注意してください。for i in range(1, N+1) とすることで、そのまま番号として使えます。

• \(D_i\) は入力として読み取りますが、計算には使用しません。入力フォーマットに合わせて正しく読み取ることだけ注意しましょう。

  ソースコード

N = int(input())
best_idx = -1
best_val = -1
for i in range(1, N + 1):
    H, S, D = map(int, input().split())
    val = H + S
    if val > best_val:
        best_val = val
        best_idx = i
print(best_idx)

この解説は claude4.6opus-thinking によって生成されました。