https://beta.atcoder.jp/contests/arc103/tasks/arc103_c
長さ$N$の文字列$S$が与えられる。以下のような$N$頂点の木が構築可能である場合は構築せよ。
$N$頂点の木から辺を1つ取り除いてサイズ$M$の連結成分ができたとき、もう1つの連結成分はサイズ$N-M$になる。ここから、構築可能であるための必要条件がいくつかわかる。
これは充分条件でもあり、構築の方法は以下のようである。
例として、$S=$'100101100011010010'を考える。$N=18$かつ$\{ 1,4,6,7,11,12,14,17 \}$文字目が'1'なので、以下のようなグラフが答えとなる。
赤線でグラフを切ると、その左側の連結成分のサイズが$\{ 1,4,6,7,11,12,14,17 \}$となっているのがわかる。赤線以外のところで切ってもサイズが必ず1になるので問題ない。このように構築すれば、上に挙げた条件を満たすグラフをすべて作ることができる。
これはコンテスト中に思いつきたかった。