AtCoder ABC115D - Christmas

本番通せなかった上に、再帰ではなく二分探索を用いて解いたので書いておきます。

問題概要

解説

$1 \leq N \leq 50$ より、単純に下から $X$ 層を探索をすると間に合わないことがわかります。ここで、バーガーのレベルが上がるごとに、バーガーの全長が指数的に長くなることを考えると、二分探索で解けそうな気がしてきます。実際この問題は二分探索で解くことができて、次のように $5$ つの場合に分けて考えます。ただし、現在レベル $i$ バーガーを見ているとし、下から $X$ 層目の位置を考えます。また、 $mid$ はレベル $i$ バーガーの中心のパティを指すようにします。

下から $X$ 層目が、

1. $i$ バーガーの最も下にあるバンであるとき

　二分探索を終える。

2. $i$ バーガーの最も下にあるバンよりも上で、 $i$ バーガーの中心のパティよりも下にあるとき（下の $i-1$ バーガーに含まれるとき）

　次に $mid$ が下の $i-1$ バーガーの中心を指すように、 $ub=mid-1, lb++$ とする。

3. $i$ バーガーの中心のパティであるとき

　下の $i-1$ バーガーすべてと $i$ バーガーの中心のパティを食べるので、答えにそれらを加え二分探索を終える。

4. $i$ バーガーの中心のパティよりも上で、 $i$ バーガーの最も上にあるバンよりも下にあるとき（上の $i-1$ バーガーに含まれるとき）

　次に $mid$ が上の $i-1$ バーガーの中心を指すように、 $lb=mid+1, ub--$ とする。また、下の $i-1$ バーガーすべてと $i$ バーガーの中心のパティを食べるので、答えにそれらを加える。

5. $i$ バーガーの最も上にあるバンであるとき

　 $i$ バーガーをすべて食べるので、それを答えに加えて二分探索を終える。

$n=0$ で 2, 4 の分岐に入ったときは、レベル $0$ のパティを足すことに注意が必要です。

ソースコード

二分探索をする前に $n$ バーガーまでのパティの含まれる数、バーガーの全長を求めておきます。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n, x; cin>>n>>x;
    vector<ll> cntP(60, 0), l(60, 0);
    cntP[0]=1, l[0]=1;
    for(int i=1; i<=n; i++){
        cntP[i]=cntP[i-1]*2+1;
        l[i]=l[i-1]*2+3;
    }

    ll lb=1, ub=l[n];
    ll ans=0;
    while(n--){ // [lb, ub]
        ll mid=(lb+ub)/2;

        if(x==lb){
            break;
        }
        else if(lb<x && x<mid){
            ub=mid-1;
            lb++;
            if(n==0) ans++;
        }
        else if(x==mid){
            ans+=cntP[n]+1;
            break;
        }
        else if(mid<x && x<ub){
            lb=mid+1;
            ub--;
            ans+=cntP[n]+1;
            if(n==0) ans++;
        }
        else if(x==ub){
            ans+=cntP[n+1];
            break;
        }
    }
    cout << ans << endl;
}