概要

\(N\) 個のノートPCの中から、コストパフォーマンス（性能÷価格）が最大となるものを見つける問題です。

考察

素朴なアプローチとその問題点

最も直感的な方法は、各ノートPCについて \(\frac{S_i}{R_i}\) を浮動小数点数として計算し、最大値を求めることです。

# 素朴なアプローチ（問題あり）
cp = s / r  # 浮動小数点数での計算

しかし、この方法には浮動小数点数の誤差という問題があります。例えば： - ノートPC A: \(S = 1, R = 3\) → \(\frac{1}{3} = 0.333333...\) - ノートPC B: \(S = 2, R = 6\) → \(\frac{2}{6} = 0.333333...\)

本来同じ値ですが、コンピュータ内部では微小な誤差が生じる可能性があり、正確な比較ができないことがあります。

解決策：交差積（クロス乗算）による比較

2つの分数 \(\frac{S_i}{R_i}\) と \(\frac{S_j}{R_j}\) の大小比較は、以下のように整数の乗算に変換できます：

\[\frac{S_i}{R_i} > \frac{S_j}{R_j} \iff S_i \times R_j > S_j \times R_i\]

この変換により、除算を使わずに整数の乗算だけで正確に比較できます。

具体例

• ノートPC 1: 価格 \(R_1 = 100\), 性能 \(S_1 = 50\)
• ノートPC 2: 価格 \(R_2 = 80\), 性能 \(S_2 = 48\)

比較: \(S_2 \times R_1 = 48 \times 100 = 4800\) と \(S_1 \times R_2 = 50 \times 80 = 4000\)

\(4800 > 4000\) なので、ノートPC 2 の方がコストパフォーマンスが高いと分かります。

（実際に確認: \(\frac{50}{100} = 0.5\) < \(\frac{48}{80} = 0.6\)）

アルゴリズム

1. 最初のノートPCを暫定的な最良候補とする
2. 2番目以降のノートPCについて順番に処理：
   • 現在のノートPCと暫定最良候補のコストパフォーマンスを交差積で比較
   • 現在のノートPCの方が優れていれば、それを新しい最良候補に更新
3. 最終的な最良候補の番号を出力

「コストパフォーマンスが同じ場合は番号が小さいものを選ぶ」という条件は、比較で厳密な不等号（>）を使い、等しい場合は更新しないことで自然に満たされます。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のノートPCを1回ずつ走査するだけ
• 空間計算量: \(O(1)\)
  • 現在の最良候補の情報のみを保持

実装のポイント

1. 交差積のオーバーフロー: \(S_i, R_i \leq 10^6\) なので、積は最大 \(10^{12}\) 程度になります。Pythonでは整数のオーバーフローがないため問題ありませんが、C++などでは long long 型を使う必要があります。

2. 1-indexed: 問題文ではノートPCの番号は1から始まるので、ループも range(2, n + 1) として1-indexedで処理しています。

3. 入力を逐次処理: 全データを配列に格納せず、入力を読みながら比較することで、空間計算量を \(O(1)\) に抑えています。

   ソースコード

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())
    # Compare s/r with best_s/best_r using cross multiplication to avoid floating point issues
    # s/r > best_s/best_r is equivalent to s * best_r > best_s * r
    if s * best_r > best_s * r:
        best_idx = i
        best_r = r
        best_s = s

print(best_idx)

---

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