概要

この問題は、商品データベースから指定された価格に一致する商品を検索し、存在しない場合は最も近い価格の商品を提案するシステムを実装するものです。

考察

問題の鍵となるポイントは2つあります：

1. 正確な価格マッチング: 指定された価格 \(X_j\) に完全一致する商品がある場合、それらを商品番号順にすべて出力する必要があります
2. 近い価格の提案: 一致する商品がない場合、価格の差の絶対値 \(|V_i - X_j|\) が最小で、同値の場合は商品番号が最小の商品を1つ選ぶ必要があります

素朴なアプローチでは、各クエリごとに全商品をスキャンすると \(O(NQ)\) の時間がかかり、\(N, Q\) が最大 \(10^5\) なので \(10^{10}\) 回の操作が必要となり、明らかにTLEになります。

アルゴリズム

効率的な解法として以下の手法を用います：

1. 事前処理: 商品データを価格ごとにグループ化し、各価格グループ内で商品番号順にソートします
2. 二分探索: すべての価格をソートしたリストを作成し、クエリ処理時に二分探索で位置を特定します
3. 候補選択: 正確な一致がない場合、二分探索で見つかった位置の前後の価格（最も近い価格）を候補とし、条件に従って最適な商品を選択します

具体的な手順： - 価格 \(v\) をキーとし、値として \((商品番号, 商品名)\) のリストを持つ辞書を作成 - 各価格グループ内を商品番号順にソート - すべての価格をソートしたリスト prices を作成 - 各クエリ \(X_j\) に対して： - prices で二分探索して \(X_j\) の位置を特定 - 正確に一致する価格があれば、対応する商品名をすべて出力 - なければ、前後の価格から候補を2つ選び、価格差と商品番号で比較して最適なものを選択

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • 事前ソート: \(O(N \log N)\)
  • 各クエリの処理: 二分探索が \(O(\log N)\)、正確一致時の出力は保証された総文字数内
• 空間計算量: \(O(N)\)
  • 商品データと価格リストの保存

実装のポイント

• bisect.bisect_left() で効率的に価格の位置を検索

• 正確一致時の出力では、事前に商品番号順にソート済みのリストから商品名を取得

• 候補選択時は、(価格差, 商品番号, 商品名) のタプルを作成し、価格差の最小値と商品番号の最小値でソート

• 出力文字数の総和制約により、大量の出力があっても問題ないことが保証されている

  ソースコード

import bisect

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n, q = map(int, data[0].split())
    products = []
    price_to_products = {}
    
    for i in range(1, n+1):
        parts = data[i].split()
        s = parts[0]
        v = int(parts[1])
        products.append((v, s, i))
        if v not in price_to_products:
            price_to_products[v] = []
        price_to_products[v].append((i, s))
    
    for key in price_to_products:
        price_to_products[key].sort(key=lambda x: x[0])
    
    prices = sorted(price_to_products.keys())
    queries = list(map(int, data[n+1:n+1+q]))
    
    output_lines = []
    for x in queries:
        if x in price_to_products:
            names = [item[1] for item in price_to_products[x]]
            output_lines.append(" ".join(names))
        else:
            idx = bisect.bisect_left(prices, x)
            candidates = []
            if idx > 0:
                candidate_price1 = prices[idx-1]
                diff1 = abs(candidate_price1 - x)
                candidate_product1 = price_to_products[candidate_price1][0]
                candidates.append((diff1, candidate_product1[0], candidate_product1[1]))
            if idx < len(prices):
                candidate_price2 = prices[idx]
                diff2 = abs(candidate_price2 - x)
                candidate_product2 = price_to_products[candidate_price2][0]
                candidates.append((diff2, candidate_product2[0], candidate_product2[1]))
            
            candidates.sort(key=lambda cand: (cand[0], cand[1]))
            output_lines.append(candidates[0][2])
    
    for line in output_lines:
        print(line)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。