Maîtrisez la recherche linéaire! ~ Version d'implémentation Python ~

introduction

C'est le premier post de Qiita en tant que débutant depuis 2 mois depuis que j'ai commencé la programmation compétitive (AtCoder) pour étudier la programmation. Cet article a été créé par @drken Mastering Linear Search! ~ Savoir ce que vous pouvez faire avec les déclarations ~ est pour vous de comprendre le merveilleux article. Aussi, je le publierai comme référence pour des personnes comme moi en publiant un exemple d'implémentation en Python. Veuillez faire attention aux spoilers car nous publierons quelques exemples de problèmes d'AtCoder. Je vous serais très reconnaissant de bien vouloir me donner des conseils s’il y a des points disgracieux.

Trouvez-en un qui remplit les conditions

ABC 060 B - Choose Integers

Énoncé du problème

Vous choisissez des entiers positifs et trouvez la somme d'entre eux. Il n'y a pas de limite au nombre de nombres que vous pouvez choisir ou au nombre d'entiers que vous pouvez choisir. Vous pouvez choisir un entier aussi grand que vous le souhaitez, ou vous pouvez choisir 5 000 trillions d'entiers. Cependant, tous les nombres que vous choisissez doivent être des multiples de A. En outre, au moins un doit choisir un entier. Et je veux faire C de sorte que la somme soit divisée par B. Déterminez si vous pouvez choisir un entier comme celui-ci. Sortez OUI si possible, NON sinon.

Contrainte

1≦A≦100 1≦B≦100 0≦C<B

Exemple numérique

A, B, C = 7,5,1 Réponse: OUI Par exemple, si vous sélectionnez 7,14, le total sera de 21, et si vous divisez cela par 5, vous obtiendrez 1.


Commentaire

Je pense que c'est un exemple typique de jugement de la direction du drapeau. L'énoncé du problème dit "de trouver la somme de la somme divisée par B", mais puisque la somme des multiples de A est divisée, c'est-à-dire que le reste est calculé en divisant le multiple de A par B. Par conséquent, comme le montant maximal du calcul est de 100 * 100, nous rechercherons honnêtement tous.

a, b, c = map(int, input().split())
ans = 'NO'              #Maintenez la valeur initiale du drapeau de jugement comme NON
for i in range(101):    #Je veux multiplier la valeur d'entrée maximale de 100 par un multiple, donc 100+1
    if a*i % b == c:    #Mettre en œuvre le jugement d'énoncé de problème avec if
        ans = 'YES'     #Si le jugement de l'énoncé if devient vrai, changez la réponse en OUI
        print(ans)      #Sortie OUI si le jugement de l'instruction if devient Vrai
        exit()          #Puisqu'il suffit de sortir n'importe lequel, arrêtez avec le jugement True
print(ans)              #Si le jugement de l'instruction if est False, NO est émis avec la valeur initiale.

Sachez où trouver ceux qui remplissent les conditions

Définissez un index dans le code précédent pour déterminer l'emplacement. Cette fois, le but est de connaître le multiple de l'entrée A. Le résultat est # OUI 3.

a, b, c = map(int, input().split())
ans = 'NO'
idx = 0                 #La valeur initiale est 0 pour connaître le multiple
for i in range(101):
    if a*i % b == c:
        ans = 'YES'
        idx = i         #Contient un multiple qui rend le jugement de l'instruction if True
        print(ans, idx) #Si le jugement de l'instruction if devient True, YES et un multiple sont émis.
        exit()
print(ans, idx)         #Si le jugement de l'instruction if est False, NO et 0 sont émis avec les valeurs initiales.

Il est également possible de connaître la position en utilisant enumerate. Dans ce cas, nous devons donner un objet itérable, nous avons donc créé la liste à l'avance. Le résultat est également # OUI 3.

a, b, c = map(int, input().split())
multiple = [x for x in range(101)]
ans = 'NO'
for idx, i in enumerate(multiple):
    if a*i % b == c:
        ans = 'YES'
        print(ans, idx)
        exit()
print(ans, idx)

Trouvez la valeur minimale, trouvez la valeur maximale

