5完。Eまでいい感じに解けた。Gに行ってまるっきり時間が足りず水パフォ。当然のように黄パフォ出してた時期との違いは何なのか。
A - Last Letter
簡単。s.back()を出力。
B - Go Straight and Turn Right
やるだけだけど面倒。配列で右回りの向きを手書きしておいて、あとは'R'が来たらmod 4でインクリメントしていくだけ。解説のやり方もいいね。
C - Yamanote Line Game
インタラクティブの練習問題。各整数について現れたかのフラグを持つ。
D - Swap Hats
慌てて置換のパリティについて思い出す。転倒数（の偶奇）を考えると、隣同士のスワップで1だけ変化する。もっと遠くのものとスワップしても、その間にあるものとの関係の寄与は2要素が動くので偶数になり結局スワップしたもの同士の1だけが残る。つまりそれぞれ転倒数を求めて偶奇を比較すればよい。10^18は十分に大きな偶数なので、偶奇が一致すればできるし、そうでなければできない。
E - King Bombee
大変そう。Sを出発してちょうどK歩でTに辿り着きXを偶数回訪れた通り数。DPだと思うけど遷移の順番がわからない。落ち着いて考えると、1歩ずつDPを進めていけばいい。現在の歩数で頂点iにXの訪問回数%2がpで存在する歩き方が何通りあるかでDP。1歩進めるには全部の辺を見て配ればいい。行き先がXなら偶奇を反転させたものへ遷移する。K+1個ではなく2個のDPテーブルを確保しゼロクリアして配りコピーするやつだいぶ慣れてきた。
F - Shortest Good Path
G問題と共通する部分が多い問題文なので、問題文を読む手間が省けてよい。Sは各頂点のパスでの出現回数の偶奇を表す文字列みたいの。DPっぽいと思ったけど考えていくと4秒あってもそれは間に合わないだろという感じになって一旦飛ばした（帰ってくることはなかった）。
（追記）bitDPじゃないんだ。うへあ。パスを作っていくことを考えると、偶奇の状態とパスの現在の末端の頂点でまとめて扱えるので、2^N*N頂点のグラフでBFSできる。辺の個数も1頂点につき高々Nなので間に合う。全部偶数の最短は長さ0とわかっているので、それは足さなくても影響ないので無視して、長さ1のスタート地点N通りからBFSする。自力では全くわからなかった。
G - Construct Good Path
Fを読んで難しそうだと思った構成が問題になっている。全部の頂点を訪れることを考える。一筆書きとかでググり、辺の数を2倍にすれば一筆書きできると気づく。しかしこれでは1回しか訪れない頂点もあるので、更に倍にすれば全部偶数回になる。制約は4*Nだが、辺の数はもっと多い可能性があるのでそのままではダメ。厄介そうだと思ったが、単に辺を削って木にすればよかった。制約内ならどんなグラフでも達成できると書いてあるので、木になるまで辺を減らしてもデメリットはない。各頂点が正の偶数回現れるパスは構成できた（木でDFSを2回）ので、あとは奇数にしたいところを削れないか。奇数にしたい頂点2つをペアにしてそのパス上だけ2回ではなく1回に減らせばいい。奇数の頂点が奇数個だったときは、とりあえずあぶれたやつを無視して構成し、そのパスはループになっているのであぶれたやつが先頭に来るようにrotateして先頭を削除すればいい。あとはペアの作り方だが、オイラーツアーで（元々白で）一部の辺を黒く塗ることを考えて、奇数の頂点が現れるたびに反転してその色で辺をxor塗りすれば最終的にペア同士を結ぶ重ならない黒いパスができるはず。これ、色は行きでだけ変えて戻り値で色を親に渡すんだけど、どうしたらいいかわからなくてめちゃくちゃ時間かかった。思いをプログラムに落とす力がない（競プロerであってもほとんどの人はそうだと思うんだけどなあ）。塗ったら、黒いところだけ1回でそれ以外は2回DFSする感じでパスを構成する（黒いパスの両端だけ奇数回減る）。こちらも難しい。まずオイラーツアーの頂点をvectorに入れるのからして詰まる。現在の頂点を入れて、再帰呼び出しして、子を入れる、とすればよかった。全体で偶数個になるのもなかなかわからなかった。黒いパスの部分を減らすのは、コンテスト中に考えていた方針はめちゃくちゃ時間かかった（白い部分は2回DFSして、1回目は普通に、2回目は白い部分だけ、黒から白に変わったときはまたそこを根にして2回、イメージは浮かぶけど実装はありえないほど難しかった）。コンテスト後に全然実装できなくて他の方針を考えると、単に白い辺だけ都度1往復すればいいと気づいた。40分遅れくらいでAC。
解説はよくわかんないけど、UnionFindで木にしなくても単にDFS木を使えばよかった。DFSは2回しなくてもいい（1回にまとめられる）。あぶれた奇数頂点は、そもそもそこを根にしてDFSすれば、1だけ長くして根で始まり根で終わるパスにするだけで偶奇は反転する。
