AtCoder Beginner Contest115 D問題「くりすます！！！！」

# [Christmas](https://atcoder.jp/contests/abc115/tasks/abc115_d)

# 考察

## コンテスト中の考察

- 愚直な再帰だと$O(2^N)$になって間に合わない。
- なにも良い方法が思いつかないので、とりあえず実験してみる。
- 実験すると以下のような結果が得られる。でも、法則性は見つからない。実験は諦める

```sh
P
BPPPB
BBPPPBPBPPPBB
BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
BBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBB
```

- なにもわからないので、とりあえずわかると嬉しそうな情報を調べていく。
- レベルNバーガーの長さとパティの数は等差数列っぽいので数学使えば求められる。
- 求めてみたけど、その後何も思いつかない。
- 終了





## 理想の考察

- 最初に愚直な再帰を思いつく。でも、計算量がやばいし、文字列での再帰だとメモリ的にも厳しそう。数値で再起する感じかなー？とか思う
- ここで、実験してみる。でも、法則性が見つからない。実験は捨てる

### パターンに分けて考える

- 次に、パターンを列挙してみる。複雑に見えるけど、パターン列挙してみれば単純になるかもしれないので。
- すると、レベルLバーガーは以下のように５つの構造に分けることができる。

![abc115_1.png](https://qiita-image-store.s3.amazonaws.com/0/218584/d045bb8e-dfbf-bc34-1988-4d37b9f841f9.png)


### 各パターンのパティ数について考える

- このとき、下からX層にパティが何枚あるかを考える。
- Xが①にあるとき、パティの数は0。
- Xが②にあるとき、すぐにパティの数はわからない。なので、再帰を使ってXがどの位置にあるのかを探っていく。これは再帰を使って書けそう？Xの位置を求めるには、バーガーのレベルと現在のレベルでのXがわかっている必要がある。なので、`rec(バーガーのレベル, 層の数)`みたいにすれば良いかなーって感じになる（ふんわりとしたイメージだけど）
- Xが③にあるとき、パティの数は「（レベルL-1バーガーのパティ数）+1」となる。
- Xが④にあるとき、パティの数は「（レベルL-1バーガーのパティ数）+1+（再帰で良い感じの結果を返してもらう）」みたいな感じ
- Xが⑤にあるとき、パティ数は「2*（レベルL-1バーガーのパティ数）+1」となる。

![abc115_2.png](https://qiita-image-store.s3.amazonaws.com/0/218584/220dc48a-4344-0b7b-1220-a54e53424475.png)


### ちょっと整理する

- 現時点では以下のようなコードになるはず

```cpp
int rec() {
  if (パターン①) {
    
  } else if (パターン②) {
    
  } else if (パターン③) {
    
  } else if (パターン④) {
    
  } else if (パターン⑤) {
    
  } 
}
```

- そこで、パターンnになる条件を考える。
- パターンは、Xがどの位置にあるかによって定まる。Xの位置を求めるためには、「レベルLバーガーの長さ」がわかっている必要がある。レベルLバーガーの長さが前もってわかっていると嬉しくなりそう。なので、前もって前バーガーの長さを求めておく。レベル0バーガーの長さが1で、それ以降は$2L_{i-1}+3$ずつ増えていく。なので、バーガーの長さはループで求められそう。
- `Len[i]`をレベル$i$バーガーの長さと考えると、現時点でコードは以下のようになるはず。

```cpp
int rec(int level, int layer) {
  if (layer <= 1) { // 1
    
  } else if (layer <= Len[level-1] + 1) { // 2
    
  } else if (layer <= Len[level-1] + 2) { // 3
    
  } else if (layer <= 2*Len[level-1] + 2) { // 4
    
  } else { // 5

  }
}
```

- このコードに、先ほど考えた「各パターンのパティ数」を当てはめていく
- すると、コードは以下のようになる。これでも良さげだけど、なんどもパターン④に入ると計算量が大変になりそう（なんとなく）。なので、バーガーの数だけでなく、パティの数もあらかじめ求めておく（念の為）。

```cpp
int rec(int level, int layer) {
  if (layer <= 1) { // 1
    return 0;
  } else if (layer <= Len[level-1] + 1) { // 2
    return rec(level-1, layer-1);
  } else if (layer <= Len[level-1] + 2) { // 3
    return rec(level-1, layer-1) + 1;
  } else if (layer <= 2*Len[level-1] + 2) { // 4
    return rec(level-1, layer-1) + 1 + rec(level-1, layer - Len[level-1] - 2);
  } else { // 5
    return  2*rec(level-1, layer-1) + 1;
  }
}
```

- そんな感じでコードを書けば良い感じになる。でも、このコードじゃACできない。なぜなら、`level`の終了条件を書いていないから。僕もアルメリアさんに指摘されるまでわからなかった...
- `level`の終了条件を書いて実装終了になる



## 解法

1. レベル0~Nについて、そのバーガーの数とパティの数をあらかじめ計算しておく
2. 再帰を書く



## [コード](https://atcoder.jp/contests/abc115/submissions/3834816)

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

#define int long long

int Len[55]; // Len[level]: levelバーガー全体の長さ
int Pat[55]; // Pat[level]: levelバーガーのパティ数

// levelとlayerを投げると、パティ数が返ってくる関数
int rec(int level, int layer) {
  // レベル0は例外
  if (level == 0) {
    return 1;
  }

  if (layer == 1) { // 範囲1
    return 0;
  } else if (layer <= Len[level-1] + 1) { // 範囲2
    return rec(level-1, layer-1);
  } else if (layer <= Len[level-1] + 2) { // 範囲3
    return Pat[level-1] + 1;
  } else if (layer <= 2 * Len[level-1] + 2) { // 範囲4
    return Pat[level-1] + 1 + rec(level-1, layer - Len[level-1] - 2);
  } else { // 範囲5
    return 2 * Pat[level-1] + 1;
  }
}

signed main() {
  // 入力
  int N, X;
  cin >> N >> X;

  // バーガーの長さとパティの数を前計算
  Len[0] = Pat[0] = 1;
  for (int i = 1; i <= N; i++) {
    Len[i] = Len[i-1] * 2 + 3; // レベルi-1バーガー２つ + バン２つ + パティ１つ
    Pat[i] = Pat[i-1] * 2 + 1; // レベルi-1バーガーのパティ数*２ + パティ１つ
  }

  // 出力
  cout << rec(N, X) << endl;

   return 0;
}
```



## 要点

- 複雑な問題に思えても、パターン列挙してみれば単純になる
  - これが当てはまる問題結構ある気がする
  - 今回は普通に思いつかなかった
- 再帰の終了条件を忘れずに書く！！
  - 久々の再帰だったので普通に忘れてた。
  - 再帰は終了条件と場合分けが書ければ大勝利なので、忘れずに書きたい



## 参考記事

- [アルメリアさんの記事](https://betrue12.hateblo.jp/entry/2018/12/08/225123)。図が神
- [公式解説](https://img.atcoder.jp/abc115/editorial.pdf)。簡潔に書かれてて神