概要

商品の価格に基づいて検索クエリに応答するシステムを実装する問題です。 exact match（完全一致）があればその商品名をすべて出力し、なければ最も価格が近い商品を1つ提案します。

考察

この問題では、最大 \(10^5\) 個の商品と \(10^5\) 件のクエリが与えられるため、効率的な処理が必要です。

素朴なアプローチとその問題点

単純には、各クエリに対して全商品を走査して価格が一致するものを見つける方法があります。これは各クエリで \(O(N)\) かかり、全体で \(O(Q \cdot N)\) となり、最悪ケースで \(10^{10}\) 回の計算が必要になり、時間制限に間に合いません。

また、exact matchがない場合に「最も価格が近い商品」を見つけるのも、毎回線形探索していると同様に遅くなります。

改善策

• 各価格に対応する商品リストを事前に構築しておくことで、exact matchの判定と取得を高速に行えます。
• 「最も近い価格」を求めるには、価格のリストをソートしておき、二分探索（bisect）を使うことで高速に求められます。

さらに、exact matchがある場合は「商品番号順」に出力する必要があるため、事前に各価格ごとの商品リストを番号順にソートしておく必要があります。

アルゴリズム

1. 入力の読み込みと前処理

   • 各商品を (価格, 商品番号, 名前) のタプルとして保存。
   • defaultdict(list) を使い、価格ごとに (商品番号, 名前) のリストを保持。
   • 価格ごとのリストは、商品番号の昇順にソートしておく。

2. 価格のソート

   • 価格のキーだけを抜き出してソートしたリスト sorted_prices を作成（二分探索用）。

3. クエリ処理

   • 各クエリ \(X_j\) に対して以下を行う：
     • Exact Match: \(X_j\) がキーとして存在すれば、その価格の商品名リストを順番に連結して出力。
     • Nearest Price:

          - `bisect_left(sorted_prices, X_j)` で $X_j$ 以上の最小の価格の位置を取得。
          - その位置の左右（あれば）の価格を候補として、差分と商品番号を比較し、条件を満たす商品を1つ選択。
       

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • 商品の前処理に \(O(N \log N)\)（価格リストのソート）
  • 各クエリで二分探索に \(O(\log N)\)、候補比較は定数時間なので全体で \(O(Q \log N)\)
• 空間計算量: \(O(N + Q)\)
  • 商品情報、価格ごとのマッピング、ソートされた価格リストなどを保持

実装のポイント

• 商品データは (価格, 番号, 名前) のようにタプルで管理し、ソートや検索をしやすくする。

• exact match時の出力は「番号順」なので、価格ごとのリストを事前にソートしておくのが重要。

• 二分探索後に左右の候補を比較する際、差が同じなら「商品番号が小さい方」を選ぶことに注意。

• 入力を高速に読み込むために sys.stdin.read を使用し、文字列分割は一度だけ行うことで高速化を図っている。

  ソースコード

import bisect
from collections import defaultdict
import sys

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    products = []
    price_to_names = defaultdict(list)
    
    for i in range(N):
        S = data[idx]
        idx += 1
        V = int(data[idx])
        idx += 1
        products.append((V, i, S))
        price_to_names[V].append((i, S))
    
    # 各価格ごとに商品を番号順にソート
    for price in price_to_names:
        price_to_names[price].sort()
    
    # 価格リストをソートしたものを保持（二分探索用）
    sorted_prices = sorted(price_to_names.keys())
    
    results = []
    for _ in range(Q):
        X = int(data[idx])
        idx += 1
        
        if X in price_to_names:
            # 一致する価格の商品名を番号順に出力
            names = [name for _, name in price_to_names[X]]
            results.append(' '.join(names))
        else:
            # 最も近い価格を探す
            pos = bisect.bisect_left(sorted_prices, X)
            candidates = []
            
            # 左隣
            if pos > 0:
                left_price = sorted_prices[pos - 1]
                diff = abs(left_price - X)
                candidates.append((diff, price_to_names[left_price][0][0], price_to_names[left_price][0][1]))
            
            # 右隣
            if pos < len(sorted_prices):
                right_price = sorted_prices[pos]
                diff = abs(right_price - X)
                candidates.append((diff, price_to_names[right_price][0][0], price_to_names[right_price][0][1]))
            
            # 最小差分を選ぶ（同じなら番号が小さい方）
            candidates.sort()
            results.append(candidates[0][2])
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

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