ABC243 参加記録

コンテスト中AC:A〜D

D - Moves on Binary Tree

公式解説の解法1とほぼ同じでした。

まず、根からへの移動方法の文字列を得ます。具体的には、

が1となるまで以下を行う。

の末尾に、が偶数なら'L'を、奇数なら'R'を追加。
と更新。

上記が終了したら、を反転させる。

その後、について、以下を行います。

が'U'なら、の末尾から文字を一つ取り除く。
そうでないなら、をの末尾に追加。

これによって、は根から答えのノードまでの移動方法の文字列となります。あとはこれに従って、根(番号1)から計算していけば良いです。

計算量は、までの文字列の大きさがで、最終的なの大きさもを超えないことから、だと思います。

提出コード

書いていて気づきましたが、最終的には'U'を含まないので、答えの番号を求めるときの分岐は不要でした。

解法2の考え方も思いついたのですが、ビットシフトしなければいけないと思い断念しました。
単純に末尾に末尾への追加・削除だけで良いことを思いつけなかったです。