だいたい完全二分木 [yukicoder No.566] - はまやんはまやんはまやん

解説放送

未定

解説

https://yukicoder.me/submissions/203590

まずは、完全二分木を構成することを考えてみる。
普通に完全二分木を構成すると高さはK-1である。
完全二分木を構成するときは、再帰を使って構成すると良い。

例えば
1 2 3 4 5 6 7
であれば、真ん中の4を最初に入れる
1 2 3   5 6 7
すると2つのグループに分かれる。
これは独立に処理できるため、まず、[1,3]を入れることを考える。
ここでも真ん中の2を最初に入れる
1   3   5 6 7
するとまた2つのグループに分かれる。
1と3はまたしても独立に処理できるため、[1,1]を入れることを考える。
これは1つだけなので、1を入れる。
    3   5 6 7
次に[3,3]のグループの3を入れる。
        5 6 7
次に[5,7]のグループの真ん中6を入れる。
        5   7
次に[5,5]の5,[7,7]の7を入れると完全二分木を構成する順番となる。

この例から言えることが、「f(L,R) := [L,R]を順番に入れる」の中身の処理は
1. [L,R]の中心(mdとする)を入れる
2. f(L, md-1)を処理する
3. f(md+1, R)を処理する
であり、これを再帰関数として定義して処理する。
　
今回の問題。
高さはK以上にする必要があるため、ほぼ上のルールで処理していくが、少しだけ変えて高さを稼ぐ。
完全二分木の上の方を変更すると部分木に影響があり少しめんどくさいので、葉に近い部分だけ変える。
具体的には、[1,3]を処理するときに2,1,3と入れるのではなく、1,2,3と入れることにする。
これで[1,3]の部分木の高さが1ではなく2になるので、高さがKとなりAC。

vector<int> ans;
void f(int L, int R) {
    if (L == 1 && R == 3) {
        ans.push_back(1);
        ans.push_back(2);
        ans.push_back(3);
        return;
    }

    if (L == R) {
        ans.push_back(L);
        return;
    }

    int md = (L + R) / 2;
    ans.push_back(md);
    f(L, md - 1);
    f(md + 1, R);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int K; cin >> K;
    int ma = 1;
    rep(i, 0, K) ma *= 2;
    f(1, ma - 1);

    int N = ans.size();
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}