ARC103 E. Tr/ee
問題
各文字は0または1の長さnの文字列sが与えられる。
n頂点の木について考えたとき、
- i文字目が0なら、木からどのように辺を1つ取り除いてもサイズiの連結成分が作れない
- i文字目が1なら、木からある辺を1つ取り除いてサイズiの連結成分を作れる
を満たすような木を実際に1つ構築せよ。
構築できない場合は-1を出力せよ。
制約
- 2 <= n <= 10^5
解法
小さいケースで考えてみると、
- 一番最後の文字が1の場合は構築できない
- リーフの頂点につながる辺を除くと連結成分が1のものが必ずできるので、最初の文字は必ず1でないといけない
- 辺を取り除いてサイズxの連結成分ができたら、対称的にN-xの連結成分ができるので、文字列は最後の文字を除いて対称になっていないといけない
ということがわかる。
以下、上記の条件を満たすような文字列について考える。
今、満たしたい連結成分集合が{1,3,5,...}のような場合を考える。
「1」は、リーフの部分の辺を切ればよい。
「3」は、木の形を考えてみると、以下のようなものになる(赤枠と交差している辺を切ればよい)。
「5」は、上記の形を残しつつ、5個の頂点を入れる必要があるので、以下のように青枠を考えればよい。
もし、「5」ではなく「6」だった場合は、以下のように頂点を増やせばよい。
上記のように、与えられた連結成分集合の小さい方から考えて、それまでの形を残しつつ、順次構築していけば目的の木が作れる。
上記の木は、「キャタピラ木」といい、線グラフの各頂点にいくつか頂点を生やしたような木になっている。
Caterpillar tree - Wikipedia
生やした部分はリーフなので、必ず連結成分は1のものができ、線グラフの部分の辺を消すことが題意に相当する。
反省
木の形はある程度限られるので、時間がもう少しあれば、いろいろな木を書いて見ている中でたどり着けたかもしれないけど、、、
「順次構築」的な発想をするようにしていれば効率的にたどり着けたかもしれない。
