À propos de la recherche peu complète qui apparaît souvent chez les professionnels de la concurrence Aux yeux des débutants avec python

en premier

J'étais un professionnel de la compétition et j'ai commencé à étudier les algorithmes. Je voudrais expliquer la recherche peu complète, qui est le début de l'algorithme, avec la signification de la sortie. Je suis encore un jeune étudiant, veuillez donc signaler toute erreur. J'écrirai dans l'histoire principale du professionnel du concours.

Qu'est-ce qu'une recherche peu complète?

C'est l'une des méthodes de recherche complète. Cette technique peut être utilisée lorsqu'il y a plusieurs variables et que chaque variable prend deux valeurs. bit signifie 0 et 1 dans l'ordinateur et prend deux valeurs. C'est assimilé à. Je pense que c'est difficile à comprendre à partir de l'explication des personnages, je vais donc en donner un exemple.

exemple

0,1 Seuls les deux nombres de peuvent être inclus dans la liste. La longueur de la liste est de 3. Énumérez toutes les listes possibles.

répondre

bit.py


for i in range(2**3): #1
    list=[0]*3 #2
    for k in range(3): #3
        if ((i>>k)&1): #4
            list[k]=1 #5
    print(list)

Commentaire

1 Chaque élément de la liste a 2 types, 1 ou 0, donc le nombre d'éléments est 2 ** (le nombre d'éléments) 2 Créez une liste temporaire. Il sera réécrit plus tard en fonction du résultat de l'opération de bit. Au fait, [0] * 3 = [0,0,0]. 3 La longueur de la liste est de 3, vous pouvez donc la décaler jusqu'à 2 fois. 4 C'est la partie centrale de la recherche complète de bits. i >> k signifie décaler i vers la gauche k fois. Puisque & indique et, cette ligne signifie "i >> k signifie si i est décalé à gauche k fois et 1 est vrai".

Exemple en compétition pro

https://atcoder.jp/contests/abc045/tasks/arc061_a

Chose importante

N'apportez pas le n ° 2 sur la boucle for

4 est l'opérateur bit

& Est le produit logique des opérations sur les bits, | est la somme logique, ^ est la somme logique exclusive

Recommended Posts

À propos de la recherche peu complète qui apparaît souvent chez les professionnels de la concurrence Aux yeux des débutants avec python
Essayez de mettre en œuvre une recherche complète de la séquence qui apparaît souvent chez les pros de la concurrence avec python
Recherche de bits complète avec Python
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (010 --014 Recherche complète: Recherche complète de bits)
Résolvez les problèmes de somme partielle avec une recherche complète en Python
Résoudre avec Python [100 anciennes questions sélectionnées que les débutants et les intermédiaires devraient résoudre] (015 --017 Recherche complète: Recherche complète en avant)
Apprenez Nim avec Python (dès le début de l'année).
Trouvez la partie 575 de Wikipedia en Python
Un mémorandum sur la mise en œuvre des recommandations en Python
recherche complète de bits python
Liste de mes articles pouvant être utiles aux pros de la compétition (mise à jour de temps en temps)
Essayez de gratter les données COVID-19 Tokyo avec Python
Calculez des millions de chiffres dans la racine carrée de 2 avec python
[Pour les débutants] Résumé de l'entrée standard en Python (avec explication)
[Homologie] Comptez le nombre de trous dans les données avec Python
Google recherche la chaîne sur la dernière ligne du fichier en Python
Créez une application qui recherche uniquement à l'aide de l'API de recherche personnalisée Google avec Python 3.3.1 dans Bottle
À propos des fonctionnalités de Python
L'histoire de la création d'un Bot qui affiche les membres actifs dans un canal spécifique de Slack avec Python
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (005 --- 009 Toutes les recherches: Toutes les énumérations pour réduire le nombre de rues en concevant)
Exportez le contenu de ~ .xlsx dans le dossier en HTML avec Python
Une fonction qui mesure le temps de traitement d'une méthode en python
Lisez le fichier en Python avec un chemin relatif depuis le programme
[Parlez de la structure de dessin de plotly] Visualisation dynamique avec plotly [python]
Visualisez la fréquence des occurrences de mots dans les phrases avec Word Cloud. [Python]
De l'introduction de JUMAN ++ à l'analyse morphologique du japonais avec Python
L'histoire de la création d'un module qui ignore le courrier avec python
Note de solution de contournement lorsque l'erreur de segmentation: 11 apparaît dans l'importation d'opencv qui a été installée avec virtualenv de python
[Version terminée] Essayez de connaître le nombre d'habitants de la ville à partir de la liste d'adresses avec Python
Analysez le code source de votre propre moteur de recherche simple écrit en Python avec l'outil de visualisation de code "SOURCE TRAIL"
Une histoire sur la création d'un programme qui augmentera le nombre d'abonnés Instagram de 0 à 700 en une semaine
Existence du point de vue de Python
À propos de la liste de base des bases de Python
Apprenez les bases de Python ① Débutants élémentaires
Résultats qui n'ont pas été pris en compte dans la recherche avec ce mot
Remplissez la chaîne avec des zéros en python et comptez certains caractères de la chaîne
[Python] Explorez les caractéristiques des titres des meilleurs sites dans les résultats de recherche Google
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (028 --033 recherche de priorité de largeur)
Résumé de base du scraping avec des requêtes que les débutants peuvent absolument comprendre [Python]
Extraire les lignes qui correspondent aux conditions d'un fichier texte avec python
Recevez une liste des résultats du traitement parallèle en Python avec starmap
Caractéristiques des modules d'expressions régulières qui sont souvent utilisés personnellement en Python
Découvrez le nom de la méthode qui l'a appelée à partir de la méthode qui est python
D'un livre qui apprend de manière intéressante la façon de penser du programmeur (Python)