概要

\(N\) 個の荷物それぞれに対して、\(M\) 箇所の配送センターの中から最も近いものを選び、距離の合計を最小化する問題です。各荷物は独立に最寄りの配送センターを選べばよいため、二分探索を用いて効率的に解けます。

考察

重要な気づき：各荷物は独立に最適な配送センターを選べる

求める値は \(\sum_{i=1}^{N} |D_i - S_{f(i)}|\) の最小値です。この式をよく見ると、各荷物 \(i\) の項 \(|D_i - S_{f(i)}|\) は他の荷物の割り当てに一切影響を受けません（1つの配送センターが複数の荷物を担当してもよいため）。したがって、各荷物について個別に最も近い配送センターを選べばよいのです。

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

各荷物 \(i\) に対して全配送センター \(j\) を調べて \(|D_i - S_j|\) の最小値を求めると、計算量は \(O(N \times M)\) です。\(N, M\) がともに最大 \(2 \times 10^5\) の場合、\(4 \times 10^{10}\) 回の計算が必要となり、制限時間に間に合いません（TLE）。

解決策：ソート＋二分探索

配送センターの座標をソートしておけば、各荷物の届け先 \(D_i\) に最も近い配送センターを二分探索で \(O(\log M)\) で見つけられます。

具体例で説明します。配送センターが \(S = [1, 5, 8]\)（ソート済み）で、届け先が \(D_i = 6\) の場合：

• 二分探索で \(6\) の挿入位置を求めると \(\text{pos} = 2\)（\(S[2] = 8\) が \(6\) 以上の最小の要素）
• 右側の候補：\(S[2] = 8\) → 距離 \(|6 - 8| = 2\)
• 左側の候補：\(S[1] = 5\) → 距離 \(|6 - 5| = 1\)
• 最小は \(1\) なので、配送センター \(5\) を選ぶ

アルゴリズム

1. 配送センターの座標 \(S\) をソートする。
2. 各荷物の届け先 \(D_i\) について以下を行う：
   • bisect_left で \(D_i\) のソート済み配列 \(S\) における挿入位置 \(\text{pos}\) を求める。
   • \(S[\text{pos}]\)（\(D_i\) 以上で最小の値）と \(S[\text{pos}-1]\)（\(D_i\) 未満で最大の値）の2つが最寄り候補。
   • 境界チェック（\(\text{pos} = 0\) や \(\text{pos} = M\) の場合）をした上で、距離が小さい方を選ぶ。
3. 各荷物の最小距離を合計して出力する。

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  • 配送センターのソートに \(O(M \log M)\)、各荷物に対する二分探索に \(O(\log M)\) × \(N\) 回
• 空間計算量: \(O(N + M)\)
  • 入力データの格納に必要な分

実装のポイント

• 境界チェックが重要: 二分探索で得た挿入位置 \(\text{pos}\) が \(0\) の場合は左側の候補がなく、\(M\) の場合は右側の候補がありません。両方のケースを正しく処理する必要があります。

• 高速入出力: \(N, M\) が大きいため、Python では sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

• 距離の計算の工夫: \(S\) はソート済みなので、\(S[\text{pos}] \geq D_i\) かつ \(S[\text{pos}-1] < D_i\) が成り立ちます。そのため絶対値を取らずに S[pos] - d と d - S[pos-1] で距離を計算でき、わずかに効率的です。

  ソースコード

import bisect
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    D = [int(input_data[idx + i]) for i in range(N)]; idx += N
    S = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    S.sort()
    
    total = 0
    for d in D:
        pos = bisect.bisect_left(S, d)
        best = float('inf')
        if pos < M:
            best = min(best, S[pos] - d)
        if pos > 0:
            best = min(best, d - S[pos - 1])
        total += best
    
    print(total)

main()

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