再帰関数の使い方に慣れるための教育的問題。

この手の再帰的なフラクタルっぽい構造を読み解く問題は「十分回数を重ねると最初の方の模様が収束する」みたいなことをするイメージがあるけど、今回はそういうのじゃなくて純粋に再帰関数の使い方を問われる問題だった。

問題概要

とある世界では、今日はクリスマスです。

高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル L バーガー (L は 0 以上の整数) とは次のようなものです。

レベル 0 バーガーとは、パティ 1 枚である。
レベル L バーガー (L≥1) とは、バン 1 枚、レベル L−1 バーガー、パティ 1 枚、レベル L−1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。

例えば、パティを P、バンを B で表すと、レベル 1 バーガーは BPPPB (を 90 度回転したもの)、レベル 2 バーガーは BBPPPBPBPPPBB といった見た目になります。

高羽氏が作るのはレベル N バーガーです。ダックスフンドのルンルンは、このバーガーの下から X 層を食べます (パティまたはバン 1 枚を 1 層とします)。ルンルンはパティを何枚食べるでしょうか？

制約

$1 \le N \le 50$

まずは様子をつかむ

バーガーの長さは、 $L$ に応じて概ね 2 倍くらいのペースで増えて行く。ちゃんと求めることもできて、レベル $i$ のバーガーの長さを $a_i$ とすると

$a_0 = 1$
$a_{n+1} = 2 a_{n} + 3$

なので、これを解く (高校数学の数列の単元で手でくる) と、

$a_{n} = 2^{n+2} - 3$

となる。確かに $a_{0} = 1, a_{1} = 5, a_{2} = 13$ となって合ってそう。同様にレベル $n$ のバーガーに含まれるパティの量 $b_n$ は、

$b_{n} = 2^{n+1} - 1$

となる。

再帰的に

この問題、つまりは再帰的な構造を的確に利用して再帰関数を設計できるかを問う問題だと言える。

rec(int n, long long x) := レベルが n のバーガーの下から x 枚に含まれるパティの量

とすると、x の値に応じて、レベルが n - 1 のバーガーに関する問題に投げることができる。

#include <iostream>
using namespace std;

long long rec(int n, long long x) {
    if (n == 0) return 1;
    long long len = (1LL<<(n+1)) - 3;
    long long num = (1LL<<n) - 1;
    if (x == 1) return 0;
    else if (x <= len + 1) return rec(n-1, x-1);
    else if (x == len + 2) return num + 1;
    else if (x <= (len + 1) * 2) return num + 1 + rec(n-1, x-len-2);
    else return num * 2 + 1;
}

int main() {
    int N; long long X;
    cin >> N >> X;
    cout << rec(N, X) << endl;
}