D - Christmas - 予鈴

問題

非負整数 $N,X$ が与えられる。2つの文字 $P,B$ に対して、N番目の文字列を
$S_N := B + S_{N-1} + P +S_{N-1} + B$ とする。
下から $X$ 文字に含まれる文字 $P$ の数を求めよ。
beta.atcoder.jp

解法

・各 $n$ に対して $P$ の数と含まれるすべての文字の数を定義に従って前計算する。
・再帰関数で含まれる文字数を計算することができる。
・ $x \geq S_{n-1} + 2$ のとき、 $S_{n}$ のうち下半分の $S_{n-1}$ と中間の $P$ は完全に答えに含まれる。
・残った数、つまり $x - S_{n-1} - 2$ の場合と $x < S_{n-1} + 2$ の場合はわからないので次数を下げて投げる。
・ $i == 0$ のときはこれ以上次数を下げることができない。定義からレベル0はPのみで構成されるので、xが0より大きい場合のみ1を返す。

・これすき、今度はコンテスト中にときたい。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
using namespace std;
signed main(){
    vector<int>dp(51,1LL),dp2(51,1LL);
    int n,x; cin >> n >> x;
    for(int i = 1; i < dp.size();++i){
        dp[i] = dp[i-1] + dp[i-1] + 3;
        dp2[i] = dp2[i-1] + dp2[i-1] + 1;
    }
    function<int(int,int)>cal = [&](int i,int x) -> int{
        if(x == 0){ return 0;    }
        if(i == 0){ return x > 0;}
        return (x >= dp[i-1] + 2 ? dp2[i-1] + 1 + cal(i-1,x-dp[i-1]-2) : cal(i-1,x-1));
    };
    cout << cal(n,x) << endl;
}