概要

各クエリ価格 \(X\) について、同価格の商品があれば商品番号順に全ての名前を出力し、なければ「最も近い価格」の商品名を 1 つ提案する問題です。

考察

重要なのは次の 2 点です。

1. 「価格がちょうど一致」する場合
   同じ価格の商品をすべて、商品番号の小さい順に出力します。入力は商品番号 \(1,2,\dots,N\) の順に与えられるので、同じ価格ごとに名前を配列に追加していけば、その配列は自然に商品番号順になります。

2. 一致がない場合は「最も近い価格」
   素朴に各クエリごとに全商品を走査して最小の \(|V_i-X|\) を探すと、\(O(NQ)\) で最大 \(10^{10}\) となり TLE します。
   そこで「価格」のみに注目し、存在する価格の集合をソートしておけば、二分探索で \(X\) の近く（直前と直後）の価格だけを見れば十分です。
   最も近い候補は、

   • \(X\) より小さい側で最大の価格（直前）
   • \(X\) 以上で最小の価格（直後）

のどちらかになります。

さらに、差が同じ（例：\(X=100\)、価格が 98 と 102）なら 商品番号が最小のものを選ぶ必要があります。ここで「ある価格に属する商品のうち最小の商品番号」を前計算しておけば、価格同士の比較だけでタイブレークまで処理できます。

アルゴリズム

前処理として次を作ります。

• price_to_names[v]：価格 \(v\) の商品の名前を、商品番号順に並べたリスト
  （入力順に append するだけで商品番号順が保たれる）
• price_to_min[v] = (min_index, name)：価格 \(v\) を持つ商品のうち、商品番号が最小の商品の（番号, 名前）
• prices：登場する価格（price_to_min のキー）を昇順ソートした配列

各クエリ \(X\) は以下で処理します。

1. もし price_to_names[X] が存在するなら、それをスペース区切りで出力。
2. 存在しないなら、prices に対して二分探索（bisect_left）で挿入位置 pos を求める。
   • pos==0：全ての価格が \(X\) より大 → 最小価格が最も近い
   • pos==len(prices)：全ての価格が \(X\) より小 → 最大価格が最も近い
   • それ以外：直前の価格 lo_p=prices[pos-1] と直後の価格 hi_p=prices[pos] を比べる
     差 \(d_\mathrm{lo}=X-lo_p\), \(d_\mathrm{hi}=hi_p-X\) を比較し、
     • 小さい方の価格に属する price_to_min[...] の名前を出力
     • 差が同じなら、price_to_min[lo_p] と price_to_min[hi_p] の 商品番号が小さい方の名前を出力

具体例

価格一覧が [80, 120, 200] のとき、\(X=150\) なら直前は 120、直後は 200。差は 30 と 50 なので 120 の商品の（最小番号の）名前を提案します。
\(X=160\) なら差が 40 と 40 で同じなので、120 側の最小番号商品と 200 側の最小番号商品を比べて、番号が小さい方を出します。

計算量

• 時間計算量:
  前処理 \(O(N)\)、価格ソート \(O(M\log M)\)（\(M\) は異なる価格数、\(M\le N\)）、各クエリ二分探索 \(O(\log M)\) より全体で \(O(N + M\log M + Q\log M)\)
  ※一致価格の出力は名前列を結合して出すため、追加で「出力される文字数」に比例します（問題文より総量は \(10^6\) 以下）。
• 空間計算量: \(O(N + M)\)（価格ごとの名前リストと、価格配列など）

実装のポイント

• 同価格商品の出力順は「商品番号順」なので、入力順にリストへ append するだけでよい。

• 「最も近い価格が複数」になったときのために、各価格について 最小の商品番号の商品を price_to_min に持っておく（これがないと同価格内で追加探索が必要になる）。

• 二分探索では「直前・直後」の 2 価格だけを見れば十分。

• \(N,Q\) が大きいので、Python では sys.stdin.buffer.read() による高速入力と、出力を配列に貯めて最後にまとめて出すのが安全です。

  ソースコード

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))

    price_to_names = {}
    price_to_min = {}  # price -> (min_index, name)

    for i in range(1, N + 1):
        s = next(it).decode()
        v = int(next(it))

        lst = price_to_names.get(v)
        if lst is None:
            price_to_names[v] = [s]
        else:
            lst.append(s)

        cur = price_to_min.get(v)
        if cur is None or i < cur[0]:
            price_to_min[v] = (i, s)

    prices = sorted(price_to_min.keys())

    out_lines = []
    for _ in range(Q):
        x = int(next(it))
        names = price_to_names.get(x)
        if names is not None:
            out_lines.append(" ".join(names))
            continue

        pos = bisect_left(prices, x)
        if pos == 0:
            out_lines.append(price_to_min[prices[0]][1])
        elif pos == len(prices):
            out_lines.append(price_to_min[prices[-1]][1])
        else:
            lo_p = prices[pos - 1]
            hi_p = prices[pos]
            d_lo = x - lo_p
            d_hi = hi_p - x
            if d_lo < d_hi:
                out_lines.append(price_to_min[lo_p][1])
            elif d_hi < d_lo:
                out_lines.append(price_to_min[hi_p][1])
            else:
                lo_i, lo_s = price_to_min[lo_p]
                hi_i, hi_s = price_to_min[hi_p]
                out_lines.append(lo_s if lo_i < hi_i else hi_s)

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。