高橋君がいまいる頂点の番号を保持しながら、移動をそのままシミュレートしようとすると、頂点の番号の桁数が非常に大きくなるためTLEします。

効率よくシミュレートするにはどうすればよいでしょうか？

解法1

L または R の直後に U がある場合、この \(2\) 回の移動で元の頂点に戻るため、このような移動は無視してもよいです。stack などを用いて \(S\) の先頭から順に調べることで、そのような箇所全てを \(O(N)\) で取り除くことができます。

取り除いた後に残る文字列を \(S'\) とすると \(S'\) は「\(0\) 個以上の U からなる文字列」の後ろに「\(0\) 個以上の L または R からなる文字列」を連結したものになっています。\(S'\) による移動の過程において、頂点番号が \(\max(最初にいる頂点,最後にいる頂点)\) を超えることはありません。したがって、高橋君がいまいる頂点の番号を保持して、移動をそのままシミュレートすることで高速に答えを求めることができます。

計算量は \(O(N)\) です。

実装例(Python)

解法2

高橋君がいまいる頂点の番号を \(2\) 進法で表した文字列 \(T\) で管理することを考えます。このとき各移動による \(T\) の変化は次のようになります。

• U のとき、\(T\) の末尾の文字を削除する
• L のとき、\(T\) の末尾に 0 を追加する
• R のとき、\(T\) の末尾に 1 を追加する

これらの操作は全て \(O(1)\) で行えます。したがって、十分高速にこの問題を解くことができます。操作全体の最初と最後で、\(2\) 進法で表された文字列と整数の相互変換を行うため、全体の計算量は \(O(N+\log X+\log \text{答え})\) となります。

実装例(Python)