ARC156

2完。青パフォ以下でレーティングを下げるの3か月ぶりくらいらしいです。このいやーな気持ちを毎週のように味わう競技だったね。久しぶりすぎて「耐えられるか？」って思っちゃうくらい。

A - Non-Adjacent Flip

手で実験して感じをつかむ。N=3のときだけ操作できない点がある。操作で表の枚数は偶数だけしか変化しないので、元の表の枚数が奇数ならできない。表が0枚なら0回でできる。N=3のケースは（あとでまとめてできるかもしれないが）場合分けしてしまう（真ん中が表ならダメ、そうでないなら（表が0枚や奇数枚のケースは処理済みなので）1回）。遠くのコインとは自由に操作できるので、4枚以上残っていれば前半と後半に分けてペアを作れば理論値出せる。あとは表が2枚のときで、離れていれば1回でできる。くっついているとき、1回では無理で、左右どちらかに長さ2以上のコインがあれば一番遠いやつと操作することで2回が達成できる。そうでないとき、N=4であり、できる操作は限られているのでその操作をすると、2回ではできず（1回の操作ではくっついた状態にしかならないため）、3回でできる。

時間はかかったけど詰めるのは難しくない問題だった。まあratedでやりたい問題ではないけど、いい問題だと思う。

B - Mex on Blackboard

mexは昨日のyukicoderでやったのですんなり入れる。どういう数が追加できるか考えると、mex(黒板)以下の非負整数全部だ。最終的に追加できる数も4*10^5程度にしかならないので、全部試せそうだ。最初黒板になかった数を全部試す感じで書き始めたが、そうではなく、単に追加した最大の数を全部やるのでよかった。追加した最大の数を固定したら、そこまでのない数は全部1個は追加する必要があり、追加した最大の数のぶんも1個追加して残りのKを自由に分配できる。これは仕切りを入れればいい。元々ない数かどうかで素直に場合分けするとよかった（ない数のときだけKをデクリメントする）。境界を考える余裕がなくて、大きめに確保した（こういうのかえって危なかったりもするけどな）。

C - Tree and LCS

解ける見た目をしていない（ただこういうのって趣旨がわかれば簡単なことが多いんだよね、Cに置かれてるわけだし）。Dと交互に考えて結局Cに集中した。

類似度が0になることがあるか考えると、1を1に移していたら1以上になるし、1を2に移していたら頂点1と頂点2を結ぶパスを選べばやはり1が共通して類似度1以上になる。じゃあ類似度は常に1にできるんじゃないかって考えると、パスを延長すると不利になるので極大なパスだけ考えればよくて、（12345と54321みたいに）数が逆順に並んでいればいいので、木の真ん中っぽいところを根にして各子の部分木を順番保って入れ替える感じでできそう（部分木の内側にその部分木由来の数がないようにすれば根を通るパスのみ考えればよくなる）。ググって木の重心を一つ求める。重心を根として一番（頂点数が）大きいやつからやっていく。最初は頂点と深さを集めて深さでソートするだけ（のちにこのソートは不要だったと気づく（先入れ先出しするだけで必要な順序は保たれる））。次からは、頂点を集めつつキューに入れたさっきの頂点たちの番号を割り当てていく。最後、最初の大きい部分木のぶんの頂点があまっているのでそれを割り当てる。

1回目の提出はREで、一番大きい部分木を根以外でも求めていた。それを修正して2回目はWAが9個。かなり悩んで、N=2のケースを試したら間違ってたんで埋め込んでWAが8個に減った。ここでソートが不要だと気づいてとりあえず投げてみるが当然何も変わらない。4回提出してダメだった。終了後も考え続け、重心が2個あるケースで普通に間違っていた。辺を重心みたいに考えないといけないんだね。なんとか修正してACしたが、めちゃくちゃ時間がかかっている。Bがわりと早く解けた中でこれはちょっと厳しい。

D - Xor Sum 5

K回選んだ合計のmod 2、これはわかりそう。mod 8が4未満かも行列累乗でわかる。しかしmod 2^16とかになるとできない。A_iが小さいことを生かす方法も見えない。問題名見てなかった。見てたら印象変わりそう。