2週間分まとめて記事書いてたけどいちいち下書き開くの面倒なので
ABC404
ooooo-o 93:21 + 1ペナ 321位
A問題
STLとか使うと速そうだが、書き方を覚えていなかった（完） 00:59
B問題
グリッドの回転面倒...... 06:06
C問題
全ての次数が2+連結成分の個数が1 を判定すればOK 後者はDSUを使わせてもらう 09:51
D問題
動物園を3回訪れるのは無駄なので、0～2回の範囲でそれぞれ何回行くかDFS
310=59049通りなので間に合う 19:06
E問題
最初迷走する。移動させるなら最も0までのたどる個数が少ないところで良い？みたいな思い違いをして1WA。 Gを解き終わった後見てみると、使う皿の最小化問題と言い換えてよいことに気付き「dp[i]=i番目の皿を最後の中継地点にしたとき、使用される皿の数の最小値」としてDPを行うとよいと分かる。 93:06
F問題
DP[iターン残っている][現在K点]=確率 として、手持ちのボタンを押すチャンスM回をどう割り振るかをやれば良さそうだと考えたが、多分M回を全探索していてはよくなさそう。押せるボタンはだいたい0になりそうだがそれでも通り数は多い......?
G問題
順位表を見るとFよりGの方が解かれていたので先にこちらに手を付ける。
累積和を取ると x[j]-x[i]=S という形の制約が大量に与えらえる問題になるので、これは2変数の間しか式がないため牛ゲーのフレームワークに落ちる。 最近線形計画法についてまとめていたのがよかった。
感想
E詰まりすぎ
