No.392 2分木をたどれ

毎日ブログを書かないとなあ。

No.392 2分木をたどれ - yukicoder

個人的には2進数っぽくて好きな問題。

例えば、13から0に向かうことを考えます。（ちなみに13はRRLです。）

13を2進数変換すると1101になるわけですが、これを右シフトします。すると6になります。6を2進数にすると110です。これを右シフトすると3になります。ところが6の上は2なのでうまく辿れていません。そこで6から1を引き、5を右シフトします。すると、2になります。2を2進数にすると10なので、これを右シフトしてやっても上手くいかないのでやはり1を引いてから右シフトします。

というわけで、偶数の時は1を引いて右シフト、奇数の時はそのまま右シフトすると辿っていけるわけです。与えられている木を見ると、偶数の時は右側、奇数の時は左側にあるので、文字列にRLをその通りつなげていくとOKです。ただ私のように文字列をどんどん後ろに追加するようにしてしまうと、最後に逆転させる必要があるので要注意ですね。

Python3での回答コード

#115556 No.392 2分木をたどれ - yukicoder

def solve():
    for _ in range(int(input())):
        i = int(input())
        res = ""
        while i > 0:
            if i % 2 == 0:
                i -= 1
                res += "R"
            else:
                res += "L"
            i >>= 1
        print(res[::-1])


if __name__=="__main__":
    solve()

★1.5くらいなような気もしますが、考察がたまたまうまく行っただけだなあ。