En Python, vous pouvez créer une liste et utiliser la fonction min et la fonction max pour la trouver. Si la liste est lente, l'utilisation de set semble la rendre explosive. La raison pour laquelle il est devenu explosif simplement en passant de "dans la liste" à "dans l'ensemble" en Python

lst = [i for i in range(-5, 6)]
print(lst)       # [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
print(min(lst))  # -5
print(max(lst))  # 5

Comptez ceux qui remplissent les conditions

ABC 081 B - Shift only

Énoncé du problème

N entiers positifs A1,…, A2,…, AN sont écrits sur le tableau noir. Sunuke peut effectuer les opérations suivantes lorsque tous les nombres entiers écrits sur le tableau noir sont pairs.

--Remplacez tous les nombres entiers écrits sur le tableau noir par ceux divisés par deux.

Veuillez demander combien de fois vous pouvez effectuer l'opération au maximum.

Contrainte

Exemple numérique

N=3 A=16,12,24 Réponse: 2


Commentaire

Si toutes les valeurs de la liste sont paires, incrémentez de 1. C'est un problème qui est plus facile à comprendre s'il est implémenté avec while, mais j'ose l'implémenter avec for. La valeur maximale de A est 10 ^ 9, mais ce doit être un nombre pair, donc je pense qu'il suffira de le répéter jusqu'à 31623 fois avec √10 ^ 9 (puisqu'il n'y a pas de sens des mathématiques, la quantité de calcul est approximative).

