概要
解法
$K=1$ に帰着します。次のような問題が解ければよいです。
点 $X_0, \ldots, X_N$ （$X_i \leq X_{i+1}$）がある。各点は赤または青である。赤点から青点へのマッチングの費用を最小化せよ。
これは、次のような最小費用流として定式化できます。
- $X_i$ と $X_{i+1}$ の間：容量 $\infty$、コスト $|X_i {}-{} X_{i+1}|$
- source から赤い点へ流量 $1$ 流す
- 青い点から sink へ容量 $1$ の辺を張る
次のように関数 $f_i$ を定めます。
- $f_i(x)$：$X_{i-1}$ から $X_i$ に向かう流量が $x$ であるときの、その辺まで考慮した最小費用
初期条件は $f_0(x) = \begin{cases}0 & (x=0)\\ \infty & (x\neq 0)\end{cases}$、答は $f_{N+1}(0)$ です。
遷移は以下の通りです：
- 赤い点：$f_{i+1}(x) = f_i(x-1) + d_i|x|$
- 青い点：$f_{i+1}(x) = \min_{y\in [x,x+1]} f_i(y) + d_i|x|$ （$d_i = X_{i+1}-X_i$）
これらは slope trick の凸共役における基本操作 なので解けます。
一応、凸共役 $f^{\star}$ に対する操作列として書き下しておきます。
$f^{\star}(p) = 0$ で初期化します。赤い点での $1$ 平行移動は、$f^{\star}(p)$ に $p$ を加える操作です。青い点での $\min_{y\in [x,x+1]} f(y)$ は、$f^{\star}(p)$ に $(0-p)_+$ を加える操作です。赤青どちらも $d|x|$ を加える操作がありますが、これは $f^{\star}$ において「左側集合」に $-d$、「右側集合」に $d$ を加える操作です。これらを全て行ったあと、$f(0) = -\min_{f^{\star}}$ を答えればよいです。
