概要

一直線上に並ぶ \(N\) 箇所の消防署から、\(Q\) 件の火災通報それぞれに対して、待機中の消防車のうち最も近いものを出動させる問題です。出動した消防車は以降使えなくなるため、動的に管理する必要があります。

考察

重要な気づき

1. 毎回「最も近い待機中の消防車」を見つける必要がある: 火災地点 \(P_j\) に対して、まだ出動していない消防署の中から最も距離が近いものを選びます。距離が同じなら性能値 \(S_i\) が大きい方、それでも同じなら番号が小さい方を選びます。

2. 消防署の座標 \(X_i\) は狭義単調増加: すべて異なる値です。これにより、ある火災地点に対して等距離にある消防署は高々2つ（左側に1つ、右側に1つ）しかありません。

3. 出動するたびに消防署が1つ減る: 動的にデータを管理し、効率よく検索・削除ができるデータ構造が必要です。

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

毎回全消防署を走査して最も近いものを探すと \(O(NQ)\) となり、\(N, Q\) が最大 \(2 \times 10^5\) の場合 \(4 \times 10^{10}\) 程度の計算量になり TLE します。

解決方針

平衡二分探索木（ソート済みリスト）を使って、待機中の消防署を座標順に管理します。火災地点 \(P_j\) に対して二分探索を行えば、最も近い候補を \(O(\log N)\) で見つけられます。

アルゴリズム

1. データ構造の準備: 待機中の消防署を SortedList に \((X_i, -S_i, i)\) というタプルで格納します。\(-S_i\) とするのは、距離が同じとき性能値が大きいものを優先するためです（タプルの比較で小さい方が優先されるので、符号を反転）。

2. 各火災通報の処理:

   • 火災地点 \(P_j\) に対して bisect_left((P, -∞, -1)) で挿入位置 pos を求めます。
   • pos - 1（左側の最近候補）と pos（右側の最近候補）の2つを確認します。
   • 各候補について比較キー \((|X_i - P_j|, -S_i, i)\) を計算し、このタプルが最小のものを選びます。
     • 距離が最小 → 性能値が最大（\(-S_i\) が最小）→ 番号が最小
   • 選ばれた消防署を SortedList から削除し、結果を出力します。

3. 候補が2つで十分な理由: \(X_i\) はすべて異なるため、ソート済みリスト上で火災地点の左隣と右隣をチェックすれば、最小距離の候補をすべて網羅できます。同じ距離の消防署が3つ以上存在することはありません。

具体例

\(X = [2, 5, 8]\), \(S = [3, 1, 3]\) で火災地点 \(P = 5\) の場合： - pos は \((5, ...)\) の位置 → 候補は pos-1（座標2）と pos（座標5） - 距離: 座標2は \(|2-5|=3\)、座標5は \(|5-5|=0\) - 座標5の消防署（消防署2）が出動

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 初期化で \(N\) 回の挿入（各 \(O(\log N)\)）、各クエリで二分探索と削除（各 \(O(\log N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• タプルの設計: \((X_i, -S_i, i)\) とすることで、Python のタプル比較をそのまま利用して優先順位の判定ができます。距離の比較は別途 abs(X_i - P) で行い、同距離の場合にタプルの第2・第3要素で自動的にタイブレークされます。

• bisect_left の検索キー: (P, -∞, -1) を使うことで、座標が \(P\) ちょうどの消防署があれば pos がその位置を指し、なければ \(P\) より大きい最小の座標を指します。これにより pos-1 と pos の2箇所を調べるだけで済みます。

• sortedcontainers.SortedList: Python 標準ライブラリにはないため、sortedcontainers を使います。競技プログラミングの Python 環境では利用可能なことが多いです。

  ソースコード

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N, Q = int(input_data[idx]), int(input_data[idx+1])
    idx += 2
    
    X = [0] * N
    S = [0] * N
    for i in range(N):
        X[i] = int(input_data[idx])
        S[i] = int(input_data[idx+1])
        idx += 2
    
    # We need to efficiently find the closest available fire station to a given point.
    # On ties in distance, pick highest S, then smallest index.
    
    # We'll use a SortedList of (X[i], -S[i], i) for available stations.
    # For each query, we need to find candidates near P using binary search.
    
    available = SortedList()
    for i in range(N):
        available.add((X[i], -S[i], i))
    
    out = []
    
    for _ in range(Q):
        P = int(input_data[idx])
        idx += 1
        
        # Binary search for position of P in available
        # We want to check the element just before and at the insertion point
        pos = available.bisect_left((P, float('-inf'), -1))
        
        best = None
        best_key = None  # (distance, -S[i], i)
        
        # Check candidates around pos
        for p in (pos - 1, pos):
            if 0 <= p < len(available):
                xi, neg_si, i = available[p]
                dist = abs(xi - P)
                key = (dist, neg_si, i)
                if best_key is None or key < best_key:
                    best_key = key
                    best = (xi, neg_si, i)
        
        # The above checks at most 2 candidates. But there could be ties in distance
        # at positions further away. For example, if pos-1 and pos have the same distance,
        # we handled it. But what if pos+1 also has the same distance?
        # Actually, since X values are strictly increasing, at most 2 stations can be
        # equidistant (one on each side). But after removals, the sorted list entries
        # are a subset, so at most one on each side at closest distance.
        # Wait, X are strictly increasing, so all X[i] are distinct. In the sorted list,
        # keyed by (X[i], ...), X values are distinct. So bisect gives us at most
        # one candidate on each side at minimum distance. That's correct.
        
        out.append(str(best[2] + 1))
        available.remove(best)
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

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