ABC243D

ABC243D の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc243/submissions/30097544

問題

バイナリーツリーの内部処理に必要なグラフの移動を説く教育的な問題です．

解説

移動を示す文字列が，
Uなら「割る2」
Lなら「かける2」
Rなら「かける2 + 1」
と一見シンプルな問題ですが，xの値が非常に大きいことがネックになります．

直近のABCではD問題でも灰-茶であることは珍しくないので，
「これ楽勝じゃね？」
と思ってそのままシミュレートしてTLEくらいました．

時間内に処理を終わらせるには，不要な計算を削減するために無駄な移動を減らす必要があります．

概要図です．

ABC243D_overview

では，コードです．まず標準入力を読み取ります．

N, x = map(int, input().split())
S = list(input())

これから，不要な上下運動を削除します．
書き方はいろいろあると思います．例を３つ書きます．
その1）ひとまず s を append して，一番後ろが'U'で，その前が'U'以外なら２個削除する方法．

# その1
T = []
for s in S:
    T.append(s)
    if len(T) > 1:
        if T[-1] == 'U' and T[-2] != 'U':
            T.pop()
            T.pop()

その2）continue を使う．

# その2
T = []
for s in S:
    if s=='U':
        if T:
            if T[-1] != 'U':
                T.pop()
                continue
    T.append(s)

その3）公式解説のように条件文をandでつないで，elseで分岐するなど...

# その3
T = []
for s in S:
    if s=='U' and T and T[-1] != 'U':
        T.pop()
    else:
        T.append(s)

こうして，無駄な動きを排除したTに対して，シミュレートすればOKです．

for t in T:
    if t == 'U':
        x //= 2
    elif t == 'L':
        x = x*2
    elif t == 'R':
        x = x*2 + 1
print(x)

以上，ABC243Dの解法でした．
公式にあるbitの解き方は，まったく発想としてありませんでした．
あの解放が浮かんでくるように精進します...

余談ですが，個人的にこういったアルゴリズムの中身を部分的に抽出した教育的な問題は好きです．
すなわち，コードのコピペで解けるような問題ではなく，きちんとアルゴリズムの中身を理解してるか聞いてくる感じの問題です．そして，解くと勉強になります．
例えば，ワーシャルフロイド法の内容を聞いてくる D - Shortest Path Queries 2 が志向が近い問題です（ただし，ワーシャルフロイド法を使うABC243Eが解けたとは限らないww）．

＜参考解説リンク＞
・公式