DDCC2020本戦-B : Hawker on Graph

こういう非自明な例が出てくると理解が進んで助かる。(間違ってたら教えてください)

問題

解法

　解説の議論を追っていくことにしよう。

単に足していくだけだったら...

　まず最初に、重み $w$ の辺を通るごとに所持金が $w$ だけ増え、負になることもあり得る場合を考えよう。この場合は、 $dp _ {u,v,k}$ を「頂点 $u$ から頂点 $v$ に $k$ 回の移動で向かうときの所持金の最大値」とすれば、遷移式は

$dp _ {u,v,k+1} = \max (dp _ {u,x,k} + dp _ {x,v,1})$

と書ける。 $k+1$ 回目で $v$ に行くので、 $k$ 回目にどこにいるかで全探索していることになる。
　ところで、この遷移式をよく見てみると、右辺が行列積の形をしている気がしてくる。例えば $\max$ を加算、その中の加算を乗算に置き換えてみると、これは実行列の四則演算における積の計算そのものである。 $\max$ と加算の場合も、同様に行列を用いて計算ができる。元の問題に立ち返れば、加算はグラフ上でパスを伸ばしていく演算であり、 $\max$ は互いに素なパスの結果をまとめる演算ということになる。
　遷移が行列で書けるということは、行列累乗による高速化を検討したくなる。行列累乗に持ち込むには、2つの演算に「結合則」(演算を行う順番を変えても結果が変わらないこと、交換則とは違う！)と、加算に交換則が成り立つこと、分配則が成り立っている必要があるが、 $\max$ と加算はもちろんそれが成り立っている。そういうわけで、この場合は $O(N ^ {3} \log K)$ で解くことができる。

元の問題の解法

　元の問題では、所持金 $x$ のときから重み $w$ の辺を通ると所持金が $\max(x+w,0)$ となる。この変化を行列累乗に持っていくことを考えよう。そのためにまず、この所持金の変化の関数を $\max(x+a,b)$ と見て、行列の各要素に $(a,b)$ のペアを持たせることにする。次に、上述した行列積に落とすのに必要な2つの演算を考えよう。まずパスを伸ばす演算を考える。 $f = \max(x+a,b)$ 、 $g = \max(x+c,d)$ とすると $g \circ f = \max(\max(x+a,b)+c,d)$ となる。ここで $x+a \leq b$ のときは $\max(b+c,d)$ となり、 $x+a \gt b$ のときは $\max(x+a+c,d)$ となる。これをまとめると

$g \circ f = \max(\max(x+a,b)+c,d) = \max(x+a+c,\max(b+c,d))$

となり、これはたしかに合成前の関数と同じ形をしている。
　次に、パスをまとめる演算を考える。これ $\max(x+a,b)$ と $\max(x+c,d)$ の $\max$ ということになるが、 $x$ のある方を使うなら $a$ と $c$ の大きい方、使わないなら $b$ と $c$ の大きい方が関わるので、単に $\max(x+\max(a,c),\max(b,d))$ でよい。これも合成前と同じ形をしている。
　今定義した2つの演算はどちらも結合則と分配則を満たし、パスをまとめる演算は交換則を満たすことがわかるので、これらの演算をもとに行列累乗が可能である。