ベスパリブ

ベスパもってないです。バイク買いました。

ABC 115: D問題の解説 (Python3)

問題: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()