ARC103 E - Tr/ee
解法
考察は終わっていましたが実装が間に合いませんでした。
まず、木を作るのに必要な要素は3つあります。
sの最後の文字が0
辺を1つ選んだ時点で、サイズはnより小さくなってしまうので、条件を満たすことができません。sの最初の文字が1
葉につながっている辺を切断すると、サイズが1の連結成分が必ず作成されます。
なので、ここが0であった場合、条件を満たすことができません。sの1文字目からn-1文字目までが回文になっている
というのは、i文字目とn-i文字目の文字が一致している、ということです。
辺を1つ切ると、連結成分は2つにわかれます。
サイズiの連結成分が作成されたとき、もう片方のサイズはn-iになります。
なので、このような条件が満たされていないと、答えは-1になります。
逆に、以上の条件を満たすことができれば、必ず問題の条件を満たすような木を作成することができます。
木を作成する際に、現在までに追加し終えた頂点と、まだ追加してない頂点の個数を利用し、条件を満たすような木を作成していきます。
具体的には以下のようにして作成することができます。
まず、変数を2つ用意して、1つは次に追加する頂点の番号(cntとします)、もう1つはcntを次に繋ぐべき頂点の番号(nowとします)というように定義します。
初期はcnt が2、nowが1です。
sのi文字目が1か0で場合分けをします。
1のとき
cntとnowを辺で繋ぎます。
最後に、nowにcntに代入し、その後でcntに1を加えます。0のとき cntとnowを辺で繋ぎます。
cntに1を加え、操作を終了します。
この操作を繰り返すだけで、条件を満たす木を作成することができます。
