ABC188のバチャをした。全完。

Dはするっと座圧っぽいコードが書けたので良かった。単純にソートしてwhileで違う座標になるまで追ってって同じ座標の部分をかき集めるやつは座圧って呼ぶのか謎だが。

EはDAGだったのでギャグだった。ギャグって程じゃないかもだがかなり簡単なDPで解けた。解説読むとちゃんとDAGじゃない一般の場合に関する解説もあったので面白かった。順次取り除きながら繰り返しBFSすることでO(N)になるらしい。

O(N^2)が間に合わない制約だと、O(N)やO(NlogN)のアルゴリズムを非定数回繰り返すような発想はなんとなく捨ててしまいがちだが、合計でO(N)になって間に合うのは面白いなと思う。O(N^2)っぽい発想でも実は合計O(N)な可能性を検討してみると良いのかもしれない。

FはほぼほぼPay to Win(AGC044-A)だった。ので大体同じ事をやって楽に解けてしまったが、ぶっちゃけちゃんと理解しているかというと怪しい。逆から考えていくのはいいとして、なぜ$\lfloor\frac{N}{2^a}\rfloor$と$\lceil \frac{N}{2^a} \rceil$さえ考えればいいのか。

ABC188-FにしてもAGC044-Aにしても、どうやら本質は±k→÷kはすべからく÷k→±1に変換できるという点で、それを使って自明に減らせるコストを減らしたら$N \rightarrow \lfloor\frac{N}{k}\rfloor$と$N \rightarrow\lceil \frac{N}{k} \rceil$しか残らないという話である。そして$\lfloor\frac{\lfloor\frac{N}{p}\rfloor}{q}\rfloor$、$\lfloor\frac{\lceil\frac{N}{p}\rceil}{q}\rfloor$、$\lceil\frac{\lfloor\frac{N}{p}\rfloor}{q}\rceil$、$\lceil\frac{\lceil\frac{N}{p}\rceil}{q}\rceil$の4パターンはいずれも$\lfloor\frac{N}{pq}\rfloor$か$\lceil\frac{N}{pq}\rceil$のどちらかに落ち着くという補題を踏まえると、結局全ての割り算における切り捨て・切り上げはまとめられてしまうことが分かる。

面白いけど、今一つ一般的な教訓が得にくいな。連続した切り上げ・切り捨てがまとまるのは役立ちそうだけど。

自明にコストが減らせるパターンを見抜いて考慮すればいい状態数を減らすのは一般的だけど、あまりに当たり前で一般的過ぎるから教訓って言ってもなあ感がある。気付ければ勝ちで気付けなければ負けだし。

ちなみに出場してたら黄パフォっぽかった。ざんねーん。

---

焦点が同じ双曲線と楕円が直交する証明が面白くて良かった。クソみたいな式を頑張って整理すると良い感じにシンプルな式になるやつ好き。