7完。めちゃくちゃ簡単だった。Gを提出して(ジャッジ中に)順位表見て順位が低くて驚いた。
A - camel Case
文字コードどっちが小さいんだっけ。まあAとZの間で判定すればよい。isupperは忘れてたな。
B - Trimmed Mean
ソートして真ん中だけ足す。
C - LRUD Instructions 2
unordered_setに突っ込んでいってサイズがN+1かで判定。もうちょっと高速で実装も同じくらいで済む方法ありそうだけどな。
unordered_setってどうなんだろうな。AtCoderならハックはされないし、そういうヤバいケースも入れてこないと思うけど。
D - Flip Cards
DPテーブルが小さすぎてどう実装するか迷ってしまった。実装方針はいまいちだった気がする。
E - Find Permutation
木とかループとか非連結とか考える。その様子からトポロジカルソートに思い至る。MがNよりずっと大きい場合もあるのでアドホックな実装は厳しい。ABC223のDを探して、辞書順最小ができるならその自由度があるかで判定できるはず。最初、誤って頂点番号を順番に出力していたが、そうじゃなくて答えのvectorを用意して頂点番号の位置に1から順に書き込んでいくのだった。このへんややこしい。
F - Teleporter and Closed off
スタートとゴールからそれぞれBFSしておいて、kをまたぐ移動であってスタートまでの距離とゴールまでの距離の和が最小のものを求める。
G - OR Sum
5bitしかない。1bitのときを考えると、これはFFTでできる形をしている。もう少し考えると、FFTを5回やるだけっぽい。なんかヤバい畳み込みかと警戒してたけど。添え字がややこしいけど頑張る。Bを逆順にしておいて、N*2-1個の結果が出てくるので折り畳んでN個に収める。1bitずつ計算して足していくだけ。最初に全部の和を求めておいて、無駄になる(立ってるビットが被る)のが最小のものを引く。
Ex - Balanced Tree
この前のARCで木の重心を求めたので類似性に気づく。重心を一つ求めてそこを根にしてみると、その子を根とした部分木(ややこしいけど誘導部分グラフで元の問題を考えるみたいな意味)が条件を満たさないことはあるものの、そこでも重心を求めてそれを根に付け替えればいくつか試した範囲ではLCAの条件も満たしていそう。時間もないので実装する。重心で分けているので全体をなめる回数はO(log(N))で済みそう。再帰的にやるのが慣れていないとかなりきつく、コンテスト終了後もやってけっこう時間がかかった。頂点数のカウントも毎回愚直にやって間に合う。これが重心分解らしいけど、何が嬉しいのかわかってない。