2完。ギリギリのエスパー。疲れたー。
解説も見たけど苦笑いするしかないというか。自分はただACしただけだし。内容が高度でよくわからん。
A - My Last ABC Problem
全体の文字の種類数を減らす操作とは何かとか色々かなり時間をかけて考えた。そして、隣と文字が異なる個数は操作によって高々2しか減らないということに気づく。2個減らすことができない、隣と文字が異なる個数ができるだけ多いケースを作ろうとしてみると、4個以上なら常に2個減らせそうだ。また、3個のときは2回必要だし2回でできる（4つの同じ文字の区間がありそのうち2つは同じ文字であるため）。2個のときは、ABAとABCの2パターンがあり、後者は2回必要でそこが厄介。色々なパターンを書き出し手を動かしても規則性がありそうでわからない。自分は何の影を見ているんだと悩み続ける。90分やってかなり考察も進んだと思うのに解けない。順位表を見るとBのAC数がAを追い越す勢いだったのでBへ。
残り20分。mod 3の世界だとして隣との差を考えてみると、A[B]A（[]内に対して隣の文字と同じになるように操作する）みたいに戻ると最小限の回数でできそう。A[BCA]BやA[BAC]Bも操作後左端と右端の差は変化していない。ということで、隣と文字が異なる個数と隣との差（-1か+1）の累積和をそれぞれ前計算しておき、異なる場所の数を2で割って切り上げたものをベースの答えとして、2で割り切れてかつABCみたいのが残る（累積和の差が3で割り切れない）ときは1回余計に必要。これでAC。終了5分前。他人の解法ツイートとか見てから考えると、差の累積和の差が3で割り切れるって要するに両端の文字が同じってことなんだけど。そのくらい、発想の外にあった。操作によって何が変わらないかをずっと追い求めていたのだが、両端の文字が同じかどうかが（有効な）操作によって変わらないというあまりにも単純な性質は完全に発想の外だった。
B - Arrange Your Balls
捉えどころがないと思っていたが、グラフで考えると現れる色は連結になっている。全部でK色だったとき、単にソートすればペアの個数はKにできる。グラフを木にすればK-1にできる（連結なのでこれ以上は減らせない）。2個以上ある色を適当に挟めばいけると思って提出するがWA。改めてN=5とかで考えると全然木になっていなかった。ひどい。
例えば、1 2 3 4 5 4 3 2 とすれば木になる。もちろん 1 2 1 3 1 4 1 5 みたいなのもある。この中間みたいなケースを試してもちゃんと木が作れそうだ。ここでオイラーツアーを思いつく。オイラーツアーから末尾の1個を取り除いたもの（ループしてるので？）になっている。根の場合、その色の個数だけ子を持てる（ループしてるぶん）。そうでないときその色の個数引く1だけ子を持てる。個数が小さい順にやるとすぐ手が尽きてしまうので、大きい順にやればいいだろうと思いそうする。色を多い順にソートして貪欲に子を持つ。木ができなかったらソートして出力するだけ。木ができるときは、オイラーツアーのインデックスを色に直し別のvectorに突っ込む。そこに入れたぶんをカウントすることで残りの個数がわかり、その色が初めて現れたときに残りを全部突っ込む（まとめてしまえば関係ない）。オイラーツアーのvectorに最初から要素が入っている謎の挙動でデバッグに苦しんだが、最初にclear()することでサンプルが通り提出してAC。今調べたら、マルチテストケースだからだった。いつもの感覚で使い捨てのグローバル変数を使っていた。なるほどね。
