GCJ 2022 R3
Dのデバッグがなんとか30秒前に間に合った！
去年はデバッグが終わらずに落ちてしまったので成長を感じた。この調子で勝負強くありたい。
去年は順位表に踊らされて立ち回り失敗したので、（Hiddenの結果が信用できなすぎる）
今年は自分のボーダー見積もり力を信じることにして、順位表を一切見なかった。
ABC/AbCdの71速解きがボーダーで、D-large通せさえすれば通ると思ってた。
B-smallまで行ければABCdにも勝てるので盤石だったけど、間に合わなかった
A - Revenge of Gorosort
余裕じゃんと思って2個ずつペアにする感じのを書く。
１しか通らなかったので制約をちゃんと読むと、制約が全部のテストケースまとめての回数であることに気づく。落ち着こうね。（まぁとりあえずで様子を見る意図もあったのでよし）
サイクルごとに独立に考えてよい。
サイクルを何個ずつくらいに分けるのが効率良さそうかを見積もると、4が最善だった のでそんな感じで。
「終了までの回数の期待値」ではなく「減る個数の期待値」で見積もってるので、厳密ではないと思うけど
ランダムシャッフルしたときに場所が合う個数の期待値が長さに関わらず 1 であることなどを使うと効率を見積もりやすい。
$ ?,2,3,...,n（?はダミー）をシャッフルして場所が合う個数の期待値は$ n-1/nで、１個あたりでいうと$ n-1/n^2
あれ？2が最善では？ 運が良かったということで・・・
（メモを見ると$ 4/3 > 3/2や$ 9/4 > 8/3などというトンデモ数学を披露しており...）
実際は、2ではなく4とかでやると残るサイクルサイズが小さくなりがちなのが効いてるのかー。なるほど。
B - Duck, Duck, Geese
問題文読解でもたもた。
解けるものに見えないので後でsmallを取ることにして次へ。
捨てる判断が速くて偉い。
後で考えよう。
解法は分かった気になったけど、案の定苦手なタイプの実装（区間の端の±1とかに気を付ける必要がある）なので、飛ばして正解だった。みんな実装早い。
C - Mascot Maze
天才パズルの波動を感じ、これは解かないといけないかなと思ってまじめに取り組む。
天才パズルかと思ったが、冷静になると典型だった。カモフラージュが上手。
彩色の典型を知っていますか？僕は(ry
出次数のmaxが6の有向グラフを無向にしたものの13彩色
つまり辺の本数は高々6N（次数の合計は12N）
必ず次数が12以下の頂点があるのでそれを後で塗ることにして削除、を繰り返す
余談：今日のABCのEと似た実装が発生して面白かった。 D - Win As Second
SmallとLargeの差があんまりなさそうだったのでBより優先で取り組む。
木の形が自由なので、部分木が少なそうな木をランダムに生成して探すとすぐに見つかり、はい。
と思ったのにバグを埋め込んでしまい大変なことに・・・
writer: Petrだろうと思ったらやっぱりそうだった。
木の形：
パスグラフに4,5頂点をランダムにくっつける
バグの原因：
部分木からvを消して出来る部分木について、その根を消すとさらに部分木が分かれるということを失念...
30~40分デバッグしてた気がする・・・よく間に合わせた、えらい。
SmallとLargeの差：偶数より奇数の方が難しいらしい
おまけ