思考の墓場

ABC115-D:Christmas

Pythonで解いた記念。

問題

レベル $L$ バーガーを以下のように定義する。

$L=0$ のとき，パティ1枚。
$L\geq 1$ のとき，パン1枚，レベル $L-1$ バーガー，パティ1枚，レベル $L-1$ バーガー，パン1枚　を下から重ねたもの。

レベル $N$ バーガーの下から $X$ 枚目までに，パティは何枚あるか。
$1\leqq N \leqq 50$

考察

レベル $L$ バーガーが再帰的に定義されていることを使いたい。絵を描いてみるとこんな感じ。
f:id:sigma1113:20181208224144p:plain
これの $X$ 番目が例えばここだとする。
f:id:sigma1113:20181208224158p:plain
これを見れば，「レベル $L$ バーガーの $X$ 番目までのパティの数」は「レベル $L-1$ バーガーの $X-1(=X')$ 番目までのパティの数」だとわかるだろう。同様に，レベル $L-1$ バーガーはこんな感じで， $X'$ 番目がここだとする。
f:id:sigma1113:20181208225003p:plain
これを見れば「レベル $L-1$ バーガーの $X'$ 番目までのパティの数」は
「レベル $L-2$ バーガーの $(X'-2-(レベルL-2バーガーの長さ))$ 番目までにパティの数 $+$ レベル $L-2$ バーガーのパティの数 $+1$ 」
とわかる。こう考えると，再帰的に問題を解いていけばよさそうという気持ちになれる。
　では，具体的に再帰関数を書いていくことを考えよう。まず，レベル $i$ のバーガーの長さを $l_i$ ，レベル $i$ のバーガーにあるパティの数を $p_i$ とすると，これらは次の漸化式を満たす。

$l_i = 2l_{i-1}+3,l_0=1$
$p_i = 2p_{i-1}+1,p_0=1$

これはバーガーの定義からわかるだろう。事前にこれらの値は求めておく。
そして， $dfs(level,dist)$ を次のように定義する。

$level=0$ のとき， $1$
$level\neq0,dist=1$ のとき， $0$
$level\neq0,dist=l_{level}$ のとき， $p_{level}$
$level\neq0,dist=2+l_{level-1}$ のとき， $p_{level-1}+1$ (ちょうど真ん中)
$level\neq0,dist \leqq 1+l_{level-1}$ のとき， $dfs(level-1,dist-1)$
$level\neq0,dist \geqq 3+l_{level-1}$ のとき， $p_{level-1}+dfs(level-1,dist-2-l_{level-1})$

これを実装すればOK。計算量は $O(N)$ である。

提出

Submission #3744671 - AtCoder Beginner Contest 115

Pythonで書いた。
for文でも同様のことができるらしい(たしかに)。