競プロの過去問埋めを少しやった。

ABC330-A: やるだけ

ABC330-B: やたらめんどくさい問題文だが、clampするだけだった。

ABC330-C: 尺取りしつつchmin

ABC330-D: 愚直にやると$O(N^4)$になるが、適当に式変形すれば$O(N^2)$になる。

ABC330-E: 各値の存在数を管理した上でsetを使えばmexは普通に出せるので、やるだけ。

ABC330-F: サイズをぶたんする。あるサイズに収めるために必要なコストがK以下かどうかで判定すればよい。あとはコストの計算をどうするかの話になる。

ちょっと考えればxとyは完全に独立して考えられることが分かる。そして数直線上の点群における各点となんかとの距離の総和、みたいなやつは割と頻出問題で、$f(なんかの位置)=距離の総和$という関数はだいたい下に凸な折れ線グラフになる。この形の底を探せばよい。これはなんかの両側にある点の数が等しくなるポイントを探せばよく、あらかじめソートしておけば尺取り法などで$O(N)$で探すことができる。これで最小コストが求まるのであとは頑張れば解ける。

ABC313-E: 2以上が2つ以上連続している場合は永遠に潰れないので、もし有限の時間で潰れるならばそのSは数字1と孤立した2以上の数字のみで構成されることが分かる。

また数字0は存在しないのでどの数字も基本的には増えるか変わらないかしかなく、潰れるのは末尾のみである。従って後ろから見ていくのがよい。

基本的に末尾は1ステップごとに1文字消えるだけだが、問題はある数字が潰れる段階に至るまでにその数字がどれだけ増殖しているかだ。結論から言えば、後ろに数字nがある場合はtステップ経つ間に$1+(n-1)t$個に増加している。そしてそれを消化するためにもちろん$1+(n-1)t$ステップがかかる。これらを念頭に後ろから順番に計算すると解ける。

ABC313-F: 制約を見ると$O(QK)$かけて良いことが分かる。このようなパターン数は普通にDPで求めればよい。ボールを1個増やすのは簡単に$O(K)$でできる。問題はボールが減るときの方だが、これはボールを増やすときの逆演算をすればよいだけだ。これでシンプルに解けた。

ABC321-E: とりあえず木なので愚直にDFSすれば答えは出せる。親、子左、子右の3つそれぞれから距離K-1のノードの数(ただし元来た方向のノードを除く)をカウントする、と言う風にして再帰すればいい。

問題はN,X,Kがクソでかいことである。ガッとまとめて数えたい。完全二分木という構造が美しいので頑張るとO(1)で数える関数ができるので、使うと、解ける。