37.50.48

%20 の ブログ

KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing)

この記事は KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing) の解説です。

いくつかの解法があるらしいがこの解法で fastest(33ms)になった(出題されてからジャッジ環境が変化しているのであまりフェアな比較ではない)。

問題文のストーリーに従うのならばクエリが与えられる毎に答えを求める必要があるが、ストーリーを無視すればクエリを先読みして後ろから順に処理できる。
辺が減っていくのを後ろから順に見ると辺が増えていくことになるので UnionFind が使える。
辺が全くない状態から辺を増やしていきたいので、入力で \(x_i\) として出現しない頂点(根は除く)を \(x_{Q+1},x_{Q+2},\cdots,x_{N-1}\) に追加しておく。
元のグラフの部分グラフであるような各連結成分に対し、元のグラフのある葉からその連結成分の根までの移動コストの最小値は次のような DP で求められる。

初期化

\(\begin{eqnarray} dp[v] := \begin{cases} 0&(頂点vが葉である) \\ \infty&(頂点vが葉でない) \end{cases} \end{eqnarray}\)

頂点 \(v\) が属する連結成分の根を \(r[v]\) とする。
\(r[v] := v\)

(すべての辺が使えるときの)根(頂点 \(1\) )から頂点 \(v\) までの移動コストを \(s[v]\) とする(これは累積和の要領で求まる)。
\(\begin{eqnarray} s[v] := \begin{cases} 0&(頂点vが根である) \\ s[p_v]+w_v&(頂点vが根でない) \end{cases} \end{eqnarray}\)

更新

\(find\) 関数を UnionFind の再帰的に代入するやつとする。
頂点 \(x\) と頂点 \(p_x\) の間に辺を張るとき、\(R := find(p_x)\) とすると
\(dp[R] := {\rm min}(dp[R],dp[x]+s[x]-s[R])\)
\(r[x] := R\)

元の問題では辺が減った後の移動コストの最小値を問われているので、後ろから見たときは辺が増える前の移動コストの最小値 \(dp[1]\) をその時点での答えとすればよい。

実装例