概要

各荷物の届け先と配送センターの位置が与えられ、すべての荷物の配送コストの合計を最小化する問題です。

考察

素朴なアプローチでは、各荷物に対してすべての配送センターを試すと \(O(N \times M)\) の計算量となり、制約条件（\(N, M \leq 2 \times 10^5\)）では最大40億回の計算が必要になるため、実行時間制限に間に合いません。効率的な解法が必要です。

重要な観察として、最適な割り当てでは各荷物は最も近い配送センターから配送されるべきです。しかし、すべての荷物と配送センターの組み合わせについて最近傍を求めるのは計算量が大きすぎます。そこで、配送センターと荷物の届け先をソートし、両方を順に走査することで効率的に最近傍を求めることができます。

アルゴリズム

1. 配送センターの座標 \(S\) と荷物の届け先 \(D\) をそれぞれソートします。
2. 配送センターのインデックス \(j\) を0で初期化します。
3. 各荷物 \(d\)（ソート済み）について、現在の配送センター \(S_j\) と次の配送センター \(S_{j+1}\) を比較します：
   • \(|d - S_j| \geq |d - S_{j+1}|\) の場合、次の配送センターの方が近いので \(j\) をインクリメントします（ただし \(j < m-1\) の範囲内で）。
   • この条件が満たされなくなるまで \(j\) を進め、最終的に最も近い配送センター \(S_j\) を見つけます。
4. 各荷物について見つけた最近傍の配送センターまでの距離を合計に加算します。

このアプローチでは、配送センターのリストを一度だけ走査しながら、各荷物に対して最も近い配送センターを効率的に見つけることができます。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • ソートに \(O(N \log N)\) と \(O(M \log M)\)、走査に \(O(N + M)\) かかります。
• 空間計算量: \(O(N + M)\)
  • 配列 \(D\) と \(S\) を格納するためのメモリです。

実装のポイント

• 配送センターと荷物の両方をソートすることで、効率的な走査が可能になります。

• 配送センターのインデックス \(j\) はリセットせずに維持します。これはソートされた配送センターと荷物の位置関係を利用して、前の荷物で見つかった最近傍配送センターのインデックスから探索を開始できるためです。

• 条件 abs(d - S[j]) >= abs(d - S[j+1]) は、現在の配送センターよりも次の配送センターの方が近いか等しい場合に真となります。等号を含めることで、同じ距離の場合は次のセンターに進みます（どちらを選んでもコストは同じですが、進行方向の整合性を保ちます）。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    D = list(map(int, data[2:2+n]))
    S = list(map(int, data[2+n:2+n+m]))
    
    S.sort()
    D.sort()
    
    total = 0
    j = 0
    for d in D:
        while j < m - 1 and abs(d - S[j]) >= abs(d - S[j+1]):
            j += 1
        total += abs(d - S[j])
    
    print(total)

if __name__ == "__main__":
    main()

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