概要

家と避難所がどちらも座標順に並んでいることを利用し、各家について「最寄りの避難所までの距離」を高速に求めます。

考察

最も素朴には、各家 \(X_i\) について全ての避難所 \(P_j\) を見て \(\min_j |X_i-P_j|\) を計算できます。しかしこれは \(O(NM)\) となり、最大で \((2\times 10^5)^2\) になってしまい確実に TLE です。

重要な観察は次の2点です。

• 家の座標 \(X_1<X_2<\cdots<X_N\)、避難所の座標 \(P_1<P_2<\cdots<P_M\) はどちらも昇順にソート済み。
• 家を左から右へ見ていくと、「最寄りの避難所の番号」は左に戻らず、同じか右へしか動きません（単調性）。

直感的には、家が右へ動くほど、最寄りの避難所も右側のものが有利になりやすく、すでに「近くない」と分かった左側の避難所が急に最適になることはありません。
この単調性のおかげで、避難所のポインタを一方向に進めるだけで全ての家を処理できます。

例：避難所が \(P=[2,10,20]\) のとき、家が \(x=1,5,12,19\) と右へ進むにつれ、最寄りはそれぞれ \(2,2,10,20\) のように右へ（または据え置きで）変化し、左へは戻りません。

アルゴリズム

「しゃくとり法（2ポインタ）」で解きます。

1. 避難所の添字 \(j\) を \(0\)（一番左の避難所）から開始します。
2. 家を左から順に（\(X\) を昇順に）見ていき、現在の避難所 \(P_j\) と次の避難所 \(P_{j+1}\) のどちらが近いかを比較します。
3. もし \(|x-P_{j+1}| \le |x-P_j|\) なら、次の避難所の方が同じかより近いので \(j \leftarrow j+1\) と進めます。
4. これ以上近くならなくなるまで（条件が成り立たなくなるまで）\(j\) を進めたら、その時点の \(|x-P_j|\) が最小距離です。
5. 次の家に進みます（\(j\) は戻さずそのまま使い回す）。

ポイントは、家 \(x\) が右へ進むと「\(P_{j+1}\) の方が近い」と判定される境界も右へ進むため、\(j\) を全体で高々 \(M-1\) 回しか増やさないことです。よって全体が線形時間で終わります。

（コード中の <= は、ちょうど中点で距離が同じ場合に右側へ進めるための処理です。どちらでも最小距離自体は同じですが、こうしておくとポインタが自然に右へ寄っていきます。）

計算量

• 時間計算量: \(O(N+M)\)（\(j\) は全体で最大 \(M-1\) 回しか増えない）
• 空間計算量: \(O(1)\)（出力を除く。配列入力分は別途保持）

実装のポイント

• 入力サイズが大きいので sys.stdin.buffer.read() でまとめて読み込むと高速です。

• while j + 1 < M を忘れると配列外参照になるので注意します。

• abs(x - P[j]) と abs(x - P[j+1]) の比較だけでよく、二分探索（\(O(N\log M)\)）よりも速い \(O(N+M)\) 解法になります。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    X = data[2:2 + N]
    P = data[2 + N:2 + N + M]

    j = 0
    out = []
    for x in X:
        while j + 1 < M and abs(x - P[j + 1]) <= abs(x - P[j]):
            j += 1
        out.append(str(abs(x - P[j])))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。