https://atcoder.jp/contests/abc144/tasks/abc144_f
洞窟があり、その構造はそれぞれの部屋を頂点とした$N$頂点$M$辺のDAGになっている。部屋0から出発して、部屋$N$を目指す。ここで、各部屋ではその部屋から伸びる辺をランダムにひとつ選んで進むことを繰り返す。
出発する前に好きな辺をひとつ消せるとき(消さなくてもよい)、部屋$N$に到達するまでに通る辺の数の期待値の最小値を出力せよ。
辺を消さないときの期待値は、DAG上をDFSしながら、各頂点で隣接している頂点での期待値を全部足して隣接している頂点の数で割り、最後に1を足すことで求められる。
ある頂点から伸びる辺を消すとき、その頂点に隣接している頂点のうち期待値が最も大きい頂点への辺を消すのが良い。よって、どの頂点からの辺を消すかを全探索すればO($NM$)でこの問題が解ける。隣接する頂点がひとつしかない頂点では辺を消せないことに注意（$N$に到達できなくなるため）
惜しかった。ほとんど解法めいたものがわかっていたが実装時間が足りなかった。強いて言えばE問題で入力の受け方を間違えて無駄に時間を溶かしたことが敗因か。想定解と少し違う方法でやろうとしていたのでもう少し時間があったらできていたかどうかは不明といえば不明。辺を消さない場合の期待値がすぐわかったのは成長っぽい。