2分木をたどれ [yukicoder 392]

問題

http://yukicoder.me/problems/no/392

完全二分木があり、上のリンクの図のように根を0として順に番号が付けられている。
根から探索を始めるものとして、左下に行くならL、右下に行くならRとする。
このとき、m個の点Aiに対して、それぞれ、点0から点Aiへのルートを答えよ。

0 < m <= 4094
0 < Ai <= 4094

考察

1. 完全二分木で図のように番号をつけるやり方は、セグメントツリーで使う手法と同じ
2. ある親xの子は、2x+1と2x+2であることが知られている

今回はその逆を考える

3. 色々実験してみたり、2.の式を変形してみたりするとわかるが、以下のことが言える

ある子xの親は、
　xが偶数なら x/2-1
　xが奇数なら x/2の小数切り捨て
である

4. これで親の頂点が分かり、そこから更に親の親の頂点を計算し、…みたいにやっていく
5. xが偶数なら右に遷移、xが奇数なら左に遷移ということも分かる

6. 全体的な解法としては、子から親まで遷移を記録しながらたどっていって、最後に遷移の記録を逆転させればそれが答え

実装

http://yukicoder.me/submissions/102962

int m;
//-----------------------------------------------------------------
int main()
{
    cin >> m;
    rep(i, 0, m) {
        int a; cin >> a;
        string ans = "";
        while (0 < a) {
            if (a % 2 == 0) {
                ans += "R";
                a = a / 2 - 1;
            }
            else {
                ans += "L";
                a = a / 2;
            }
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
}