日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）

　Eまで五完。

コンテストへのリンク
コンテスト後のツイート

日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303） Eまで。EXでケーリーの公式の証明を眺めたが分からず、Fの二分探索後の判定が上手くできず終了。
B setで管理
C シミュレーション
D DP
E まず次数3以上の頂点を除く

— titia (@titia_til) May 27, 2023

F - Damage over Time

　自力AC。

　答え二分探索。どの呪文を優先して使うかは、$t_i*d_i$が大きい順にソートしておく。さらに、同じ$d$なら長い$t$のものだけを使うといった枝狩りもする。

　あとは、時間Dの間に最大何ダメージ与えられるか？　を計算できれば良い。

　次の呪文に移るべきタイミングは計算できるので、x日～y日までで何ダメージ与えられるか？　が求まればよく、これは、全体（$t_i$日全てダメージを与えたとき）から、実際はダメージを与えられない日が最大何日・最小何日かを計算し、その平均を引けば良い。

　コンテスト中もこの方針で考えていたが、最後の立式で混乱し、一時間考えてもサンプルが合わなかった。が、今やったらあっさりACすることができて不思議な気持ちになった。

　時間が経って頭が整理されたのかなぁ。

 G - Bags Game

　解説AC。

　区間DPを高速化すれば良いという方針自体は（自分は解説を見てしまったが）分かりやすいが、実装がとにかく大変だった。

　添え字を合わせるのがしんどいだけでなく、自分のセグ木による実装だとPyPyでは通らず、RUSTに直してなんとかACした。

　方針は簡単だがACするのは非常に厳しい問題なので、AC人数が伸びなかったのもよく分かる。