Codeforces Round #841 (Div. 2) and Divide by Zero 2022

　Cまで三完。Eは通したかった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #841 (Div. 2) and Divide by Zero 2022　Cまで三完。CでハマってDE通せず悲しい。
B シグマ計算
C zero sum ranges系。平方数になるところを除く。
D 二次元Sparse tableを書いてMLEだろうと思って投げたらWA。
E 約数包除した後で貪欲でWA。

— titia (@titia_til) December 27, 2022

D. Valiant's New Map

　二次元Sparse table（か、二次元セグメント木）でやるしかないと思ってコンテスト中書いたがWA。

　クエリ計算のところで、二点のminではなく、四点のminを取るよう修正したらMLEになりました。

　昔、二次元Sparse tableを書いたときそれだけで数時間かかったことを思えば成長。一旦Sparse tableを取ったあと、そのそれぞれの要素についてもう一度Sparse tableを取ると考えたら、それほど詰まらずに書けました。このままライブラリ化しても良いかも？

　この感じなら、二次元セグメント木も書けそうな気がしてきました。

　ただ、この問題はそういうデータ構造を使わなくても解ける問題でした。毎回二次元累積和を取る解法でAC。

E. Graph Cost

　約数包除くでgcdの個数を列挙した後、大きい方から貪欲にやればOK。

　という解法は分かっていたけど、約数包除の実装でミス。時間がなかったので、ベン図など書かずにこんなものかな、と実装したらダメ。ちゃんと図を描いたら解けました。