AtCoder Beginner Contest 243 D - Moves on Binary Tree【Python】

https://atcoder.jp/contests/abc243/tasks/abc243_d

AtCoder ProblemsでDifficulty: 758でした。

解けませんでした。
解説

atcoder.jp

の解法2の2進数に変換した文字列で考えるというのは部分的に他の問題でもあった記憶があるため思いつきたかったところです。

解説の解法1

from collections import deque
N, X = map(int, input().split())
S = input()
d = deque()

for i in range(N):
    s = S[i]
    if len(d) == 0:
        d.append(s)
    else:
        dl = d[-1]
        if (dl == 'R' or dl == 'L') and s == 'U':
            d.pop()
        else:
            d.append(s)

for s in d:
    if s == 'U':
        X //= 2
    elif s == 'L':
        X *= 2
    else:
        X = X * 2 + 1
print(X)

解説の解法2

N, X = map(int, input().split())
S = input()

T = list(bin(X))
for i in range(N):
    s = S[i]
    if s == 'U':
        T.pop()
    elif s == 'L':
        T += '0'
    else:
        T += '1'
print(int(''.join(T), 2))