概要

\(N\) 個の商品の中から、値段と美味しさの条件を満たす商品を探し、値段が最も安い（同額なら美味しさが最も高い、さらに同点なら番号が最も小さい）商品を求める問題です。

考察

この問題では、各商品に対して以下の3つの条件をチェックする必要があります。

1. 値段が \(L\) 以上 \(R\) 以下
2. 美味しさが \(T\) 以上
3. 上記を満たす中で「値段が最小 → 美味しさが最大 → 番号が最小」の優先順位で最適なものを選ぶ

商品数 \(N\) は最大 \(2 \times 10^5\) なので、全商品を1回ずつ見る \(O(N)\) の解法で十分間に合います。ソートなどの追加処理も不要で、1回の線形走査で答えが求まります。

アルゴリズム

比較キーを使った線形走査で解きます。

各商品 \(i\) について条件（\(L \leq P_i \leq R\) かつ \(S_i \geq T\)）を満たすか判定し、満たす場合にこれまでの最良の商品と比較します。

比較の優先順位は以下の通りです：

1. 値段 \(P_i\) が小さい方が良い
2. 値段が同じなら、美味しさ \(S_i\) が大きい方が良い
3. それも同じなら、番号 \(i\) が小さい方が良い

これをタプルによる辞書順比較で実現します。具体的には、各商品に対してキー \((P_i, -S_i, i)\) を作ります。

• \(P_i\)：小さいほど良い → そのまま昇順
• \(-S_i\)：美味しさが大きいほど \(-S_i\) は小さくなる → 昇順比較で美味しさ降順を実現
• \(i\)：小さいほど良い → そのまま昇順

このタプルが辞書順で最小のものを選べば、すべての優先順位を正しく反映できます。

具体例: \(N=3, L=100, R=500, T=3\) で、商品が以下の場合を考えます。

商品番号	値段	美味しさ	条件を満たすか	キー
1	200	5	○	\((200, -5, 1)\)
2	200	8	○	\((200, -8, 2)\)
3	300	10	○	\((300, -10, 3)\)

キーの辞書順比較で \((200, -8, 2) < (200, -5, 1) < (300, -10, 3)\) なので、答えは商品 \(2\) です（値段が同じ200円の中で美味しさ8が最大）。

計算量

• 時間計算量: \(O(N)\) — 全商品を1回走査するだけ
• 空間計算量: \(O(N)\) — 入力データの読み込み分（最良の商品を記録する変数自体は \(O(1)\)）

実装のポイント

• タプルの辞書順比較を活用することで、3段階の優先順位を1回の比較 (key < best) でシンプルに処理できます。美味しさを負にする (-S) のがポイントです。

• sys.stdin.read() でまとめて入力を読み込むことで、\(N\) が大きい場合でも高速に動作します。

• 条件を満たす商品が1つも見つからなかった場合（best is None）に -1 を出力する処理を忘れないようにしましょう。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    L = int(input_data[idx]); idx += 1
    R = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    best = None  # (price, -tastiness, index)
    
    for i in range(1, N + 1):
        P = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        
        if L <= P <= R and S >= T:
            key = (P, -S, i)
            if best is None or key < best:
                best = key
    
    if best is None:
        print(-1)
    else:
        print(best[2])

main()

---

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