D - Moves on Binary Tree Editorial by kyopro_friends
高橋君がいまいる頂点の番号を保持しながら、移動をそのままシミュレートしようとすると、頂点の番号の桁数が非常に大きくなるためTLEします。
効率よくシミュレートするにはどうすればよいでしょうか?
解法1
L
または R
の直後に U
がある場合、この \(2\) 回の移動で元の頂点に戻るため、このような移動は無視してもよいです。stack などを用いて \(S\) の先頭から順に調べることで、そのような箇所全てを \(O(N)\) で取り除くことができます。
取り除いた後に残る文字列を \(S'\) とすると \(S'\) は「\(0\) 個以上の U
からなる文字列」の後ろに「\(0\) 個以上の L
または R
からなる文字列」を連結したものになっています。\(S'\) による移動の過程において、頂点番号が \(\max(最初にいる頂点,最後にいる頂点)\) を超えることはありません。したがって、高橋君がいまいる頂点の番号を保持して、移動をそのままシミュレートすることで高速に答えを求めることができます。
計算量は \(O(N)\) です。
解法2
高橋君がいまいる頂点の番号を \(2\) 進法で表した文字列 \(T\) で管理することを考えます。このとき各移動による \(T\) の変化は次のようになります。
U
のとき、\(T\) の末尾の文字を削除するL
のとき、\(T\) の末尾に0
を追加するR
のとき、\(T\) の末尾に1
を追加する
これらの操作は全て \(O(1)\) で行えます。したがって、十分高速にこの問題を解くことができます。操作全体の最初と最後で、\(2\) 進法で表された文字列と整数の相互変換を行うため、全体の計算量は \(O(N+\log X+\log \text{答え})\) となります。
posted:
last update: