Christmas [AtCoder Beginner Contest 115 D]

https://beta.atcoder.jp/contests/abc115/tasks/abc115_d

解説

https://beta.atcoder.jp/contests/abc115/submissions/3745333

再帰的な構造を含む問題は、大体再帰関数を使って解く。
f(level, x) := レベルlevelバーガーの下からx番目まででパティが何枚あるか（xは0-indexed）
これを作ることで解決していこう。
　
これを計算するために、patty配列とtot配列を用意する。
patty[level] := レベルlevelバーガーに含まれるパティの数
tot[level] := レベルlevelバーガーの層数
この2つは定義を見ながら構築していこう。
　
関数fの実装。
level=0なら、パティ1枚なので1を返す。
それ以外なら、下からx番目のxが5パーツに別れてるうちのどこに含まれるかを見る。
① x=0 : バン1枚
② 1≦x≦tot[level-1] : レベルL-1バーガー
③ x=tot[level-1]+1 : パティ1枚
④ tot[level-1]+2≦x≦2*tot[level-1]+1 : レベルL-1バーガー
⑤ x=tot[level-1]+2 : バン1枚
　
②の途中、④の途中にxが来た場合は、再帰関数を使って、そのレベルL-1バーガーの下からx'番目までのパティを得る。
典型問題ではあるが、初めてで1から実装するのは難しい。
類題

int N; ll X;
//---------------------------------------------------------------------------------------------------
ll patty[51], tot[51];
ll f(int level, ll x) {
    if (level == 0) return 1;
 
    if (x < 1) return 0;
    x--;
 
    if (x < tot[level - 1]) return f(level - 1, x);
    x -= tot[level - 1];
 
    if (x < 1) return patty[level - 1] + 1;
    x--;
 
    if (x < tot[level - 1]) return patty[level - 1] + 1 + f(level - 1, x);
    x -= tot[level - 1];
 
    return patty[level - 1] * 2 + 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    X--;
 
    tot[0] = 1;
    rep(L, 1, N + 1) tot[L] = tot[L - 1] * 2 + 3;
    patty[0] = 1;
    rep(L, 1, N + 1) patty[L] = patty[L - 1] * 2 + 1;
 
    cout << f(N, X) << endl;
}