トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）Fまで。
C 適切にsort。
D 一周期の和をXとし、S=S%Xとする。累積和中にa+Sが含まれればよいので、setで判定。累積和は二周期くらい取る。
E dfs+heapq
F 2^iの余りで分類
G Moや平方分割を考えていたが上手くいかず。

— titia (@titia_til) December 14, 2024

G - Abs Sum

　こたつがめさんの放送の振り返りを見てAC。

　Mo’s algorithmは考えたのだが、差分更新の方法が分からなかった。ソートしてある配列のどこへA[x]を差し込むか？　みたいに考えていたため、平衡二分木がいるのでは？　などと考えてしまった。

　sortedsetが必要そうな問題で、実はBITで事足りるということは良くある。その方針で検討しなくてはいけなかった。

　Mo’s algorithmの分割個数をどうすれば良いかは謎。

　今回は、分割する個数をかなり小さくしたら通ったが、計算上の計算量は増えているはずだし、いつもそれで良いかは分からない。