AtCoder World Tour Finals 2022
day1
A
それっぽいの書いたら通った
B
サイクルごとにサイズ-1回で出来れば良い。
奇数
真ん中 (c) で分けて左だけで完結・右だけで完結を交互に取る。
真ん中をまたぐ辺だけになるので、$ (c, P_c) をやり続けられる
偶数
思ったより困る
N回でいいなら内部で完結を交互に取るのを全体に対してやって(1,1)してからサイクルごとに$ (c, P_c) みたいな感じで出来るが、かなりタイトな設定だ
奇数と同じで出来ない場合、多い方の中だけで完結するのを１個だけ残す
$ (c, P_c)の途中でそれが来たら２個同時に回収する
$ P_{P_c}, P_c, cの並び：$ (P_{P_c}, P_c),$ (P_c, c) とやる
$ P_c, P_{P_c}, cの並び：$ (P_{P_c}, c),$ (P_c, P_{P_c}) とやる
$ 2,4,1,3 はサイクルの辺だけでは出来ないので、ヒントになるかも。
２時間半かかっちゃった・・・
解説見たらかなり短くてすげー
C
二彩色すると、違う色同士を取る問題になる。
まず残す部分を決めたときの判定問題を解く
根付き木の森を全部取れるか。
白の個数＝黒の個数
根は黒と白の両方が１個以上ある
（根付き木に対する何らかの値） ≦ 頂点数
あたりが満たされれば良さそうに見える。
数えるのは、残った頂点のうち頂点1に最も近いものを固定して数えると重複がない。
適当に四乗状態のdpをすればよさそう。
何らかの値：
例えば W→B→W, B みたいなのは不可能で、f(W→B→W) = 6 っぽい。
最初はサイズ*2とか最長パス*2とかかと思ったけど、f(B←W→B→W) = 6 っぽい
よく分からんので、貪欲で計算してみたら通った。
葉が２色あったらそれらをマッチさせる
１色なら外部から１頂点取ってくる必要がある
深い葉を優先して使う
何らかの値＝サイズ＋外部から取ってきた頂点数
ギリギリで修正してコンパイルせずに投げたら１個だけ落ちた。
N=2のコーナーケースで落ちてて悲しい。
D
こんなの解けたらびっくりする
E
こんな設定で難しいのびっくりする
day 2
昨日より一段階むずいマジ？
A
よくある設定、むずそう。
まずグリッド上の左上から右下の経路に言い換えます。（maroonなので（いいえ））
後ろの方から決まっていきそう
yes/noで得られる情報
前にいる人の情報は全部分かってるので増えない
後ろの人のyes/noにより、座標が絞り込める
誰の帽子も見てない人のつもりで、ありえない座標にxを書いていくことを考える
yes：右と下のうち片方がxであるような座標しかないことが確定、以降のラウンドで情報は増えない
no：右と下のうち片方がxであるような座標ではないことが分かる
右も下もxなときもxにするっていうのもすれば、次の人だけ気にすればよくなる(α)
yes/noは全員同時じゃなくて、前の人から答えていくってしてもいい
大体は10分くらいで思いついていたけど、(α)が思いついてなくて三乗にならなくて実験とかをしていた
B
多項式になるだけでびっくり出来る（りんごさんなら2000とかで出しそう）
大きい方から考える
xをx以上の中で何番目にすることが出来るかを考える
0~xと∞だけだと思って良い
∞をちょうど１個に出来ればそいつとswapできる
他の∞を両端にどれだけ寄せられるか知りたいが、難しい
何番目に出来るかの区間が分かれば、区間の長さの積が答え
xごとに独立な理由：
大きい順に並べ替えていくことが出来る
その際他のものの配置を元通りにできることに注意
∞を端に寄せ、xとyをswapした後逆操作をすると、x,yだけがswapされた状態になる
∞を右に寄せる＝他を左に寄せる、みたいな気持ちになり、
小さい順に求めていく
求めた後、なるべく左に動かしたのと右に動かした順列を計算しておく
この順列から範囲も求まる
ストレステストをかけると通ったので、あとは熱烈データ構造・・・（ねむすぎたのもあり、２時間）
順列L,Rがあり、「Lでのi個目の∞の位置」ー「Rでのi個目の∞の位置」みたいなのの区間min ≧ w? みたいなのが知りたくなる
「Lのi+wまでの∞の個数」-「Rのiまでの∞の個数」≦2 ならいい、とかに言い換える
区間add区間maxのsegtreeとかがあれば出来る
C
貪欲で出来るマッチングを２つ組み合わせた感じ（マトロイド交差ってこういうやつ？）
なんもわからん
D
制約が5000で嬉しい！（250000をやめろ～）
hosさん今日はこれやってるんだろうなとなった
jianglyすげー
E
あまり考えてない
touristのコード短かった
すごい問題出してくるねぇ
まとめ
激シンプルで高配点の問題がたくさんあってすごい
全問題ACが出ててすごい
５時間でむずい問題をじっくり解くのも楽しいものだなぁ
day1C間に合わせたかったな～