概要

各ノートPCのコストパフォーマンス \(\frac{S_i}{R_i}\) を比較し、最大となるPCの番号（同率なら最小番号）を求めます。

考察

最大の \(\frac{S_i}{R_i}\) を探すだけなら、各PCについて値を計算して最大を取ればよさそうに見えます。しかし素朴に 浮動小数点（float）で割り算して比較すると、丸め誤差により本来は等しい／大小関係が逆になる可能性があり、WAの原因になります。

そこで、分数同士の比較は割り算をせずに 交差乗算で行います。
2つのPC \(a,b\) について - \(\frac{S_a}{R_a} > \frac{S_b}{R_b}\) かどうかは - \(S_a \cdot R_b > S_b \cdot R_a\) で判定できます（\(R_a, R_b > 0\) なので不等号の向きは変わりません）。

これなら整数演算だけで正確に比較でき、\(N \le 2 \times 10^5\) でも1回走査で十分間に合います。

同率（\(\frac{S_a}{R_a} = \frac{S_b}{R_b}\)）の場合は「番号が小さい方」を選ぶ必要がありますが、先に見つけたものを保持しておけば、等しいときに更新しないだけで条件を満たせます。

アルゴリズム

1. 1番目のPCを「暫定ベスト」として記録する（best_R, best_S, best_idx）。
2. \(i=2\) から \(N\) まで順にPC \((R,S)\) を読む。
3. 現在のPCと暫定ベストを交差乗算で比較する：
   • left = S * best_R
   • right = best_S * R
   • もし left > right なら \(\frac{S}{R} > \frac{best\_S}{best\_R}\) なので、暫定ベストをこのPCに更新する。
   • left == right（同率）のときは更新しない（より小さい番号が既に保持されているため）。
4. 最後に best_idx を出力する。

例：
ベストが \((R,S)=(10,6)\)（\(\frac{6}{10}\)）で、次が \((15,10)\)（\(\frac{10}{15}\)）なら
\(10 \cdot 10 = 100\) と \(6 \cdot 15 = 90\) を比べ、\(100>90\) なので次の方が高コスパと分かります。

計算量

• 時間計算量: \(O(N)\)（各PCを1回ずつ比較）
• 空間計算量: \(O(1)\)（ベスト情報だけ保持）

実装のポイント

• 割り算（浮動小数点）で比較せず、必ず交差乗算 \(S_1 R_2\) と \(S_2 R_1\) で比較する。

• 同率時は「最小番号」を優先するため、> のときだけ更新し、== では更新しない。

• 入力が最大 \(2 \times 10^5\) 行なので sys.stdin.readline を使うと安定して高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    best_idx = 1
    best_R, best_S = map(int, input().split())

    for i in range(2, N + 1):
        R, S = map(int, input().split())
        left = S * best_R
        right = best_S * R
        if left > right:
            best_idx = i
            best_R, best_S = R, S
        # if equal, keep earlier index (already best)

    print(best_idx)

if __name__ == "__main__":
    main()

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