AtCoder Beginner Contest 115: D - Christmas

競技プログラミング AtCoder

問題

問題文

https://beta.atcoder.jp/contests/abc115/tasks/abc115_d

問題概要

多次元バーガーを作る事を考える. 多次元バーガにはレベルがあり, レベル L バーガー (Lは 0 以上の整数) は以下のように定義される.

  • L = 0 : パティ 1 枚のみで構成される.

  • L > 0 : バンズ 1 枚 + (L-1)バーガー + パティ 1 枚 + (L-1)バーガー + バンズ 1 枚

レベル N (1 <= N <= 50) バーガーの下から X (1 <= X <= レベルNバーガの層の総数) 層までに含まれるパティの枚数を出力せよ.

解答例

指針

解説

以下, パティを P バンズ を B とする.

最初に思いつく方針として, レベル 50 までのバーガーの状態を文字列として持ち, 末尾から数えて X 文字までに含まれる P の数をカウントするというものがあるがこの方針だと TLE となる.

入力例 3 で以下のように X が非常に大きくなることがわかる. このことからこの方針だととても間に合わないし, メモリ制約的にもきついと判断できる.

50 4321098765432109

ところで, レベル L バーガーはその定義より再帰的に決定される. 漸化式っぽく書くと以下のようになる.

{\displaystyle Lv.Lバーガー = \begin{eqnarray} \left\{ \begin{array}{c} P \quad (L = 0) \\ B + Lv.(L-1)バーガー + P + Lv.(L-1)バーガー + B \quad (L > 0) \\ \end{array} \right. \end{eqnarray} }

ここで, レベル i バーガーの層の総数を BurgerLen[i-1] とし, レベル N バーガーの下から X 枚の層に含まれるパティの枚数を {\displaystyle f(N, X) } とすると, X に関して場合分けすることで以下のようにかける.

{\displaystyle f(N, X) = \begin{eqnarray} \left\{ \begin{array}{c} 1 \quad (X = 1 \quad and \quad N = 0) \\ 0 \quad (X = 1 \quad and \quad N \neq 0) \\ f(N-1, X-1) \quad (1 \lt X \leq BurgerLen[N-1] + 1) \\ f(N-1, BurgerLen[N-1]) + 1 \quad (X = BurgerLen[N-1] + 2) \\ f(N-1, BurgerLen[N-1]) + 1 + f(N-1, X-BurgerLen[N-1]-2) \\ (BurgerLen[N-1] + 2) \lt X \lt BurgerLen[N] ) \\ f(N-1, BurgerLen[N-1]) \times 2 + 1 \quad (X = BurgerLen[N] ) \end{array} \right. \end{eqnarray} }

これをそのまま実装すれば, メモ化をしなくても制限時間以内に答えを出力することができた.

  • Python3 による実装例
#!/usr/bin/env python3

N, X = map(int, input().split())
burger_len = [1]

for i in range(N):
    burger_len += [ burger_len[i] * 2 + 3 ]

def rec(N, X):
    if X == 1:
        return 1 if N == 0 else 0
    elif 1 < X <= burger_len[N-1] + 1:
        return rec(N-1, X-1)
    elif X == burger_len[N-1] + 2:
        return rec(N-1, burger_len[N-1]) + 1
    elif burger_len[N-1] + 2 < X < burger_len[N]:
        return rec(N-1, burger_len[N-1]) + \
        1 + rec(N-1, X - burger_len[N-1] - 2)
    elif X == burger_len[N]:
        return rec(N-1, burger_len[N-1]) * 2 + 1

print (rec(N, X))
  • C++ による実装例

int だとオーバーフローするので注意.

#include <iostream>

using namespace std;

typedef long long ll;

ll burger_len[51] = {1};

ll rec(ll N, ll X) {
    if (X == 1) {
        return N ? 0 : 1;
    } else if (1 < X && X <= burger_len[N-1] + 1) {
        return rec(N-1, X-1);
    } else if (X == burger_len[N-1] + 2) {
        return rec(N-1, burger_len[N-1]) + 1;
    } else if (burger_len[N-1] + 2 < X && X < burger_len[N]) {
        return rec(N-1, burger_len[N-1]) + 1 + rec(N-1, X - burger_len[N-1] - 2);
    } else if (X == burger_len[N]) {
        return rec(N-1, burger_len[N-1]) * 2 + 1;
    }
}

int main() {
    ll N, X;
    for (int i = 1; i <= 50; i++) {
        burger_len[i] = burger_len[i-1] * 2 + 3;
    }

    cin >> N >> X;
    cout << rec(N, X) << endl;

    return 0;
}

参考文献