Universal Cup 2023 - Ukraine

強連結ならok

コンテスト後証明した

≦だと思ってて、解かれすぎてびびってた

タイトルに騙されなくて偉い！

1,2,...,n は不可能

クエリごとにparityが変わる

n-1で出来ない条件は、逆転してるペアに辺を張ったグラフの次数が全部偶数であること

その場合も隣接する2点を消せばよくてn-2。次数は偶奇だけ分かればいいので$ (a_i-i)\%2で良い。

未証明

なんか正しそうな気はするけど、正確な証明を書くのが難しい

例えば「ある解に距離3のペアがあったらそこに辺を張っても良い」は嘘（C7とか）

「ある解で偶数のところは、1を全部張ったグラフでも偶数」みたいな方針ならいけるのかー

おまけ：

1 のところに辺を全部張った時条件を満たす ⇔ 距離3以上のペアがない ⇔ 連結なP4-free(= cograph) → 線形で判定可能

数え上げ初心者なので、$ \sum x^i \cdot {}_nC_i \cdot i を計算するのに無限時間かかった

$ d/dx (1+x)^n=n(1+x)^{n-1}ってことでいい？

微分すれば良いことだけ知ってたけど不慣れなので・・・

数直線を同じ座標を２回以上通らないように移動する

+2,-1,+2で和が少ない方の1を消費できることに気づきにくい

これを除くと折り返しは両端だけで、その形を2通り（+折り返さないの1通り）ずつ試す

らしい

3以下

---- upsolve ----

最小値までは分かってたけど数え上げられなかった。

挿入していくって方向で考えればよかったのか。

ソースコードだいぶシンプルだし、これくらい解かれるのも納得。。。

$ O(2^NN)（wordsize<Nのもと）

知見

$ dp_{S} = $ 1から出発して通った集合が$ Sであるときの終点の集合

さえあれば全ペアについて$ O(2^NN)で求められる

適当な順番で入れると3~10くらいが全部通ったから提出

感想

楽しみにしてたセットだったが、睡眠に失敗して悲しい

Cが一生わからなくて困った

antonとかだとratedじゃなくて5hに出題することになんか理由がありそう

エスパーで通されやすそう

証明の方が難しい：A,D,K,H?

結論がシンプルすぎ：C,F

annoying：M

too classic？：E,I,B

風変わりすぎ？：J,N,L

TL設定とかむずそう的な？：G