Highestを更新。一生ないと思っていたのにね。最近はいいパフォーマンスをコンスタントに出していて、これは4年やってて初めてで、ここまで来たんだなあという感慨がある。いや正直青落ちは覚悟してたし黄パフォ出たらAGCでの黄色初防衛めっちゃ嬉しいになる感じだったので、あの状況からの橙パフォは不意打ちだった。
160分の折り返しを過ぎたあたりで思い出して用意しておいたチョコレートを食べた。お腹が空いたのでカロリーメイトも食べた（これはお腹にも時間的にも重いが、行き詰まっていたので気分転換の意味もある）。
A - Long Common Subsequence
楽しく考えていると、「もう20分経ってるのｗ」になる。長さが2Nなら'0'を2N個出力するだけでいい。2N+1なのでどうしますかという問題だ。00100みたいのはよさそうだ。とりあえずそれで実装するが、証明できないので考え続けていると0110+0110という反例が出てきた。0011型にするか、あるいは文字列が3個だから16個くらいパターン用意して全部違うタイプの文字列でも対応できるようにするとか。少しして、00110を見つけた。前半からN個の0と後半からN個の1を採れるので、文字列が0で終わるならその最後の0を追加してOK。1で終わるなら「末尾に1がちょうどK個連続している」というKが存在し、その直前は0である。前半で1もK個もらえて後半ではN-K個だけ取ればいい。そこには0とK個の1が残っているので0をもらって終わり。
きっちり解けたのにWA。Bを考えながらチラチラ見ていたが、ソースも何回か見直したのに文字列をintで受け取っていたことに気がつかなかった。入力はNしか使わないし、マルチテストケースだし、これは割り切るしかない（AGCの"圧"というやつ）。ただ、自分では解けてるつもりだから放置してBに行けばいいと思ったけど、やっぱり気になって見直しちゃうんだよね。面白い問題だと思ったけど、コンテスト中にこうして贅沢な30分を使うことには複雑な気持ちもある。
（解説を読んで）きれいな証明だ。
B - Tree Edges XOR
謎の「奇数」（こういうのはやってるうちに忘れるもの）。辺に注目する問題だ。操作で自分は変わらず隣の辺たちにxorする。とりあえず、重みが0か1で、木がパスグラフのケースを考えてみる。色々手で実験して、なんか長さ2の塊が移動してるみたいなイメージ（重なると0になる）（端には1マスぶんだけ食い込める）。パリティみたいなものは感じるが、具体的に何が不変量とか言語化できない。全部1の状態からかなり減らせるが、めちゃくちゃ自由というわけでもなさそう。
というのを延々やっていつの間にか残り1時間。AGCは長いと思ってもマジであっという間。まあそれはいいことだ。ここまで1完1WAで2問目も解ける見通しがなく状況は悪いが、立ち回りはよかった。落ち着いて考えれば大抵の（青diff以下や相性のいい黄diffくらいの）問題は解けるという感覚があり、実際落ち着いて考える（実力を発揮する）ことができていた。ただ、ここから30分くらいはすることがなくなってきて微妙だった。今考えている特殊ケースが解けたとして30bitに拡張できるのか、一般の木だとどうなるのか、たまに考えるけど特殊ケースも解けてないので考えようがないという感じだった。
残り30分くらいになって、ノートに描いた木を見て3つに分かれてたらパリティもクソもないじゃんと気づく（今更かよ！）。それを機に、木で考えてみたら、辺より頂点のほうが一つ多いから頂点に重みを設定して、結んでる2頂点のxorを辺の重みとすればいいと気づいた（適当に頂点を選んで重み0の根してDFSすれば、指定した辺の重みになるような頂点の重みが設定できる）。これがいいアイデアだと気づくにつれ、大きな有声ため息が出た。もっと早く気づいていればACのチャンスがあった。しかし最善は尽くそう。まず実装から入る。実装は考えが整理されるし、時間がかかるからその間に考察を寝かせることができる。そして、操作は頂点の重みのswapであると気づく。これは一気に進んだ。頂点の重み自体は、根を任意の重みに設定できるので自由度がある。N^2の計算量でいいなら解けたっぽい。残り15分以上あるのでいけそう。しかしなかなかわからない。頂点の重みをソートしたいんだけど、全体に何かの値でxorかけても辺の重みは変わらないのでどうにもならない（基準がない）。気分転換にトイレに行く（いいムーブ）（このあたりでは震えがきている）。戻って少しして（タイミングあんま覚えてない）「奇数」を思い出す。ここまで忘れていた。急いでw1,w2それぞれの頂点の重みの総xorを求めるコードを書く。でもわからない。時間がない。両方に0は存在してるわけで、ワンチャンそのままソートでいけないか（いや0の個数が異なるケースとか前に思いついてるのでやけくそだけど）？サンプルを動かしてみると、変数名の書き換え忘れを発見し、直してやはりサンプル1が正しく判定できない。しかし0,1,8と0,1,9の違いだったのでxor的に希望は感じる。残り5分を切っているのでさっき計算した総xorを両方w2側にかましてからソートして比較でサンプル通ったので提出。ACだった（最後はもうごめんなさい完全にてきとうでした）（これが通るのけっこう珍しい感覚）。
（追記）布団の中でなぜそれで上手くいくのか考えた。総xorをSとする。根の重みを0からXに変更すると（頂点は奇数個なので1個を残して打ち消し合って）総xorはS xor Xになる。つまり総xorが重要で、これが0になるように正規化（？）できる。総xorを求めその値で全体にxorかければいい。自分が書いたコードは、0にはせずに、w2側をw1側に合わせていた。
（追記）重みが0か1で一本道の特殊ケースでもあんなに難しかったが、それも同じ方法で解けているということなので、具体的にどうなっているか見てみる。辺の重みが全て0だと何もできないというのは、頂点の重みが全て同じということなので、これはいくらswapしても何も起こらない。「長さ2の塊」は、重み1の頂点の位置が動くとそれが影響を与える2辺も動くということだ。端に1マスぶん食い込むのは、端の頂点の影響は1辺にしか及ばないから。全ての辺の重みが1のとき操作でどこまで重み1の辺の個数を減らせるかも気になっていたが、頂点が01交互になっているので片方に寄せれば1個まで減らせて0個にはできない（手でやってたときはN/4とかまでしか減らせないイメージだったが、1個まで減らすにはO(N)の操作回数では無理だったのね（可能ならO(N)回で済むという無意識の思い込みがあった））。辺の重みが0のときは操作できないので複雑そうだと思っていたが、同じ重みの頂点2つで重みをswapしても意味ないということだ。いやあ全ての謎が解けてしまいましたすごい。自分は"影"を見ていたから断片的な法則性しかわからなかったんだ。
