ABC115 D - Christmas

初めに思いついたこと：

・Ｎ＜＝５０と小さい。

・漸化式を用いて、ＮバーガーのＰとＢの総数と、ＮバーガーのＰの総数は表せる。

（前者をnum[N],後者をf[N]と表す。）

・後ろから数え上げればいいな。

ー＞シミュレーションか？

ー＞シミュレーションは厳しそう。

理由：後ろから見ていっても、構造が単純ではなさそうだから。

～～さらによく問題を読んでみると～～

・（レベル）Ｎバーガーをひとつの塊とみると、ＮバーガーはＮ－１バーガーで表せて、これが全てのＮについて言える。

なので・・・

・全てのＮバーガーについて、後ろからＸの位置までのＰの個数の求め方はＮ－１バーガーに含まれるＰの個数の情報で表せる。

これは再帰関数で表せそう！

具体的には：

nバーガーの後ろからpos番目までのＰの総数を、rec(n,pos)と表す。

このとき

(0)pos==０のとき0個

　n==０のとき、０バーガーより１個

(1)pos>=num[n-1]*2+2のとき

ｎバーガーを　B （[n-1]バーガー） P （[n-1]バーガー）  Bと表すと（以後、[n-1]とす)

posの位置は[n-1]を完全に二つとも含む。

また、左の[n-1]よりも左にはＢしかないので、ここから左にはＰは存在しない

よってrec(n,pos)=f[n-1]*2+1と表される。

(１は真ん中のＰ）

(2)pos>=num[n-1]+2のとき

[n-1]は一つだけ完全に含まれ、左の[n-1]は途中までふくまれる。

ここで、左の[n-1]がどれだけ含まれているか、すなわち後ろから何番目まで含まれているかをpos2と表すと、左の[n-1]の中のpos2までのＰの個数は

rec(n-1,pos2)と表される。（定義より）

よって、rec(n,pos)=rec(n-1,pos2)+f[n-1]+1と表される。

(ただし、pos2=pos-(num[n-1]+2))

(3) 上記以外のとき

右の[n-1]が中途半端に含まれ、真ん中のＰは含まれないため

右のバーガーがpos3まで含まれているとすると

rec(n,pos)=rec(n-1,pos3)と表される。

（ただし、pos3=pos-1)(右のＢを除いただけ）

以上をもとに再帰関数を組めばよい。

求める答えはrec(N,X)

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

int N, X;
int f[100], num[100];

int rec(int n, int pos) {
  if (pos == 0) return 0;
  if (n == 0) return 1;

  if (pos >= 2 * num[n - 1] + 2) {
    return f[n];
  } else if (pos >= num[n - 1] + 2) {
    int tmp = pos - (num[n - 1] + 2);
    int res = f[n - 1] + 1 + rec(n - 1, tmp);
    return res;
  } else {
    int tmp = pos - 1;
    return rec(n - 1, tmp);
  }
}

signed main() {
  cin >> N >> X;

  f[0] = num[0] = 1;
  for (int i = 0; i < 50; i++) {
    f[i + 1] = 2 * f[i] + 1;
    num[i + 1] = 2 * num[i] + 3;
  }

  cout << rec(N, X) << endl;
  return 0;
}

反省：

今回はＤを２ＷＡしてしまいました・・・

一つは範囲外参照。

もう一つはn==0のときの再帰の処理（重要）です。

どちらも本質ではないので悔しいです。

ですが、全完できたのは成長かなと思います！

頑張ります！