[PYTHON] So lösen Sie die rekursive Funktion, die abc115-D gelöst hat

Problem

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

Die zweite Herausforderung. Ich war wirklich glücklich, es zu lösen. Diese Art von Problem ist überraschend wichtig, da es auch auf anderen professionellen Websites von Wettbewerbern gestellt wird.

Richtung

Es ist nicht schwer vorstellbar, dass eine rekursive Funktion aus der Problemstellung verwendet wird. Das Problem ist, dass wenn Sie einen Simulator erstellen, alle Burgerelemente riesig sind, so dass es unmöglich ist. Überlegen Sie, was Sie brauchen, und lösen Sie es effizient mit Arithmetik.

Was ist schwierig

Es gibt kein Problem bei der Interpretation des Problems. Die Frage ist, ob die Bedingungen und der Rückgabewert für die Wiederholung korrekt bestimmt werden können. Darüber hinaus erhöht die Tatsache, dass es viele bedingte Zweige gibt, auch den Schwierigkeitsgrad.

Lösung

Ich hatte das Gefühl, dass der Trick des rekursiven Problems darin bestand, die Zustandsphase mit einer kleinen Anzahl von Werten zu modellieren. Mit anderen Worten, die folgenden zwei Dinge sind wichtig

1. Da die Funktion rekursiv aufgerufen wird, erstellen Sie eine Funktion, die für alle N, N-1, N-2 ... 1, 2 gilt.

2. Beachten Sie die Kündigungsbedingungen.

3. Da die Funktion rekursiv aufgerufen wird, erstellen Sie eine Funktion, die für alle N, N-1, N-2 ... 1, 2 gilt.

Da bei diesem Problem der aktuelle Standort von Daxfund und die Dimension des Burgers benötigt werden, nehmen wir diese beiden als Argumente.

2. Beachten Sie die Kündigungsbedingungen.

Dieses Mal gibt es eine leicht verständliche Endbedingung für Burger der Stufe 0, verwenden Sie diese also.

Code

Der Code unten. Es gibt Raum für Verbesserungen, da meine Lösung drei Argumente vergeblich verwendet.

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
    ##Wenn Runrun unten ist, können Sie keine Pastetchen essen
    elif now_runrun == 1:
        return 0

    ##Wenn Runrun in der Mitte ist, n-1D Burger+Essen Sie 1
    elif now_runrun == now_burger_high // 2 + 1:
        return patty[dimension - 1] + 1

    ##Iss alle Pastetchen, wenn Runrun oben ist
    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))