Monge グラフ上の d-辺最短路長を計算するアルゴリズムの補題１の別証明を考える

列 \(x=(x_1,x_2, \ldots, x_n)\) と列 \(y=(y_1,y_2, \ldots, y_m)\) をマージしてソートした列を \(z=(z_1, z_2, \ldots, z_{n+m})\) とする。また、偶奇に従って要素を抜き出して \(z_{o}=(z_1, z_3, \ldots), z_{e}=(z_2, z_4, \ldots)\)と置く。

定理：\(c\) が Monge とする。\(x_0=y_0,x_n=y_m\) ならば \(c(z_o)+c(z_e)\leq c(x)+c(y)\)

証明：Mongeの定義より、列をソートしても \(c\) は増加しないので、\(x, y\) はソートされているとしてもよい。\(x_{i} < y_{j} \leq y_{j+1} < x_{i+1}\) を満たす \(i, j\) が存在するならば、\(x, y\) を \((x_1, \ldots, x_i, y_{j+1}, \ldots, y_m), (y_1, \ldots, y_j, x_{i+1}, \ldots, x_n)\) で置き換えても \(c(x) + c(y)\) は増加しない。\(x\), \(y\) を入れ替えても同様。この操作を繰り返すと、\(x, y\) は \(z_o, z_e\) になる■

コメント１：\(k\ (\geq 3)\) 個の列に対しても、\(\bmod k\) で分類すると同様の事実が成り立つ。

コメント２：\(||x||\) を列の長さとする。列 \(x, y\) の重み \(c(x), c(y)\) が等しいとき \(||x|| \leq k \leq ||y||\) を満たす任意の \(k\) について、長さ \(k\) で \(x, y\) と重みの等しい列が二分探索により \(O((||x||+||y||)\log k)\) で取れる。Alien DP の復元など。