かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC144 F - Fork in the Road

競技プログラミング 解説 ABC グラフ 動的計画法 期待値

問題はこちら

問題概要

{2\le N\le 600}頂点{N-1\le M\le \frac{N(N-1)}{2}}辺の閉路のない有向グラフ(=DAG)が与えられる. 頂点{1}から辺をたどって頂点Nに行くことを考える. 各頂点から出ている辺から等確率でランダムに選び進む. このグラフから一つだけ辺を取り除けるとき頂点{N}に到達するまでに通る辺の数の期待値の最小値を求めよ.

思考の流れ

まず辺を取り除かない場合の期待値は, グラフがDAGであることからDPで求められる. 具体的には{dp[i]}を「頂点{i}から{N}までに通る辺の数の期待値の最小値」として

{\displaystyle dp[N]=0}

{\displaystyle dp[i]=\frac{\displaystyle \sum_{j\in E_i}{dp[j]}}{|E_i|}+1}

となる.

{\downarrow}

1つの辺を取り除いたあと, その辺以降の頂点のDPの値は変わらない. その辺以前の頂点のDPの値を再計算する. すべての辺に対してその辺を取り除いたときの値を考えると計算量は{O(M^2)}かかり間に合わない.

{\downarrow}

よく考えると, 一つの頂点に対してその頂点から出る辺の先の頂点のDPの値が最も高いものを削除するのがいいことがわかるので, 各頂点に対して一つの辺のみ考えればいい. 計算量は{O(NM)}となり間に合う.

提出プログラム

https://atcoder.jp/contests/abc144/submissions/12454169

感想

すんなりわかってよかった.