問題概要

頂点数が十分多い完全二分木が与えられる。根の番号は 1 であり、一般に頂点 $k$ の左子頂点の番号は $2k$ 、右子頂点の番号は $2k+1$ である。

最初、頂点 $X$ にいて、各回の移動が以下のいずれかのよって定められているような $N$ 回の移動を行う (文字列 $S$ として与えられる)。

親頂点に移動する
左子頂点に移動する
右子頂点に移動する

$N$ 回移動後の頂点の番号を答えよ。

制約

$1 \le N \le 10^{6}$
根にいるとき、親に移動しようとすることはない
答えは $10^{18}$ 以下

考えたこと

まともにシミュレーションすると、途中で $2^{10^{6}}$ 位の大きさの数値になってしまう。そんなものは扱いきれない。そこで、次のことに着目しよう！

"L" をしたあと、"U" をすると、相殺する
"R" をしたあと、"U" をすると、相殺する

このように、「新たに挿入することによって直前のものと相殺する」と来たら、スタックを思い出す。カッコ列のカッコの対応がとれているかをスタックを用いて判定するやつと同様の考え方で解ける。

上記の「相殺」を取り入れることで、最終的には、次のような文字列が残る。

"U" が何個か続いたあと (0 個のこともある)
"L" や "R" が連続する

この残った文字列をシミュレートすればよい。答えが $10^{18}$ 以下であることから、 64 ビット整数の範囲を超えないことは保証される。

計算量は $O(N)$ である。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    long long X;
    string S;
    cin >> N >> X >> S;

    // スタックによるカッコ列整合性判定の要領で文字列を扱う
    string str = "";
    for (auto c : S) {
    if (c == 'U') {
        // 直前の 'R', 'L' を無効にする
        if (str == "") X /= 2;
        else str.pop_back();
    }
    else str += c;
    }

    // 最後にシミュレーション
    for (auto c : str) {
    if (c == 'L') X = X * 2;
    else X = X * 2 + 1;
    }
    cout << X << endl;
}