ARC105 E - Keep Graph Disconnected - ♥沙耶花の備忘録♥

↓にゃ

最終的に頂点 $1$ を含む連結成分のサイズを $a$ , 頂点 $N$ を含む連結成分のサイズを $b$ とすると, 二人が選べる辺の本数は $\frac{N(N-1)}{2} - M - ab$ 本となりまふ. この偶奇, すなわち $ab$ の偶奇によって勝敗が決まりまふ. 実際には, $a+b=N$ なので $N$ の偶奇でまず場合分けをすることにしまふ.

$N$ が奇数の時, $a,b$ のうち一方は奇数, もう一方は偶数になるので $ab$ は奇数となり, 勝敗がこの時点で分かりまふ.

$N$ が偶数の時, $a,b$ が両方奇数なら $ab$ は奇数に, 両方偶数なら $ab$ は偶数になりまふ. ここで, $1$ も $N$ も含まない, サイズが奇数の連結成分の個数を $x$ としまふ.

$x$ が0の時, 先手も後手も $a,b$ の偶奇を変えられないので初期時点での $a,b$ の偶奇が都合の良いほうが勝ちまふ.

$x$ が1の時, $a,b$ は一方が奇数でもう一方が偶数なので, 先手が両方奇数にするか両方偶数にするか選べまふ. 先手は都合の良いほうを選ぶので, 先手が勝ちまふ.

$x$ が2の時, $a,b$ の偶奇が先手にとって都合がよければ2つの奇数サイズの連結成分をマージすれば $x=0$ の状況になり, 先手が勝ちまふ. そうで無いとき, $x=1$ にしてしまうと後手が勝ちまふし, $x=2$ のままにしても $a,b$ の偶奇が後手にとって都合が良いので後手が勝ちまふ.

このように順に調べていくと, 一般に $x$ が奇数なら先手が勝ち, 偶数なら $a,b$ の偶奇が都合の良いほうが勝つことが導けまふ.

↓提出コード

atcoder.jp