n = int(input())
a = list(map(int, input().split()))
cnt = 0                              #Drapeau pour gérer le comptage
for _ in range(31623):               # _Préparez un argument vide pour une exécution répétée avec
    if all(i % 2 == 0 for i in a):   #Passer la liste a à i et juger si tout est égal avec tout
        cnt += 1                     #Si la condition est remplie, incrémenter cnt de 1
        a = [i//2 for i in a]        #Divisez chaque élément de la liste a par 2 et revenez à la liste a
print(cnt)                           #Sort la valeur numérique comptée par incrémentation

Ceci est un exemple d'implémentation dans l'instruction while. C'est plus simple, non?

n = int(input())
a = list(map(int, input().split()))
cnt = 0

while all(i % 2 == 0 for i in a):
    cnt += 1
    a = [i//2 for i in a]
print(cnt)

ABC 051 B - Sum of Three Integers C'est un exemple qui ne se trouve pas dans l'article de @ darken, mais je pense que c'est une bonne question, alors je l'écrirai ici. Le problème est de trouver le nombre de combinaisons. C'est un problème rempli d'essence nécessaire pour comprendre le mouvement de plusieurs boucles de for, en tenant compte de la quantité de calcul, de la définition de la gamme d'énoncés conditionnels et des avantages concurrents.

Énoncé du problème

Deux entiers K et S sont donnés. Il a trois variables X, Y, Z et prend une valeur entière qui satisfait 0 ≤ X, Y, Z ≤ K. Combien de valeurs peuvent être attribuées à X, Y, Z qui satisfont X + Y + Z = S?

Contrainte

Exemple numérique

K, S=2, 2 Réponse: 6

Il existe 6 ensembles de X, Y, Z qui satisfont la condition de l'énoncé du problème.


Commentaire

X, Y, Z sont chacun dans la plage de K. Par conséquent, créez une triple boucle de X, Y, Z avec k + 1 (maximum 2500), et si le total des combinaisons devient S, il sera incrémenté du nombre de fois 1.

k, s = map(int, input().split())
ans = 0                       #Indicateur pour compter le nombre qui répond aux critères
for x in range(k+1):          #Puisque toute la plage de k est recherchée, la plage de plage de x est k+1
    for y in range(k+1):      #Comme ci-dessus
        for z in range(k+1):  #Comme ci-dessus
            if x+y+z == s:    #Définir la condition de l'énoncé du problème
                ans += 1      #Si le jugement if est vrai, incrémenter 1
print(ans)                    #Sortez le nombre qui correspond à la condition

Dans l'exemple ci-dessus, la réponse est correcte, mais plus la valeur est élevée, plus le temps d'exécution sera long. Je dois essayer jusqu'à 2500 ^ 3 = 15625000000 façons, donc je ne peux pas arriver à temps. Par conséquent, il est nécessaire de concevoir des moyens de réduire la quantité de calcul.

Si c'est 2500 ^ 2, il y aura 6250000 voies, donc cela semble être à temps. Par conséquent, envisagez de réduire le nombre de boucles d'une unité.

Parmi les combinaisons de X, Y et Z, Z sera la valeur soustraite de S une fois que X et Y sont déterminés. Cependant, si vous l'implémentez dans cette condition docilement, le nombre de combinaisons sera de neuf.

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if x+y+z == s:
            ans += 1
print(ans)

C'est parce que, par exemple, si X = 2 et Y = 2, S = 2 ne se produira pas à moins que Z = -2. Par conséquent, Z doit être supérieur ou égal à 0 et dans la plage de K. Si vous ajoutez ceci à l'instruction conditionnelle, la réponse sera 6. J'ai pu trouver la bonne réponse tout en réduisant le nombre de boucles d'une unité.

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k and x+y+z == s:
            ans += 1
print(ans)

en conclusion

Nous tenons à remercier @drken pour avoir écrit de nombreux articles merveilleux, nos aînés et AtCoder pour avoir fourni un endroit pour profiter de la programmation. Merci d'avoir lu jusqu'au bout.

Recommended Posts

Maîtrisez la recherche linéaire! ~ Version d'implémentation Python ~
Recherche linéaire en Python
Recherche de priorité de largeur / recherche bidirectionnelle (édition Python)
Version 64 bits de PYTHON2.7
"Régression linéaire" et "Version probabiliste de la régression linéaire" en Python "Régression linéaire de Bayes"
Exemple d'implémentation d'un système de traitement LISP simple (version Python)
Recherche séquentielle avec Python
Implémentation RNN en python
Exercice Python Recherche prioritaire sur 1 largeur
[Python] Recherche (itertools) ABC167C
Dichotomie avec Python
Implémentation python de la classe de régression linéaire bayésienne
[Python] Recherche (NumPy) ABC165C
[Python] Recherche de bisection ABC155D
recherche complète de bits python
Dichotomie avec python
Dichotomie avec Python 3
Rechercher sur Twitter avec Python
Recherche binaire en Python
Implémentation SVM en python
Vérifier la version avec python
[Internal_math version (2)] Décodage de la bibliothèque AtCoder ~ Implémentation en Python ~
Aim Python Library Master (48) Autopep8
Aim Python Library Master (36) json2html
Aim Python Library Master (49) psidialogs
Aim Python Library Master (26) easyxml
Aim python library master (29) table_printer
Espaces de noms Aim Python Library Master (55)
AIM Python Library Master (46) BrowserPlus
Aim Python Library Master (30) Chronyk
AIM Python Library Master (3) Workalendar
Aim Python Library Master (37) Slimurl
Aim Python Library Master (44) pynetviz
Aim Python Library Master (8) Rolex
Aim Python Library Master (52) Marktime
Aim Python Library Master (7) Numparser
Aim Python Library Master (21) hy
Viser les requêtes du maître de bibliothèque python (18)
Aim Python Library Master (13) Easydev
Aim Python Library Master (20) Pyyaml
Aim Python Library Master (34) simultané
Viser la segmentation de mots du maître de la bibliothèque python
[Line / Python] Mémo d'implémentation Beacon
Aim Python Library Master (43) cpmoptimize
Aim Python Library Master (68) pazudorasolver
Aim Python Library Master (11) nlist
Aimez le maître de la bibliothèque python (38) beautiful_print
Aim Python Library Master (65) Geopy
Aim Python Library Master (2) Vincenty
Journal de bord Aim Python Library Master (59)
Aim Python Library Master (51) Pyautogui
Aim Python Library Master (10) Timeit
Algorithme de recherche utilisant word2vec [python]
Homebrew Python - Programme de recherche YouTube
[Python] DFS (recherche de priorité en profondeur) ATC001A
Changer la version de python à l'aide de pyenv
Aim Python Library Master (0) Liens