概要

各家の位置と避難所の位置が与えられるので、各家から最も近い避難所までの距離を求める問題です。

考察

各家に対して最も近い避難所を見つけるには、単純にすべての避難所との距離を計算すると \(O(N \times M)\) の時間がかかり、\(N, M\) が最大 \(2 \times 10^5\) であるため、\(4 \times 10^{10}\) 回の計算が必要となり、実行時間制限に間に合いません。

しかし、家の座標 \(X_i\) と避難所の座標 \(P_j\) はどちらもソートされているという重要な性質があります。この性質を利用すると、二分探索によって効率的に最も近い避難所を見つけることができます。

アルゴリズム

1. 家の座標リスト \(X\) と避難所の座標リスト \(P\) を入力として受け取ります
2. 各家 \(x\) について、二分探索（bisect_left）を用いて \(x\) が挿入されるべき位置 \(idx\) を \(P\) の中で探します
3. 見つかった位置 \(idx\) に基づいて、以下の3つのケースで処理します：
   • \(idx = 0\) の場合：\(x\) より左側の避難所はないので、最初の避難所 \(P[0]\) との距離を計算
   • \(idx = len(P)\) の場合：\(x\) より右側の避難所はないので、最後の避難所 \(P[-1]\) との距離を計算
   • それ以外の場合：\(x\) の左右にある2つの避難所 \(P[idx-1]\) と \(P[idx]\) との距離を計算し、小さい方を採用
4. 計算結果を出力用リストに追加し、最後にまとめて出力します

計算量

• 時間計算量: \(O(N \log M)\)
  • 各家に対して二分探索を行うため、\(N\) 回の探索それぞれに \(O(\log M)\) の時間がかかります
• 空間計算量: \(O(N + M)\)
  • 家の座標リスト \(X\) と避難所の座標リスト \(P\) を格納するためのメモリが必要です

実装のポイント

• Pythonの標準ライブラリ bisect を使用することで、効率的に二分探索を実装できます

• 境界条件（最初と最後の要素）に注意して処理する必要があります

• 出力は文字列としてまとめてから一度に出力することで、高速化できます

  ソースコード

import bisect

def main():
    import sys
    data = sys.stdin.read().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]))
    
    res = []
    for x in X:
        idx = bisect.bisect_left(P, x)
        if idx == 0:
            d = P[0] - x
        elif idx == len(P):
            d = x - P[-1]
        else:
            d1 = x - P[idx-1]
            d2 = P[idx] - x
            d = min(d1, d2)
        res.append(str(d))
    
    print("\n".join(res))

if __name__ == "__main__":
    main()

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