AtCoder Beginner Contest 115 D - Christmas

全完やったああああ！（初めてかもしれない） AGCも頑張るぞおおお（白目）

問題

多次元バーガーは以下のようなものです。

レベル0バーガーとは、パティ1枚である。
レベル $L$ バーガー $(L\geq1)$ とは、バン1枚、レベル $L-1$ バーガー、パティ1枚、レベル $L-1$ バーガー、バン1枚、をこの順にしたから積み重ねたものである。

レベル $N$ バーガーを作ったときに、下から $X$ 枚を食べると、何枚のパティを食べることができるか。

レベル $L$ バーガーの構成は以下のようになる。

f:id:donko110:20181208233500p:plain

ここで、 $X$ がどこまで伸びているかによって食べられるパティの枚数は変わってくるので、場合分けして枚数を数えてみる。

レベル $L$ で食べることのできるパティの枚数を $P_L$ とすると、以下のように場合分けできる。

f:id:donko110:20181208234549p:plain

$P_L$ = ( $P_{L-1}$ + 1) + (真ん中のパティより上側のレベル $L-1$ バーガーで食べることのできるパティの枚数)

f:id:donko110:20181208234603p:plain

$P_L$ = (レベル $L-1$ バーガーで食べることのできるパティの枚数)

後はそれぞれのレベルについて食べられるパティの枚数を、その時の $X$ に応じて数え上げると答えが求まる。

ここで、レベル $L-1$ バーガーを食べる時も、同様に数え上げることができるので、レベル $N$ バーガーを下から $X$ 枚食べた時のパティの枚数を数えることができる。

ただし、端のバンや、終了条件を注意して実装する必要がある。

（書き直してないので、汚いです。ごめんなさい。。。）

全完はうれしかった。誰か褒めてくれると喜びます。

ちなみに本番はこんな感じだったよ。

同じことを繰り返すだけなので、再帰で書いてもループで書いても大差ないと思うけど、バーガーの構成が再帰的になってて綺麗だから、再帰で書きたくなる。

↓

バグる

↓

∑(O_O；)

↓

ミスに気付く

↓

バグる

↓

Σ┌( ┐*ロ)┐

↓

...

みたいなことを8回繰り返しました...（あほすぎる）

モチベーション上がってきたので、競プロ頑張りゅ～（ゆるキャンの物販行ってきたのでバイアスがかかっています）