ABC144 F - Fork in the Road (600)
コンテスト中
ある辺を消した場合の期待値を求めるのは$ O(M)
すべての点で試すと$ O(M \times M) = O(M^2)で間に合わないが高速化が思いつかない
$ s \le tの条件を完全に見逃していた
解説を見て
$ s \le tなので、DAGになっていてかつ1から順に既に並んでいることになる
N以外の各点から辺が出てるので、それらのすべての点からNに必ず到達できる
閉路も当然存在しないので後ろから見ていくとNまで行くためのその点からの期待値が簡単に計算できる
その点のすべての次の点での期待値の平均値に1を足すだけ
平均値なので、その点からの辺を消す場合は一番大きい辺を消すのが最も期待値を小さくできる
ある辺を消した場合の期待値を求めるのは変わらず$ O(M)
点を消すパターンはすべての点から1つの辺を選ぶパターンだけなので$ O(N)、なので全体で$ O(NM)
どの辺も消さないパターンが最小値になるのはある点からどの辺を通っても期待値が同じ場合
この場合、逆にどの辺を消した場合でも最小値になるので考えない