Cで大変なことになってしまった...
AB2完。Cは終了後にAC。
A - Tile Painting
最後の TCB で似た設定を見た。素因数を つ以上持つなら上手く からその素因数を足し引きすることで全部の index を覆えるので答えは で、 つならそれを として で考えれて答えは になる。
B - 0-1 MST
これ面白い。最初頂点を半分ずつ分けて再帰する形かと思ったが、 頂点のコスト の辺からなる完全グラフの各頂点にコスト を伸ばしたもう 個の頂点をつけたので ではなく になるので嘘だった。
大人しく を取り除いたものの連結成分数を考えると、愚直に縮約しても計算量がそこまで大きくならないことに気づく。 priority_queue を使って実装したが、使わなくても良かったかもしれない。
C - Sum Balance
サイクルを見つけて再帰する形にして実装してたが、同じサイクルを複数回舐めるハメになるのでこれでは TLE になってしまう。そこで の DP を考えて、先に頂点集合ごとにサイクルがあれば つ見つけてあげるという実装にした。同一サイクルを 回以上辿っていそうなら強制終了するのを組んだが WA が取れないので TLE 覚悟で外したら通った。なんでやねん。
で が頭によぎらないの、かなりダメだった。