概要

条件を満たす商品の中から、値段が最も安く、さらに美味しさが最も高く、それでも同点なら番号が小さい商品を選ぶ問題。

考察

この問題では、まず「値段が \(L\) 円以上 \(R\) 円以下」かつ「美味しさが \(T\) 以上」という2つの条件を満たす商品だけを候補として考えます。

これらの条件を満たさない商品は一切無視して構いません。候補がなければ -1 を出力します。

次に、候補の中から「最適な商品」を選ぶ必要があります。選ぶ基準は以下の通りです：

1. 値段が最も安い
2. 値段が同じなら、美味しさが最も高い
3. それも同じなら、商品番号が最も小さい

このように複数のキーでソートする必要があるため、素朴に毎回比較関数を書くのは面倒ですし、効率的ではありません。

そこで、候補となる商品リストを作った上で、ソートキーを工夫して一度で目的の順序に並べ替えます。

具体的には、タプル \((P, -S, idx)\) でソートすることで、自動的に「値段昇順 → 美味しさ降順 → 番号昇順」になります。

また、制約が非常に大きい（\(N\) が最大 \(2 \times 10^5\)）ので、効率的な入力処理が必要です。Python では sys.stdin.read() を使うことで高速化できます。

アルゴリズム

1. すべての商品を読み込み、タプル \((P_i, S_i, i)\) の形で保存する。
2. 条件 \(L \leq P_i \leq R\) かつ \(S_i \geq T\) を満たす商品だけを抽出する。
3. 抽出した商品リストを \((P_i, -S_i, i)\) をキーにしてソートする。
4. ソート後の先頭の要素のインデックス（商品番号）を出力する。
5. 条件を満たす商品が一つもない場合は -1 を出力する。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（商品リストを保持）

実装のポイント

• 入力を高速に行うために sys.stdin.read() を使用している。
• ソートキーを \((P, -S, idx)\) とすることで、複数キーの優先順位付きソートが簡単に実現できる。
• 商品番号は 1-indexed なので、タプルに保存する際は i + 1 としている。

## ソースコード

```python
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    R = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    goods = []
    for i in range(N):
        P = int(data[idx]); idx += 1
        S = int(data[idx]); idx += 1
        goods.append((P, S, i + 1))
    
    # 条件を満たす商品のみをフィルタリング
    valid_goods = [(P, S, idx) for P, S, idx in goods if L <= P <= R and S >= T]
    
    if not valid_goods:
        print(-1)
        return
    
    # 値段が最小 → 美味しさが最大 → 商品番号が最小
    # そのため、(P, -S, idx) の順でソートする
    valid_goods.sort(key=lambda x: (x[0], -x[1], x[2]))
    print(valid_goods[0][2])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。