1/29 日記

今日は眠いので寝る

明日起きたらコドフォバチャしようかな

・F - Fork in the Road (atcoder.jp)

いつもの、という感じの問題だった。

メモ化再帰をするけど、削除する辺を全探索するとO(M^2)とかになって厳しいので、

削除する辺の始点を全探索すればよく、O(NM)になる。

解説にはO(M)もあった（期待値と一緒に確率もメモしていくやり方。普通の式変形で解けるからそこまで難易度は高くない気もする）。

最近は睡眠欲とぎゅー欲がすごい。

欲望に忠実に生きる。