概要

商品の価格検索クエリに対して、指定された価格とピッタリ一致する商品があれば該当する全商品を、なければ最も価格が近い商品（複数候補があれば商品番号最小のもの）を高速に答える問題です。

考察

\(N, Q\) がともに最大 \(10^5\) であるため、クエリごとに全商品を調べていては計算量が \(O(NQ)\) となり、実行時間制限超過（TLE）になってしまいます。そのため、クエリを高速に処理する工夫が必要です。

• ピッタリの価格の検索 価格をキーとして商品番号を保存するハッシュマップ（連想配列や辞書）を使えば、\(O(1)\) または \(O(\log N)\) で高速に検索可能です。
• 最も近い価格の検索 存在する価格のリストをあらかじめ昇順にソートしておき、二分探索を行うことで \(O(\log N)\) で前後の価格を見つけることができます。

また、問題文には「一致する商品は商品番号の小さい順に出力する」「差が同じ場合は商品番号が小さい方を出力する」という条件があります。入力データは最初から商品番号の昇順（\(1\) 番から \(N\) 番）で与えられるため、辞書に順番に追加していくだけで、自動的に商品番号の昇順リストが作成されます。この性質を利用すると実装がとても楽になります。

アルゴリズム

1. 前計算（データの準備）

   • 商品情報を順番に読み込みます。価格 \(v\) をキー、その価格を持つ商品番号のリストを値とした辞書 exact_match を作成します。
   • 存在する価格（exact_match のキー）をすべて取り出し、昇順にソートした配列 sorted_V を作成します。

2. クエリの処理 各リクエストの価格 \(X\) について以下を行います。

   • ピッタリの価格がある場合 辞書 exact_match に \(X\) が存在するか確認し、存在すればそのリストにある全ての商品名をスペース区切りで出力します。
   • ピッタリの価格がない場合 二分探索を使って、sorted_V の中で \(X\) が挿入されるべき位置 pos を探します。
     • pos == 0 の場合：全ての商品の価格が \(X\) より高いため、最も安い sorted_V[0] を選びます。
     • pos が配列の長さと等しい場合：全ての商品の価格が \(X\) より安いため、最も高い sorted_V[-1] を選びます。
     • それ以外の場合：\(X\) を挟む2つの価格 \(v_1 = sorted\_V[pos-1]\) と \(v_2 = sorted\_V[pos]\) が候補になります。価格の差 \(|v_1 - X|\) と \(|v_2 - X|\) を比較し、差が小さい方の価格を選びます。もし差が等しい場合は、それぞれの価格を持つ商品の中で最も小さい商品番号（辞書のリストの先頭要素）同士を比較し、商品番号が小さい方の価格を選びます。
     • 最後に、選ばれた価格のリストの先頭にある商品名を出力します。

計算量

• 時間計算量: \(O(N \log N + Q \log N + L)\)
  • 価格の種類数を \(K\) (\(K \le N\)) とすると、価格のソートに \(O(K \log K)\) かかります。
  • \(Q\) 回のクエリに対する二分探索に \(O(Q \log K)\) かかります。
  • 辞書の検索は \(O(1)\) です。
  • \(L\) は全クエリで出力される文字数の総和です（制約より \(10^6\) 以下）。
  • 全体として非常に高速に動作し、制限時間に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • 商品名、辞書、ソートされた価格配列などを保持するためのメモリです。

実装のポイント

• 二分探索の活用: Pythonでは bisect モジュールの bisect_left を使うことで、二分探索を自分で実装することなく簡単に利用できます。

• リストの先頭要素の利用: 商品を順番に処理して辞書に追加しているため、exact_match[v] のリストは必ず商品番号の昇順になります。したがって、exact_match[v][0] にアクセスするだけで、「価格 \(v\) の中で最も商品番号が小さいもの」を \(O(1)\) で取得できます。

• 高速な入出力: 大量の入出力を伴うため、input() や print() を毎回呼ぶと時間がかかります。sys.stdin.read().split() で入力を一括で読み込み、出力も配列に貯めてから最後に \n で繋いで一気に出力することで、処理を高速化しています。

  ソースコード

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    S = []
    exact_match = {}
    
    idx = 2
    for i in range(N):
        s = input_data[idx]
        v = int(input_data[idx+1])
        S.append(s)
        if v not in exact_match:
            exact_match[v] = []
        exact_match[v].append(i)
        idx += 2
        
    sorted_V = sorted(exact_match.keys())
    
    out = []
    for _ in range(Q):
        X = int(input_data[idx])
        idx += 1
        
        if X in exact_match:
            out.append(" ".join([S[i] for i in exact_match[X]]))
        else:
            pos = bisect_left(sorted_V, X)
            if pos == 0:
                best_V = sorted_V[0]
            elif pos == len(sorted_V):
                best_V = sorted_V[-1]
            else:
                v1 = sorted_V[pos - 1]
                v2 = sorted_V[pos]
                diff1 = X - v1
                diff2 = v2 - X
                if diff1 < diff2:
                    best_V = v1
                elif diff2 < diff1:
                    best_V = v2
                else:
                    idx1 = exact_match[v1][0]
                    idx2 = exact_match[v2][0]
                    if idx1 < idx2:
                        best_V = v1
                    else:
                        best_V = v2
            out.append(S[exact_match[best_V][0]])
            
    sys.stdout.write("\n".join(out) + "\n")

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。