abc115-Dを解いた再帰関数の解き方

問題

二度目の挑戦。解けて本当に嬉しかった。
この手の問題は他の競プロ系サイトでも出題しているので意外と大事。

方向性

問題文から再帰関数を用いるであろうことは想像難くない。問題はシュミレーターを作ると全てのバーガーの要素が膨大になってしまうので無理。必要な分だけ考えて算術で効率的にとく。

何が難しいか

問題の解釈は問題ない。問題は再帰をするための条件と戻り値を正しく決定できるかである。また、条件分岐が多いことも難易度をあげている。

解法

再帰問題のコツは状態位相を少ない値でモデリングすることだと感じた。つまり大事なことは以下の二つ

1. 再帰的に関数を呼び出すので、N,N-1,N-2...1,2の全てに成り立つ関数を作成すること。

2. 終了条件を考えること。

3. 再帰的に関数を呼び出すので、N,N-1,N-2...1,2の全てに成り立つ関数を作成すること。

今回の問題で必要となるのはダックスフンドの現在地と何次元のバーガーを参照しているかであるためその２つを引数にとる

1. 終了条件を考えること。

今回レベル０バーガーというわかりやすい終了条件があるのでこれを使う。

コード

以下コード。僕の解き方だと無駄に三つ引数を使っているので改善の余地あり。

N, X = map(int, input().split())
patty = [1]
buns = [0]

for i in range(0, N):
    patty.append(patty[i] * 2 + 1)
    buns.append(buns[i] * 2 + 2)

print(patty)
print(buns)

burger_high = patty[N] + buns[N]
print("burger : ", burger_high)
print("burger/2 : ", burger_high/2)


def dfs(now_runrun, now_burger_high, dimension):
    if dimension == 0:
        return 1
    ## るんるんが一番下にいれば一つもパティは食べれない
    elif now_runrun == 1:
        return 0

    ## るんるんが真ん中にいたら、n - 1次元バーガー + 1を食べる
    elif now_runrun == now_burger_high // 2 + 1:
        return patty[dimension - 1] + 1

    ## るんるんが一番上にいたら全てのパティを食べる
    elif now_runrun == now_burger_high:
        return patty[dimension]


    next_burger = now_burger_high // 2 - 1
    next_dimension = dimension - 1

    if now_runrun <= now_burger_high // 2:
        return dfs(now_runrun - 1, next_burger, next_dimension)
    else:
        return dfs(now_runrun - (patty[next_dimension] + buns[next_dimension] + 2),
                   next_burger, next_dimension) + patty[next_dimension] + 1


print(dfs(X, burger_high, N))