UTPC2022
オンサイトに参加した。結構広くて快適だった。電源の確保が大変そうだった。
問題は全体的にかなり好きだった。
個人参加4位（全体8位）まぁまぁ。終盤の難易度が平坦なので個人だと大変そう。
逆に序盤の難易度も平坦で、青の人とかがつらそうだった。
この難易度帯が一番面白いの作りやすいからしょうがないね。
O
序盤はとりあえずFA狙い
問題眺めながらグラフ問題を探したらこれしかなかった。
読んだら簡単だったので実装。
人を区別しなくていいのでまとめて処理して良い。
投げたとき順位表ですでにNachiaさん（だっけ）が提出してたけど落ちてたっぽくて、無事FA獲得やったぜ。
K
解けそうな見た目してたのでやった。
誤読して迷走（i+jが偶数の制約を見落としてた）（ちなみにそれは解けなそう）（解けた気になって実装したんですが。） 実装し直してACしたけど、遅かった。
D
結構もたついたので簡単枠がもう残ってなかった。
残りの中でぱっと解法が浮かんだのがこれだったのでやった。
大迷走。
$ 1と$ Nを特定してそれらを$ -N...Nの範囲で動かせば$ N^2くらいまでの差を調整できるなー
最小（最大）の特定は$ N回ずつでできるから、操作回数足りてるな！
→ん？$ 2N回ずつかからないか？
$ Nの方はランダムに選ぼう！
幸い二分探索は何回か出来る余裕があるので、ダメだったらランダムにずらして再試行
コードがハチャメチャに。なんとか手元では良い感じに動いたけど、WA
この時点でFAが出てたので飛ばす
70分くらい経ってて涙
L
まだ解かれてないうちでなんか得意そうな見た目なのでやる
条件を考察するとオートマトンで判定できる形なので、左右から一回ずつ舐める感じで。
WAしたしすでにFAが出てたので飛ばす
I
EFIJが残ってて、Eやばそう、Fちょっと考えたけどむずそう、Jむずそう、なのでIへ。
((と))は選ぶ方が一択
()はどっち選んでも嬉しさがあるので後で選ぶ
)(がやばくて、これらを良い感じに処理できれば良さそう
+-列だといまいち上手くいかなさそう（実はこの方針で準線形にできるらしい、たしかに）
マッチングの方向で考える
フロー職人なので(?)瞬く間にグラフを作り上げる
このままだと(,)の個数をちょうど2Nずつにできない可能性がある
((,)),(),)(の個数を$ A,B,C,Dとして、)(と((,))のマッチングの個数を$ X,Yとすると、$ |(A-X)-(B-Y)| \le C - (D-X-Y)を満たせば良さそう
整理すると$ \frac{A-B-C+D}{2} \le Xかつ$ \frac{B-A-C+D}{2} \le Y
フロー職人なので(?)瞬く間に最小流量制約に対処
FAには間に合わず・・・悲しい。
残り２時間（）
L(続)
FAは諦めて順位を上げに行く
とりあえず途中までやったのを通しに行く
オートマトンがちょっとバグってた
状態を２つ追加し、AC（8状態だったかな）
D(続)
リファクタリングしたらバグが取れてAC
ジャッジ待ち中にH,Aを通した
コンテスト後にdeterministicな解法も実装しといた
H
簡単枠
A
GCJ終盤ラウンドのAとかに出そう
全桁同じならそのまま
違うならそれらを下２桁にして入れ替えて差をとると9dの約数しか無理なのが分かる
9の倍数→出来た
9の倍数でない3の倍数→出来た
3の倍数でない→１桁しかない
M
和が偶数なら半分ずつに分けて0
いや、長さ1だと無理だな
奇数なら1？
長さ２だと無理なこともある
下位ビットに連続する1の個数かな～
$ O(N^2)かけていいの優しい～
B
$ X_{min}, X_{max}試せるな
最短経路、面白い
G
二分木を考える
葉にAを割り当てる
それ以外はK
深さの偶奇で+-が変わる
+の頂点が1個の状態から「葉に子を２つつける」を$ N-1回繰り返す
「＋→ー」「ー→＋」をそれぞれ$ X,Y 回とする
$ X+Y = N-1
節点：$ (X-Y)*K
葉：大きい方から$ 1-X+2Y個のAが+、残りは-
$ Xを全部試す
全体から$ K/3を引くと節点の重みが0になるらしい、たしかに
N
前から2個ずつ切るみたいなことを考えたけどちょっと違った
最適戦略が結構シンプル
dpできるね
J
Cに行きたかったけど時間が足りなそう
10点なら残り10分で取れそう
→取れませんでした！！！！（え？）
操作を逆順に出力してた
順位を２つ上げそこなって悲しいね
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝コンテスト終了＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
F
この問題すごい
バブルソートの一般化みたいな感じで、こんなもん解けるんかみたいな見た目をしている
先頭がイレギュラーそうで、そこらへんもむずそうだなーみたいな見た目をしている
考察すると結構綺麗な構造をしている
窓を後ろにずらしていくと大きい方からK-1個は送られる
バブルソートでは：最大値が送られていく
つまり「前にあるデカいやつ」の個数が$ K-1ずつ減る！
バブルソートでは：実は 1 ずつ減っていたのか～
あと、そういう物たちはindexも$ K-1ずつ減る
先頭も実はかなり綺麗に処理できる
被る分を答えから引けば良い
先頭に入ると「前にあるデカいやつ」は0になる
各要素について、0になるタイミングとその時に居る場所も分かる点に注意
C
NIMの最長手数、色んなところで出てるらしいけど１つも知らなかった・・・
見たことない計算量
J
logと見せかけて定数なのおしゃれ
場合分けを細かくやるので鬱病になりかけたので、さらに考察
やべー解法投稿されてるな。証明挑戦するか。
E
見た目がすごい。
どう考察するんだ？
「1 2, 1 2」「2 3, 3 4」みたいなのがあると１個めのグラフだけで偶置換が作れそう
「1 2, 1 2」「2 3, 1 2」とかもそう
完全に同型のグラフじゃない限り偶置換が出来る？
操作どうしの関係性を表したグラフが同型なら自由度が減りそう
例えば「1 2, 1 2」「1 3, 2 3」「1 4, 1 3」（スターとサイクル）とか
「1 2, 1 2」「1 2, 3 4」「3 4, 3 4」とかもよくわからないな
大胆予想をしてストレステスト
「1 2, 1 2」「1 3, 2 3」「1 4, 1 3」「1 4, 2 4」とかもやばい
うーん、小さいケース全探索！→AC
証明大変だー