AtCoder Beginner Contest 314

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 314 Fまで。
D t!=1については最後のクエリのみ採用
E 期待値DP。0に注意して計算
F 木を構築していく。合併させたら新しいノードを作る。各ノードに親ノードを作るときの勝率を書き込んでいき、親方向から累積和を取れば答え。

— titia (@titia_til) August 12, 2023

G - Amulets

　解説放送を見てAC。

　コンテスト中に、i番目までのモンスターまで倒すことを考えるなら、アミュレットは各タイプに関する攻撃力の和が大きいものから選べば良いことは分かっていた。なので、各Kに対してNを二分探索するTLE解法は思いついていた。

　そこまでいけば、後は差分計算するしかないはずなのだが、なぜ思いつかなかったのか。Kそれぞれの場合について求めるというのも差分計算を示唆する書き方である。

　Kではなく、モンスターの数で差分計算するという部分にちょっとした発想は必要だけど、（分かってしまえば）そこまで難しい発想とは思えないのだけど……。

　なお、実装にも苦労した。

さっきのABCのG、新ジャッジのsortedcontainersを使って通した。https://t.co/0641kZKgMt
tatyamさんのSortedSetをお借りしたらTLEして困ってたけど、tatyamさん自身が「N > 2e5 なら tatyam 木より速い」と書いていたのを思い出したので。
新ジャッジだとこういうことができるんですね！ https://t.co/9UiEQopTfK

— titia (@titia_til) August 12, 2023

　こうやってsortedcontainersを使ったので、手元でもsortedcontainersを使えるようにした。