Magentorの日記

緑以下コンテストEx - E Moving up

https://yukicoder.me/problems/no/2573

$O(W^2 \log^2{W})$ で解くことが可能です。

想定解法ではそれぞれの駒からそれぞれのマスへ少なくとも $W^2$ 本の辺を貼る必要があるので、これを削減することを考えます。

$f(i,j)$ をコマ $i$ が $(1,j)$ へ移動するのに必要な最小のコストとします。

$f(i,j)$ は $j$ について傾きが $-1,0,1$ と変化する区分線形関数となっています。よって、この問題は頂点 $S,T,A_1,A_2,\dots,A_W,B_1,B_2,\dots,B_W$ からなり、以下のように辺が貼られているグラフの $S$ から $T$ への最小費用流に帰着されます。

頂点 $S$ から頂点 $A_i$ への容量 $1$ , コスト $x_i-1$ の辺
頂点 $B_i$ から頂点 $T$ への容量 $1$ , コスト $0$ の辺
頂点 $B_i$ から頂点 $B_{i+1}$ への容量 $\infty$ , コスト $1$ の辺
頂点 $B_{i+1}$ から頂点 $B_{i}$ への容量 $\infty$ , コスト $1$ の辺
頂点 $A_i$ から頂点 $B_j$ への容量 $1$ , コスト $0$ の辺 ( $j$ はコマ $i$ が右上か左上への移動のみで $(1,j)$ に到達できるようなものとする )

このままでは辺数が $O(W^2)$ になりますが、 $5$ 行目の $j$ として考えられるものが区間の形になっていることに注目すれば、区間に辺を貼るテクによって辺数が $O(W \log W)$ となるので、計算量 $O(W^2 \log^2{W})$ でこの問題を解けました。