Day 034-Q5 | オンライン最小費用流 (MCMF + Slope Trick)

問題

$N$ 個の荷物 (位置 $a_i$) と $N$ 個の倉庫 (位置 $b_j$) がある。荷物 $i$ を倉庫 $j$ に運ぶコストは $|a_i - b_j|$。各荷物を異なる倉庫に1つずつ割り当て、総コストを最小化せよ。

さらに $Q$ 個のクエリで荷物と倉庫が各1つずつ追加され、追加ごとの最小コストを出力する。

制約

$1 \le N, Q \le 10^5$

$1 \le a_i, b_j \le 10^9$

全座標は1次元数直線上

入出力例

入力例 1

出力例 1

3
3
5

初期: |1-2|+|3-4|+|5-6|=3

★ 1次元最小コスト完全マッチング定理

荷物列 $A$ と倉庫列 $B$ を それぞれソート し、ソート後の $i$ 番目同士をマッチングする割り当てが最小コスト。

証明 (隣接の引数): $a_1 < a_2, b_1 < b_2$ のとき $$|a_1-b_1| + |a_2-b_2| \le |a_1-b_2| + |a_2-b_1|$$ が成り立つ。任意の割り当てから「逆順ペア」を解消する操作でコストが下がる。

概念図: ソート → 1対1対応

対話デモ: 1次元マッチング

荷物 $A$:
倉庫 $B$:

ヒント (段階的開示)

ヒント1: 1次元の特性

ソート済み配列の $i$ 番目同士のマッチングが最適 (隣接の引数で証明)。

ヒント2: 動的更新

新要素 $a, b$ を追加するとソート位置に挿入され、マッチングがシフト。差分列 $D_i = \text{sorted}_A[i] - \text{sorted}_B[i]$ の変化を追跡。

ヒント3: Slope Trick

$\sum |D_i|$ の動的管理は 左右ヒープによる中央値管理 や Slope Trick で $O(\log N)$ 更新可能。

模範解答

明快版 (bisect.insort)

Slope Trick (概念)

import sys
from sys import stdin
import bisect

def main():
    data = stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    A = sorted(int(data[idx+i]) for i in range(N)); idx += N
    B = sorted(int(data[idx+i]) for i in range(N)); idx += N
    Q = int(data[idx]); idx += 1

    # 初期コスト
    print(sum(abs(A[i] - B[i]) for i in range(N)))

    a_list = list(A)
    b_list = list(B)
    out = []
    for _ in range(Q):
        na, nb = int(data[idx]), int(data[idx+1]); idx += 2
        bisect.insort(a_list, na)
        bisect.insort(b_list, nb)
        cost = sum(abs(a_list[i] - b_list[i]) for i in range(len(a_list)))
        out.append(str(cost))

    print('\n'.join(out))

main()

# Slope Trick による O((N+Q) log N) の概念実装
# 差分列 D を SortedList で管理し、挿入位置とシフトを差分更新する
# 完全実装は long; ここでは骨格のみ
import bisect
from sortedcontainers import SortedList

def solve_slope_trick(A, B, Q_data):
    sa = SortedList(A)
    sb = SortedList(B)
    # 初期コスト = Σ|sa[i] - sb[i]|
    total = sum(abs(sa[i] - sb[i]) for i in range(len(sa)))
    results = [total]

    for na, nb in Q_data:
        pa = sa.bisect_left(na); sa.add(na)
        pb = sb.bisect_left(nb); sb.add(nb)
        # 挿入で D[pa..]、D[pb..] のシフトが発生
        # 詳細: 影響範囲は [min(pa,pb), max(pa,pb)] 程度
        # → スキップ部分以外の差分を BIT or SortedList で更新
        # (省略: 実装は問題依存で複雑)
        total = sum(abs(sa[i] - sb[i]) for i in range(len(sa)))
        results.append(total)
    return results

Step-by-Step 解説

11次元マッチング定理
荷物・倉庫をそれぞれソート → インデックス順に対応で最適。隣接の引数で証明。

2動的更新戦略
新要素は bisect.insort で挿入。挿入によりマッチングがシフトする。

3Slope Trick による高速化
$\sum|D_i|$ を左右ヒープで管理。挿入位置からのシフトを差分で処理し $O(\log N)$ 更新。

4計算量改善
素朴: $O(NQ)$ → Slope Trick: $O((N+Q)\log(N+Q))$

計算量

素朴 (insort + 再計算): $O(N \log N + Q(N + \log N)) = O(NQ)$
Slope Trick (理想): $O((N+Q)\log(N+Q))$
定数倍は Slope Trick が重め → Python では $N, Q \le 10^4$ 程度なら素朴で十分

よくあるミス

ミス	原因	正しい書き方
ソートせずマッチング	最適割り当てが自明ではないと思う	定理を信頼し、両方ソート後にインデックス順
追加後の全再計算	差分更新の複雑さ	小 N なら全再計算で正確性を保証してから最適化
$\|D\|$ 総和の更新誤り	挿入位置のシフトを忘れる	`bisect.insort` で挿入位置を正確管理
初期コストの出力忘れ	クエリ前の状態出力	初期配列のコストも別途出力

次のステップ

発展: 各荷物の容量制限 ($A_i$ 荷物を最大 $c_i$ 個まで送れる) → 真の最小費用流
応用: 輸送問題 (Transportation Problem) の LP 双対と MCMF の対応

自己評価

完全理解おおむね理解要復習

Day 034-Q5 — オンライン最小費用流 (MCMF + Slope Trick融合)

問題

制約