yukicoder No.392 2分木をたどれ

問題

問題概要

完全２分木上をどのようにたどれば、ルートから指定された場所に移動できるかを求める問題。

解法

完全２分木問題は1オリジンにで考えると、配列を使い親と左子、右子を簡単にたどれる。 今回はそこまで考える必要はない。単に奇数なのか偶数なのかで左子、右子が判定できる。下のコードでは1オリジンとして考えている。また葉の方向からルート側に動かしているので、あとで逆にして出力している。

ミス

なし

コード

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    int m; cin >> m;
    rep(i, m){
        int now; cin >> now;
        now++;

        vector<int> ans;
        while(now != 1){
            if(now % 2 == 0) ans.push_back(0);//L
            else ans.push_back(1);//R
            now /= 2;
        }
        int size = ans.size();
        
        for (int i = size - 1; i >= 0; --i){
            if(ans[i] == 0) printf("L");
            else printf("R");
        }
        printf("\n");
    }
    return 0;
}