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.
ABC 060 B - Choose Integers
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.
1≦A≦100 1≦B≦100 0≦C<B
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.
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.
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)
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
ABC 081 B - Shift only
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.
N=3 A=16,12,24 Réponse: 2
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.
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?
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.
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)
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