概要

\(N\) 個のノートPCの中から、コストパフォーマンス（性能 \(S_i\) / 価格 \(R_i\)）が最大となるものの番号を求める問題です。同率の場合は、最も番号が小さいものを答えます。

考察

この問題の核心は、「いかにして誤差なく、効率的に分数の比較を行うか」という点にあります。

1. 浮動小数点数の精度の問題

素朴なアプローチとして、各ノートPCに対して S / R を計算し、その値を比較する方法が考えられます。しかし、プログラミング言語における浮動小数点数（float や double）には精度の限界があります。 今回の制約（\(R_i, S_i \leq 10^6\)）では致命的な誤差は出にくいですが、より厳しい制約や複雑な計算が含まれる問題では、微小な差を正しく判定できずに不正解（WA）となるリスクがあります。

2. 整数の乗算による比較

分数の比較 \(\frac{S_1}{R_1} > \frac{S_2}{R_2}\) は、両辺に \(R_1 \times R_2\) を掛けることで、以下の整数の比較に書き換えることができます。 $\(S_1 \times R_2 > S_2 \times R_1\)\( この方法を使えば、浮動小数点数を使わずに**整数のみで厳密に比較**することが可能です。 今回の最大値は \)10^6 \times 10^6 = 10^{12}$ となりますが、Pythonは標準で多倍長整数を扱えるため、オーバーフローを気にせず計算できます。

3. タイブレークの処理

「最大値が複数ある場合は最も番号が小さいものを選ぶ」という条件があります。 入力を 1 番目から順番に処理していき、「現在の暫定ベストよりも厳密に大きい（>）場合のみ」記録を更新するようにすれば、自然と最も小さい番号が保持されます。

アルゴリズム

1. 1番目のノートPCの情報を「暫定の最高コストパフォーマンス（best_r, best_s, best_idx）」として保持します。
2. 2番目から \(N\) 番目までのノートPCを順番に調べます。
3. 現在のノートPC \((R_i, S_i)\) と暫定ベスト \((best\_r, best\_s)\) を比較します。
   • \(S_i \times best\_r > best\_s \times R_i\) ならば、暫定ベストを現在のノートPCの情報で更新します。
4. 全ての比較が終わった後、best_idx を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を 1 回ずつ走査するため、入力の大きさに比例した時間で終了します。
• 空間計算量: \(O(1)\)（または \(O(N)\)）
  • 入力を 1 つずつ読み込んで処理する場合、保持する変数は数個だけなので \(O(1)\) です。全ての入力をリスト等に格納する場合は \(O(N)\) となります。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Pythonの標準的な input() 関数を繰り返すと実行時間制限（TLE）になる可能性があります。sys.stdin を使って一括で読み込むか、ジェネレータを使って効率的に処理するのが望ましいです。

• 比較の向き: \(S \times best\_r\) と \(best\_s \times R\) のどちらがどちらに対応するか（「現在の性能 × 過去の価格」か「過去の性能 × 現在の価格」か）を間違えないように注意しましょう。

  ソースコード

import sys

def main():
    # 入力を効率的に読み込むためのジェネレータ
    def input_generator():
        for line in sys.stdin:
            for x in line.split():
                yield int(x)
    
    gen = input_generator()
    try:
        n = next(gen)
    except StopIteration:
        return

    # 1番目のノートPCを暫定の最大コストパフォーマンスとして初期化
    best_idx = 1
    best_r = next(gen)
    best_s = next(gen)
    
    # 2番目以降のノートPCと比較
    for i in range(2, n + 1):
        r = next(gen)
        s = next(gen)
        
        # コストパフォーマンス s/r を比較する。
        # 浮動小数点の精度問題を避けるため、s/r > best_s/best_r を
        # s * best_r > best_s * r という整数の乗算の形で比較する。
        # 等しい場合は、問題の指示により「最も番号が小さいもの」を優先するため、
        # 厳密に大きい（>）場合のみ更新を行う。
        if s * best_r > best_s * r:
            best_idx = i
            best_r = r
            best_s = s
            
    # 結果を出力
    sys.stdout.write(str(best_idx) + '\n')

if __name__ == '__main__':
    main()

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