概要

\(N\) 個の商品に対して \(Q\) 件の価格検索クエリを処理する問題です。指定価格と一致する商品があればすべて出力し、なければ価格が最も近い商品を1つ提案します。

考察

重要な気づき

各クエリで「価格がちょうど \(X_j\) の商品があるか？」を判定し、ない場合は「最も価格が近い商品」を高速に見つける必要があります。

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

各クエリに対して全商品を線形に走査すると、1回のクエリで \(O(N)\) かかり、全体で \(O(NQ)\) となります。\(N, Q \leq 10^5\) なので最大 \(10^{10}\) 回の操作となり、TLE（時間超過） になります。

解決方針

• 完全一致の判定: 辞書（ハッシュマップ）を使えば \(O(1)\) で判定できます。
• 最も近い価格の検索: ユニークな価格をソートしておき、二分探索を使えば \(O(\log N)\) で見つけられます。

アルゴリズム

1. 前処理:

   • 各価格に対して、その価格を持つ商品の番号リストを辞書 price_to_items に格納します。商品は番号 \(1, 2, \ldots, N\) の順に処理するので、リストは自然に商品番号の昇順になります。
   • ユニークな価格を取り出してソートした配列 sorted_prices を作ります。

2. 各クエリの処理（指定価格 \(X_j\) に対して）:

   • 完全一致がある場合: price_to_items[X_j] に登録された商品番号の順に、名前をスペース区切りで出力します。
   • 完全一致がない場合: sorted_prices に対して二分探索（bisect_left）を行い、挿入位置 pos を得ます。最も近い価格の候補は sorted_prices[pos-1]（\(X_j\) より小さい側）と sorted_prices[pos]（\(X_j\) より大きい側）の最大2つです。それぞれについて差の絶対値を比較し、差が同じ場合は商品番号が最小のものを選びます。

具体例

商品: apple 100, banana 200, cherry 100 で、クエリ \(X = 150\) の場合： - 完全一致なし → sorted_prices = [100, 200] で二分探索すると pos = 1 - 候補: sorted_prices[0] = 100（差50）、sorted_prices[1] = 200（差50） - 差が同じなので、商品番号が小さい方 → 価格100の商品1番「apple」を出力

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • 前処理でユニーク価格のソートに \(O(N \log N)\)
  • 各クエリで辞書参照 \(O(1)\) または二分探索 \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • 辞書・ソート済み配列・商品名の格納に必要

実装のポイント

• 辞書による完全一致判定: x in price_to_items で \(O(1)\) 判定できるため、完全一致と非一致の場合分けが高速に行えます。

• 二分探索の境界チェック: bisect_left の結果 pos が 0 や len(sorted_prices) になる場合があるので、候補を確認する際に範囲外アクセスしないよう注意が必要です。

• 同じ差の場合の処理: 差が等しい候補が2つあるとき、各価格グループの先頭（最小商品番号）を比較して、番号が小さい方を選びます。price_to_items[v][0] が各価格グループの最小商品番号です。

• 高速入出力: sys.stdin.buffer.read() で一括読み込みし、出力も '\n'.join() でまとめて書き出すことで、I/Oのオーバーヘッドを削減しています。

  ソースコード

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    Q = int(tokens[idx]); idx += 1
    
    names = []
    prices = []
    for i in range(N):
        s = tokens[idx]; idx += 1
        v = int(tokens[idx]); idx += 1
        names.append(s)
        prices.append(v)
    
    # Group by price: price -> list of (original_index, name)
    from collections import defaultdict
    price_to_items = defaultdict(list)
    for i in range(N):
        price_to_items[prices[i]].append(i)
    
    # Sorted unique prices for binary search
    sorted_prices = sorted(price_to_items.keys())
    
    out = []
    for _ in range(Q):
        x = int(tokens[idx]); idx += 1
        
        if x in price_to_items:
            # Exact match - items are already stored in order of original index
            items = price_to_items[x]
            out.append(' '.join(names[i] for i in items))
        else:
            # Find closest price
            pos = bisect_left(sorted_prices, x)
            best_diff = float('inf')
            best_idx = N  # large sentinel
            
            # Check pos-1 and pos
            for p in (pos - 1, pos):
                if 0 <= p < len(sorted_prices):
                    diff = abs(sorted_prices[p] - x)
                    if diff < best_diff or (diff == best_diff and price_to_items[sorted_prices[p]][0] < best_idx):
                        best_diff = diff
                        best_idx = price_to_items[sorted_prices[p]][0]
            
            out.append(names[best_idx])
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

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