◇◇ref013:AtCoder Regular Contest 103 - E : Tr/ee◇◇

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

長さ$N$の文字列$S$が与えられる。以下のような$N$頂点の木が構築可能である場合は構築せよ。

• $S$の$i$文字目が'1'であるとき、木からある辺を1つ取り除くことで、サイズ$i$の連結成分が作れる
• $S$の$i$文字目が'0'であるとき、木からどのように辺を1つ取り除いてもサイズ$i$の連結成分が作れない

$N$頂点の木から辺を1つ取り除いてサイズ$M$の連結成分ができたとき、もう1つの連結成分はサイズ$N-M$になる。ここから、構築可能であるための必要条件がいくつかわかる。

• $S_1$が'1'であること
• $S_N$が'0'であること
• $S_M=S_{N-M}$であること

これは充分条件でもあり、構築の方法は以下のようである。

例として、$S=$'100101100011010010'を考える。$N=18$かつ$\{ 1,4,6,7,11,12,14,17 \}$文字目が'1'なので、以下のようなグラフが答えとなる。

赤線でグラフを切ると、その左側の連結成分のサイズが$\{ 1,4,6,7,11,12,14,17 \}$となっているのがわかる。赤線以外のところで切ってもサイズが必ず1になるので問題ない。このように構築すれば、上に挙げた条件を満たすグラフをすべて作ることができる。

これはコンテスト中に思いつきたかった。

戻る