概要

数直線上にある家と避難所の位置が与えられるので、各家庭から最も近い避難所までの距離を求めます。

考察

この問題では、各家庭の座標 \(X_i\) に対して、最も近い避難所の座標 \(P_j\) を見つけ、その距離 \(|X_i - P_j|\) を求めることになります。

愚直に全ての避難所について距離を計算すると、計算量は \(O(N \times M)\) となり、最大で \(4 \times 10^{10}\) 回の計算が必要になり、時間制限に間に合いません（TLE）。

しかし、避難所の座標が昇順に並んでいることを利用すれば、二分探索によって「最も近い避難所」を高速に求めることができます。具体的には、ある家 \(X_i\) に対して次の2つの候補だけを考えればよいです： - \(X_i\) 以上で最小の避難所（右隣） - \(X_i\) 未満で最大の避難所（左隣）

これらは bisect モジュールを使うことで \(O(\log M)\) で求められます。

例えば、家の座標が 5 で、避難所が [2, 6, 8] だとすると、 - 左隣は 2、右隣は 6 - 距離はそれぞれ 3 と 1 → 最小は 1

このように、両隣だけを見れば十分です。

アルゴリズム

1. 各家 \(X_i\) に対して、避難所リスト \(P\) 上で二分探索を行う。
2. bisect.bisect_left(P, x) を使い、\(x\) 以上となる最小の避難所のインデックスを得る。
3. そのインデックスと、その1つ前のインデックスに対応する避難所との距離を比較し、小さい方を選ぶ。
4. これをすべての家について繰り返す。

計算量

• 時間計算量: \(O(N \log M)\)
  各家に対して \(O(\log M)\) の二分探索を行うため。
• 空間計算量: \(O(N + M)\)
  入力データをリストとして保持する必要がある。

実装のポイント

• 避難所のリスト \(P\) はソートされている前提なので、二分探索が使える。
• bisect_left の結果が 0 や M になる端のケースにも注意（左端や右端の避難所しか存在しない場合）。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
import bisect
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    X = list(map(int, data[2:2+N]))
    P = list(map(int, data[2+N:2+N+M]))
    
    result = []
    for x in X:
        # 二分探索でx以上の最小の避難所を探す
        idx = bisect.bisect_left(P, x)
        min_dist = float('inf')
        
        # x以上の最小の避難所
        if idx < M:
            min_dist = min(min_dist, abs(x - P[idx]))
        # x未満の最大の避難所
        if idx > 0:
            min_dist = min(min_dist, abs(x - P[idx - 1]))
            
        result.append(min_dist)
    
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。