Codeforces Round 986 (Div. 2)

　Dまで四完。Eは実装間に合わず。

コンテストへのリンク

コンテスト後のツイート

D 頭がこんがらがるけど、ある数字を取ったときq,j,kのどの数字まで使えるか遷移を考えれば良い。SortedSetをお借りしたけど、dequeで良かったかも？
E 一本道の場合、1,n-1/n,n-2/n,...,1/n,0となることを利用する。一番近い葉までの距離が分かればいけると思ったけど、実装間に合わなかった。

— titia (@titia_til) November 10, 2024

E. Alice's Adventures in the Rabbit Hole

　ツイートした方法であっていた。

　単純に、トポロジカルソート順にDPの値を更新していく……とかじゃなく、枝分かれしたら、そこから一番近い葉まで一気に値が決まる、みたいな感じなので実装に戸惑ったことが間に合わなかった原因か。

　トポロジカルソート順でも、どこから値が伝搬してきているか？　みたいなのを持てばできるとは思ったけど、それもちょっと大変。