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.

  1. 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))

Recommended Posts

Comment résoudre la fonction récursive qui a résolu abc115-D
Comment créer une fonction récursive
Comment créer un wrapper qui préserve la signature de la fonction à envelopper
Fonction récursive qui affiche l'arborescence XML [Note]
[Introduction à Python] Comment itérer avec la fonction range?
Comment frapper le document de Magic Function (Line Magic)
Comment utiliser le générateur
Comment appeler une fonction
Comment utiliser le décorateur
Comment augmenter l'axe
Comment démarrer la première projection
Comment calculer la quantité de calcul appris de ABC134-D
Comment exécuter automatiquement la fonction d'exportation de GCP Datastore
[Introduction à Python] Comment obtenir des données avec la fonction listdir
Comment résoudre le problème que le contenu vidéo ne peut pas être lu sur Firefox pour Linux
Comment calculer le coefficient d'autocorrélation
Comment utiliser le module optparse
Comment résoudre le problème selon lequel APL ne démarre pas après le transfert vers l'appareil réel sur Kivy-iOS
[Python] Comment dériver nCk (ABC156-D)
[Python 3.8 ~] Comment définir intelligemment des fonctions récursives avec des expressions lambda
Comment résoudre des équations linéaires simultanées
17e comment résoudre les problèmes d'écriture en temps réel hors ligne avec Python
Comment déterminer qu'une clé croisée a été entrée dans Python3
Comment lire l'ensemble de données SNLI
Comment obtenir la version Python
[Python] Explique comment utiliser la fonction format avec un exemple
Comment écraser la sortie sur la console
Comment utiliser la fonction zip de python
Comment utiliser le module ConfigParser
Comment utiliser la fonction de rendu définie dans .mako (.html) directement dans mako
Comment résoudre le problème qui se passe mal à chaque fois que vous mettez sous tension Linux
Résoudre des puzzles et 15 puzzles
Essayez de résoudre le problème de minimisation des fonctions en utilisant l'optimisation des groupes de particules
Comment résoudre le problème de l'échec de la construction lorsque CI / CD de Python Function avec AWS Amplify
Le 16ème problème d'écriture en temps réel hors ligne a été résolu avec Python
Comment diviser et traiter une trame de données à l'aide de la fonction groupby
Le 16ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Comment utiliser la bibliothèque "torchdiffeq" qui implémente le bloc ODE de Neural ODE
[Python] Comment utiliser la fonction enumerate (extraire le numéro d'index et l'élément)
[Introduction à Python] Comment écrire une chaîne de caractères avec la fonction format
Le 19ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Le 15e problème d'écriture en temps réel hors ligne a été résolu avec python
[Langage C] Comment utiliser la fonction crypt sous Linux [Hachage de mot de passe]
Comment afficher la barre de progression (tqdm)
Comment utiliser le pipeline Spark ML
Comment vérifier la version de Django
Comment explorer des pages qui défilent à l'infini
Comment régler l'heure du serveur sur l'heure japonaise
Comment mettre à jour manuellement le cache AMP
[python] Comment utiliser __command__, explication des fonctions
[Linux] Comment utiliser la commande echo
Comment obtenir une sortie colorée sur la console
Comment faire fonctionner Linux depuis la console
[Python] Comprendre comment utiliser les fonctions récursives
Comment accéder à la banque de données de l'extérieur
Comment utiliser le débogueur IPython (ipdb)
Comment résoudre le problème que seul le processus reste lorsque vous appuyez sur X sur l'écran imshow d'OpenCV
[Circuit x Python] Comment trouver la fonction de transfert d'un circuit en utilisant Lcapy
Comment trouver le coefficient de la courbe approximative passant par les sommets en Python