ABCDFの5完。最近ABCの問題が面白くていいですね。今回のDEFみたいな難しい問題を考えるのは面白いが、実装は嫌（今回だとF）。時間をかけて書き切る力が付いたので、もう飽きてしまったのだと思う。とはいえ（？）、やはりコンテスト中のが集中して実装できはする。
A - Subsegment Reverse
std::reverseを使う。123ではなく012にしててサンプル通らなかった。
B - Nutrients
Aのvectorを用意して、xを引いていって、結果Aに正の要素があったらNo。
C - Keys
ビットで持てば楽。Bonanzaの開発者が言ってたけど、速度のためというより楽だからビットボードを使うんだよね。使った鍵の集合とその結果を保存しておき、2^N通りを全探索。andしてpopcountしてK以上か判定。
D - Masked Popcount
難しい。桁DPのニオイすらする。Mが全ビット立ってるときとかを考えていて、しばらくしてビット毎に考えればいいと気づく。（Nには1を足しておいて2^iの位置を見ているとして）よく考えるとNが2冪で2^iがそれより小さいならちょうど半分の整数でそのビットが立っている。とすると、Nは2^iの位置より上だけ見れば大体いい。問題はNの2^iの位置が立ってるときで、よくおぼえてないけど0でいいと思ったらしくそれで提出してWA。けっこうびっくりした。改めて考えると、そういうときは2^iの位置より下のビットが意味を持ってくる。今度はACしたが、修正に8分かかっている。難しかった。
終了後、AIがDまで解いたと聞いて自分でも試してみたが、GPT-4oすげえこれ解けるのか。英語の問題文貼り付けて競プロの問題解いてって言って、最初愚直を出してきたので高速化してって言ったらちゃんと高速化してきた（オートでACしてる人もいそうなのでもっといい言い方があるんだろう）。発想も細部もかなり難しい問題だと思ったので、これをきっちり実装してくるのは本当に強い。
自分が使うかだけど、現状使うつもりはない。今回だと、D以降は面白いので自分でやりたい。ABは自力で瞬殺できるし、そこの速さは競技としても面白い。Cの実装をやってもらって後半の問題に時間を残すのはありそうだが、やはりここも競技として、あるいは実装（けっこう考えるところがある）自体に楽しみがあり（つらさのが多いかもしれないが）、何よりAIに任せてペナったときの得るもののなさが怖すぎる。今思ったけど、（解けたけど実装したくなくて）飛ばした問題があって残り3分とかになったらやってもらうのはありか。でもこれでさえ得るものがレーティングしかないんだよな。貴重なコンテスト中の時間にやることではない。ARCで愚直実験コードを書いてもらうのはありそうだが、これは自分がAIの吐いたコードを信用できないという問題があるんだよなあ。ここは練習してもいいかも。でもやる気はないけどな。最近なんもやる気出ない。
E - Max/Min
どういうペアが使われるかしっかり考えると、ソートしていい。上から考えると、何で割るかが色々ありすぎて無理。下から考えると、例えば7で割ったあまりの和が何らかの前計算を前提に高速に計算できればいいが、さすがに無理そう。A_iが10^6以下というのは、答えが64bit整数に収まるようにそうしたということで納得はできるが、しかし使えるかもしれないので考える。何も思いつかない。不可能なのでFへ。
終了後に考える。10^6を使うなら調和級数。そういう解法だと決め打って考えるとわりとすぐ解けた。N*(N-1)/2個の和を求める問題だが、N^2個の和を求めればよいのでそちらで解く（Aに同じ数が複数あったとき面倒なので）。Aに各数が何個あるかカウントしておき、その累積和も持っておく。Aに存在する各数について、その数で割って何になる数がAに何個あるかというのを累積和で求める。これでO(N*log(N))。サンプルがなかなか合わなかった。N^2個の値の分布みたいのが思ってたのと違った。対角線の反対側は大体0だし、Aに同じ数が複数含まれるときは1が飛び出す。結局、対角線は引かずにその飛び出した三角形を引くことにした。
F - Distance Component Size Query
undo付きUnionFindを思ったが、木構造になってない（ばらばらの位置でオンオフされる）のでだめだ。座標圧縮する。クエリのxに同じ数が複数回現れることはあっても、集合Sに同じ数が複数含まれることはない。連結成分が区間になるという性質を使う。遠くの頂点まで辺が張られることもあるが、隣だけ見ればいい。隣が何かはstd::setでわかる。あとはセグ木で各点の情報をまとめられるかと思ったが、無理そうなので遅延セグ木に。連結成分がどこからどこまででサイズがいくつかを、その区間の要素全てが持つ（頂点じゃない場所が持ってもよいとする）。これで実装を始めたが、削除によって区間が分割されたときにそれぞれのサイズがわからないことに実装してから気づいた（これはよくない）。幸い、BITで頂点数を管理することで対応できた。setで左右を見るのも毎度面倒だが、左右に連結していたかどうかで4通りの場合分けがあり、それを追加と削除でそれぞれ書く必要があるのがやばい。途中で、この実装の重さはおかしいと思い一旦立ち止まりはしたが、実装を続ける判断。直す必要がないかもしれないミスに気づいたが、直した（区間を広めにとっていた）。サンプルを実行して0しか出力されない。左右どちらにも連結する相手がないときの処理をしていなかった。更に、遅延セグ木で作用とモノイドの演算を逆に書いていた。かなりの時間を使ったが、ギリギリでACできた。
