問題：AtCoder Beginner Contest 115: D - Christmas

公式解説PDF：https://img.atcoder.jp/abc115/editorial.pdf

公式解説動画：なし

有志解説動画：【競技プログラミング】AtCoder Beginner Contest 115 D問題をJuliaで解く - YouTube

解説

考察問題であり、数学です。

方針としては、「レベルiバーガーの下からX層にあるパティPの総数」を $f(i, X)$ とし、その漸化式を導くことで問題を解きます。

とりあえず各レベルバーガーを書いてみます。わかりやすさのためパティを赤色にしています。

レベル	バーガー	層の総数	パティの総数
0	P	1	1
1	BPPPB	5	3
2	BBPPPBPBPPPBB	13	7
3	BBBPPPBPBPPPBBPBBPPPBPBPPPBBB	29	15

レベル L バーガー (L≥1) とは、バン 1 枚、レベル L−1 バーガー、パティ 1 枚、レベル L−1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。という性質が重要で、この性質から、

レベル2バーガーにはレベル1バーガーが2つ存在している
レベル3バーガーにはレベル2バーガーが2つ存在している
レベル4バーガーにはレベル3バーガーが2つ存在している
...

という性質を頭にいれておきます。

レベルNバーガーの層（パティとバン）の総数を $a_i$ とします。 $a_i$ はいくらでしょうか？

レベルNバーガーは、「レベルN-1バーガーを2つ+ 2枚のバン + 1枚のパティ」でできます。よって、

$a_i = 2 a_{i-1} + 3$

です。 $a_i$ は奇数であることもわかります。

レベルNバーガーのパティの総数を $p_i$ とします。 $p_i$ はいくらでしょうか？

レベルNバーガーは、「レベルN-1バーガーのパティの数*2 + 1枚のパティ」でできます。よって、

$p_i = 2 p_{i-1} + 1$

です。

今、解きたい問題は「ルンルンがレベルNバーガーのX層を下から食べる。食べたパティの枚数はなにか？」です。これは言い換えれば「レベルiバーガーの下からX層にあるパティPの総数」を求めることと同値です。

「レベルiバーガーの下からX層にあるパティPの総数」を $f(i, X)$ とします。

例を列挙すると、

$f(0, 0) = 0$
$f(0, 1) = 1$
$f(1, 0) = 0$
$f(1, 1) = 0$
$f(1, 2) = 1$
$f(1, 3) = 2$
$f(1, 4) = 3$
$f(1, 5) = 3$
...

です。

さて、戦略としては $f(i,X)$ の漸化式を立てることです。

レベルNバーガーはその性質上、真ん中にP（パティ）がくることがわかっています。

また、真ん中より右側には「レベルN-1バーガー + バン」ということがわかります。

また、真ん中より左側には「レベルN-1バーガー + バン」ということがわかります。

ということで、3つの場合分けをすればなんかいけそうだとあたりがつきます。

Xが真ん中より右側のとき
Xが真ん中のとき
Xが真ん中より左側のとき

の3パターンで漸化式を立てます。

$a_i$ は必ず奇数より、真ん中のPは右から $\frac{a_i + 1} {2}$ の位置にあります。

わかりやすくするため、真ん中の位置を $median_i = \frac{a_i + 1} {2}$ とします。

すると漸化式は、

i = 0のとき

${}$ $$ f(0, X) = \left\{ \begin{array}{} 1 & ( X \geqq 1 ) \\ 0 & ( X < 1 ) \end{array} \right. $$

i >= 1 のとき

${}$ $$ f(i, X) = \left\{ \begin{array}{} f(i-1, X-1) & ( X < median_i ) (Xが右側) \\ p_{i-1} + 1 & ( X = median_i ) (Xが真ん中) \\ p_{i-1} + 1 + f(i-1, X-median_i) & ( X > median_i ) (Xが左側) \end{array} \right. $$

となります。

なぜこうなるのか？というのはまあ、以下のような例をお絵かきしてみて法則性を見つけ出します。

f:id:takeg:20190921151530p:plain — Xが右側のとき

f:id:takeg:20190921151532p:plain — Xが真ん中のとき

f:id:takeg:20190921151830p:plain — Xが左側のとき

あとはこれを解くプログラムを書きます。

ちなみに、

$a_i =2^{i+2} - 3$
$p_i = 2^{i+1} - 1$

と一般項を変形できるらしいので、こちらを使うことで高速化できます。

コーナーケース

特になし

実装1（再帰関数）

# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(10000)  # 再帰関数のRecursionError対策


def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    def f(n, x):
        """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
        if n == 0:
            return 0 if x <= 0 else 1

        median = (As[n]+1)//2

        if x < median:
            return f(n-1, x-1)
        elif x == median:
            return Ps[n-1] + 1
        elif x > median:
            return Ps[n-1] + 1 + f(n-1, x-median)

    ans = f(N, X)

    print(ans)


if __name__ == "__main__":
    solve()

計算量は $O(N)$ です。

実装2（DP）

漸化式を解くといったらDPなので、DPで解こうとしたら入力例3でMemoryErrorが起きました。Xの取りうる値がでかすぎてリストの作成でコケます。以下のプログラムではACできません。

# -*- coding:utf-8 -*-
import sys


def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    # dp[i][x] := レベルiバーガーの下からx層に含まれているパティの総数
    dp = [[0]*(X+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, X+1):
        dp[0][i] = 1

    # 漸化式を解く
    for i in range(1, N+1):
        median = (As[i]+1)//2
        for x in range(X+1):
            if x < median:
                dp[i][x] = dp[i-1][x-1]
            elif x == median:
                dp[i][x] = Ps[i-1] + 1
            else:
                dp[i][x] = Ps[i-1] + 1 + dp[i-1][x-median]

    print(dp[N][X])



if __name__ == "__main__":
    solve()