ABC243Dを解いた

筆者はレート600前後の茶色コーダ

7/9のADTで出題された以下のABCの過去問題を解いていく

ADT(ALL)のページ

実装コード

完全二分木なので、親ノードに行くには半分にして
子ノードに行くには左の子なら2倍して、右の子は2倍して更に+1すればOK、
と思ったがTLE、数が大きいので掛け算に時間がかかるようだ。bit演算にしてもTLEは解消せず¹

TLEコード

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    N, X = rLI()
    S = rS()
    ans = X
    for s in S:
        if s == 'U':
            ans //= 2
            #ans >>= 1 bit演算にしても同じくTLE
        else:
            ans *= 2
            #ans <<= 1
            if s == 'R': ans += 1
            #if s == 'R': ans |= 1
    print(ans)
if __name__ == '__main__':
    main()

ここで解説を見たが、bit演算の要領で文字列を管理して、最後に計算すればいいみたい。解説通りに実装するのは面白くないのでリストと整数値を使った計算をして最後に進数変換した値を出力する感じにしてみた。

ACコード

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    _, X = rLI()
    S = rS()
    bx = bin(X)[2:]
    bits = [int(x) for x in bx]
    for s in S:
        if s == 'U':
            bits.pop()
        elif s == 'L':
            bits += [0] 
        elif s == 'R':
            bits += [1]
    ans = [b*(1<<i) for i,b in enumerate(reversed(bits))]
    print(sum(ans))
if __name__ == '__main__':
    main()

まとめ

ABC243Dを解いた、普通に計算するとTLEが出たので値を一回リストで管理して最後に値を求めるようにすることで解くことがた。

感想

完全二分木なので簡単に解けるだろうと思ったが普通にTLEが出て解説を見たが、
大きめの値を掛け算すると時間がかかるという認識がなかった。
次からは大きめの値を掛け算する必要があるときは工夫して値を出すようにしたい。

1. たしかPythonのbit演算って多倍長整数を使っている関係上、結局裏で四則演算していた記憶(要出典)。だからこの修正は意味なかった。 ↩