Comment résoudre la fonction récursive qui a résolu abc115-D

problème

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

Le deuxième défi. J'étais vraiment heureux de le résoudre. Ce genre de problème est étonnamment important car il est également posé sur d'autres sites professionnels de la compétition.

Direction

Il n'est pas difficile d'imaginer qu'une fonction récursive serait utilisée à partir de l'énoncé du problème. Le problème est que si vous faites un simulateur, tous les éléments de burger seront énormes, donc c'est impossible. Pensez à ce dont vous avez besoin et résolvez-le efficacement avec l'arithmétique.

Ce qui est difficile

Il n'y a aucun problème à interpréter le problème. La question est de savoir si les conditions et la valeur de retour pour la récurrence peuvent être déterminées correctement. De plus, le fait qu'il existe de nombreuses branches conditionnelles augmente également le niveau de difficulté.

Solution

J'ai senti que l'astuce du problème récursif était de modéliser la phase d'état avec un petit nombre de valeurs. En d'autres termes, les deux choses suivantes sont importantes

1. Puisque la fonction est appelée récursivement, créez une fonction qui est valable pour tous les N, N-1, N-2 ... 1, 2.

2. Tenez compte des conditions de résiliation.

3. Puisque la fonction est appelée récursivement, créez une fonction qui est valable pour tous les N, N-1, N-2 ... 1, 2.

Puisque ce qui est nécessaire dans ce problème est l'emplacement actuel de Daxfund et la dimension du hamburger, nous prenons ces deux comme arguments.

2. Tenez compte des conditions de résiliation.

Cette fois, il existe une condition finale facile à comprendre pour le hamburger de niveau 0, alors utilisez-la.

code

Le code ci-dessous. Il y a place à amélioration car ma solution utilise trois arguments en vain.

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
    ##Si Runrun est en bas, vous ne pouvez pas manger de galettes
    elif now_runrun == 1:
        return 0

    ##Si Runrun est au milieu, n-Burger 1D+Manger 1
    elif now_runrun == now_burger_high // 2 + 1:
        return patty[dimension - 1] + 1

    ##Mangez toutes les galettes lorsque Runrun est au sommet
    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))