概要

\(N\) 個の商品の中から、指定された値段の範囲 \([L, R]\) かつ美味しさが \(T\) 以上という条件を満たすもののうち、最も「条件に合致する」商品の番号を求める問題です。

考察

この問題で最も重要なのは、「どの商品が最も優先されるか」という優先順位の整理と、大量のデータを効率よく処理することです。

1. 優先順位の整理

条件を満たす商品が複数ある場合、以下の優先順位で 1 つに絞り込みます。 1. 値段が最も低いもの 2. 値段が同じなら、美味しさが最も高いもの 3. 値段も美味しさも同じなら、商品番号が最も小さいもの

2. 条件の判定

各商品 \((P_i, S_i)\) に対して、以下の条件をすべて満たすかチェックすればよいです。 - \(L \leq P_i \leq R\) - \(S_i \geq T\)

3. 最適な商品の更新

商品を \(1\) 番目から順に見ていくとき、暫定の「最高の商品」を保持しておきます。新しい商品が条件を満たし、かつ「暫定の最高の商品」よりも優れている（値段が安い、または値段が同じで美味しさが高い）場合にのみ更新します。

商品番号が最小のものを出力するという条件については、商品を番号順（\(1, 2, \dots, N\)）に走査し、同点の場合は更新しないというルールにすることで、自然に「最も番号が小さいもの」が残るようになります。

アルゴリズム

1. 最適な商品の番号 best_idx を -1、その値段 best_p を無限大、美味しさ best_s を -1 で初期化します。
2. 商品 \(i = 1, 2, \dots, N\) について以下を繰り返します。
   • もし \(L \leq P_i \leq R\) かつ \(S_i \geq T\) ならば：
     • まだ条件を満たす商品が見つかっていない（best_idx == -1）
     • または、現在の商品の値段が安い（\(P_i < \text{best\_p}\)）
     • または、値段が同じで美味しさが高い（\(P_i = \text{best\_p}\) かつ \(S_i > \text{best\_s}\)）
     • 上記のいずれかを満たすなら、best_idx, best_p, best_s を更新します。
3. 最終的な best_idx を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 商品の数 \(N\) に対して、各商品を 1 回ずつ確認するため、ループの回数は \(N\) 回です。\(N \leq 2 \times 10^5\) なので、十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力値をすべてリストに格納する場合、商品数に比例したメモリを使用します。

実装のポイント

• 高速な入力処理: Python では \(N\) が \(10^5\) を超える場合、input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が実行時間を短縮できます。

• 初期値の設定: 「最小値を求める」ときは初期値を非常に大きな数（float('inf') など）に、「最大値を求める」ときは非常に小さな数（-1 など）に設定するのが定石です。

• インデックスの調整: 問題文の商品番号は \(1\) から始まりますが、プログラミング言語のループやリストは \(0\) から始まることが多いため、出力時に +1 するか、ループ内で調整する必要があります。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # すべてのトークンを整数に変換します
    # 大量のデータを扱う場合、一括で変換する方が個別に変換するより高速な傾向があります
    nums = list(map(int, input_data))
    
    # 基本情報の取得
    N = nums[0]
    L = nums[1]
    R = nums[2]
    T = nums[3]
    
    # 最適な商品の情報を保持する変数
    # best_idx: 商品番号, best_p: 値段, best_s: 美味しさ
    best_idx = -1
    best_p = float('inf')
    best_s = -1
    
    # 各商品を順番にチェックします
    # 商品iの値段Piはnums[4 + 2*i]、美味しさSiはnums[5 + 2*i]に格納されています
    for i in range(N):
        p = nums[4 + 2*i]
        s = nums[5 + 2*i]
        
        # 条件1: 値段がL以上R以下
        # 条件2: 美味しさがT以上
        if L <= p <= R and s >= T:
            # 以下のいずれかの場合に最適な商品を更新します
            # 1. 条件を満たす商品がまだ見つかっていない
            # 2. 現在の商品の方が値段が安い
            # 3. 値段が同じで、現在の性能（美味しさ）が高い
            # 商品番号が小さいものを優先するという条件は、ループを1からNの順で回し、
            # 同点の場合に更新しないことで自然に満たされます
            if best_idx == -1 or p < best_p or (p == best_p and s > best_s):
                best_idx = i + 1
                best_p = p
                best_s = s
    
    # 結果を出力します
    print(best_idx)

if __name__ == '__main__':
    main()

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