概要

各家について、最も近い避難所までの距離を求める問題です。避難所の座標がソート済みであることを利用し、二分探索で効率的に最寄りの避難所を見つけます。

考察

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

最も単純な方法は、各家 \(i\) に対して全ての避難所 \(j\) との距離 \(|X_i - P_j|\) を計算し、その最小値を求めることです。しかし、この方法は \(O(N \times M)\) の時間がかかります。\(N, M\) が最大 \(2 \times 10^5\) のため、最悪 \(4 \times 10^{10}\) 回の計算が必要となり、制限時間に間に合いません（TLE）。

重要な気づき

避難所の座標 \(P\) は昇順にソートされているという条件があります。ソート済みの配列に対して「ある値に最も近い要素」を探す操作は、二分探索を使えば \(O(\log M)\) で実現できます。

具体例で理解する

例えば、家の座標が \(x = 5\) で、避難所の座標が \(P = [1, 3, 7, 10]\) の場合を考えます。

二分探索で \(x = 5\) の「挿入位置」を求めると、\(\text{idx} = 2\)（\(P[2] = 7\) の手前）です。このとき、最寄りの避難所の候補は：

• 右側の候補: \(P[\text{idx}] = P[2] = 7\)（距離 \(= 7 - 5 = 2\)）
• 左側の候補: \(P[\text{idx} - 1] = P[1] = 3\)（距離 \(= 5 - 3 = 2\)）

よって、最寄りの避難所までの距離は \(\min(2, 2) = 2\) です。

アルゴリズム

1. 避難所の座標配列 \(P\) に対して、各家の座標 \(x\) について bisect_left で挿入位置 \(\text{idx}\) を求める。
2. \(\text{idx}\) は「\(P\) の中で \(x\) 以上となる最初の要素のインデックス」を表す。
3. 最寄りの避難所は、以下の最大2つの候補のうち近い方：
   • \(P[\text{idx}]\)（\(x\) 以上で最も小さい避難所、\(\text{idx} < M\) の場合のみ存在）
   • \(P[\text{idx} - 1]\)（\(x\) より小さい避難所のうち最も大きいもの、\(\text{idx} > 0\) の場合のみ存在）
4. 両方の候補との距離を比較し、小さい方を答えとする。

計算量

• 時間計算量: \(O(N \log M)\)
  • 各家について二分探索を1回行うため、1回あたり \(O(\log M)\)、全体で \(O(N \log M)\)
• 空間計算量: \(O(N + M)\)
  • 入力の配列と出力用の配列を保持する分

実装のポイント

• 境界チェック: 挿入位置 \(\text{idx}\) が \(0\) の場合（全ての避難所が家より右にある）や、\(M\) の場合（全ての避難所が家より左にある）に、配列の範囲外アクセスをしないよう注意が必要です。

• 出力の高速化: Python では print を \(N\) 回呼ぶと遅くなるため、結果をリストに溜めて最後に '\n'.join(out) でまとめて出力しています。

• bisect_left の意味: bisect_left(P, x) は、ソート済み配列 \(P\) に \(x\) を挿入するとき、ソート順を保つ最も左の位置を返します。つまり \(P[\text{idx}-1] < x \leq P[\text{idx}]\) が成り立ちます（境界が存在する場合）。

  ソースコード

import bisect

def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    out = []
    for x in X:
        idx = bisect.bisect_left(P, x)
        best = float('inf')
        if idx < M:
            best = min(best, P[idx] - x)
        if idx > 0:
            best = min(best, x - P[idx - 1])
        out.append(str(best))
    
    print('\n'.join(out))

main()

---

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