Australia

ウォンバットのブログ

AtCoder Regular Contest 103 E - Tr/ee

問題

https://beta.atcoder.jp/contests/arc103/tasks/arc103_c

解法

木が構築可能であるための、次の必要条件が浮かびます。

$s_1=1$
$s_n=0$
$s_i=s_{n-i}$

実はこれらは十分条件でもあります。具体的には、次のようにして構成できます。

頂点 $1, 2$ 間を繋ぐ。
直前に頂点 $t, i(t < i)$ 間を繋いでいたとする。 $s_{i}=1$ の場合、頂点 $i, i+1$ 間を繋ぐ。 $s_{i}=0$ の場合、頂点 $t, i+1$ 間を繋ぐ。

このようにすれば、 $s_{i}=1$ のとき、頂点 $i, i+1$ 間の辺を切ればサイズ $i, n-i$ の連結成分ができます。 $s_{i}=0$ のとき、頂点 $t, i+1$ 間の辺を切ってもサイズ $1, n-1$ の連結成分しかできません。

実装

https://beta.atcoder.jp/contests/arc103/submissions/3297484

反省

構築は色々なパターンがあって一般論を見出すのが難しいですが、とりあえず手を動かしてみるのがいいような気がします。