Cet article est le livre de Kenchon, qui contient de nombreuses explications sur la programmation compétitive, ** Entraînez vos compétences en résolution de problèmes! Algorithmes et structures de données（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。
Sur cette page, nous présenterons le contenu du chapitre 3! Veuillez me pardonner s'il y a des bugs.
Consultez les pages suivantes pour obtenir des liens vers d'autres chapitres. [Table des matières] https://qiita.com/KevinST/items/002676619a583754bf76
C'est celui qui "vérifions dans l'ordre par l'avant"!
code3-1.py
#Recevoir des entrées
N, v = map(int, input().split())
a = list(map(int, input().split()))
#Recherche linéaire
exist = False
for i in range(N):
if a[i] == v:
exist = True
#Sortie de résultat
if exist:
print("Yes")
else:
print("No")
[Exemple d'entrée] 5 1 2 3 4 1 11 [Exemple de sortie] Yes
Il est maintenant temps d'obtenir l'index.
code3-2.py
#Recevoir des entrées
N, v = map(int, input().split())
a = list(map(int, input().split()))
##Recherche linéaire##
found_id = -1
for i in range(N):
if a[i] == v:
found_id = i
break
print(found_id)
[Exemple d'entrée] 4 2 0 2 -1 11 [Exemple de sortie] 1
Pour le nombre "2" a[0]: 0 a[1]: 2 ... Je vais le chercher. Cette fois, un [1] = 2, et le nombre que vous cherchiez ici correspond à un [i]. Cassez ici et sortez.
code3-3.py
#Recevoir des entrées
N = int(input())
a = list(map(int, input().split()))
##Recherche linéaire##
#Définissez la valeur initiale de la valeur minimale sur "infini"
min_value = float("inf")
for i in range(N):
if a[i] < min_value:
min_value = a[i]
print(min_value)
[Exemple d'entrée] 4 0 2 -1 11 [Exemple de sortie] -1
J'ai pu trouver la plus petite valeur "-1". Le montant du calcul est de O $ (N) $.
Sélectionnez un élément du tableau a et un élément du tableau b et ajoutez-les pour créer un nombre. Parmi eux, choisissez celui avec K ou plus et le plus petit.
code3-4.py
#Recevoir des entrées
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
#Recherche linéaire
min_value = float("inf")
for i in range(N):
for j in range(N):
#Si la somme est inférieure à K, jetez-la
if a[i] + b[j] < K:
continue
#Mise à jour minimum
if a[i] + b[j] < min_value:
min_value = a[i] + b[j]
print(min_value)
[Exemple d'entrée] 4 10 1 2 5 6 7 12 16 22 [Exemple de sortie] 12
Il s'agit d'une préparation à la soi-disant recherche par bits. J'ai également ajouté une entrée et une sortie pour vérifier le fonctionnement.
code3-5.py
#Recevoir des entrées
i = int(input())
bit = int(input(), 2)
#Vérifiez si le sous-ensemble représenté par bit contient le i-ème élément
if bit & (1 << i):
print("Yes")
else:
print("No")
[Exemple d'entrée] 1 1010 [Exemple de sortie] Yes
La recherche complète de bits est l'une des méthodes de recherche complète et elle peut énumérer tous les modèles ON / OFF. Pour plus de détails, voir le livre et les commentaires en ligne de Kencho-san.
Pour ceux qui disent "Bi, bit ... Non, c'est difficile> <", vous pouvez utiliser la fonction Python pour tout rechercher sans penser à bit. (Voir "Supplément 3.6")
C'est une recherche un peu complète.
code3-6.py
#Recevoir une entrée
N, W = map(int, input().split())
a = list(map(int, input().split()))
#le bit est 2^Se déplace dans n sous-ensembles différents
exist = False
for bit in range(2**N):
#La somme des éléments contenus dans le sous-ensemble
sum_val = 0
for i in range(N):
#i-ème élément a[i]Est inclus dans le sous-ensemble
if bit & (1 << i):
sum_val += a[i]
#sum_Si val correspond à W
if sum_val == W:
exist = True
if exist:
print("Yes")
else:
pritn("No")
[Exemple d'entrée] 4 10 1 9 100 200 [Exemple de sortie] Yes
Considérons le sous-ensemble (1,9). Sa somme est de 10, donc cela correspond à W. Donc, la réponse est oui".
peu c'est dur! Pour ceux qui disent, nous avons préparé un autre ver. Comme procédure
Python est bon! (Publicité)
code3-6-another_ver.py
from itertools import combinations
N, W = map(int, input().split())
a = list(map(int, input().split()))
exist = False
#Déterminez le nombre d'éléments à récupérer (num_of_a): 0 à N
for num_of_a in range(N+1):
#De a, tout num_of_Extraire des éléments avec une méthode d'extraction et stocker chacun dans le modèle variable
for pattern in combinations(a, num_of_a):
#Calculer le total
sum_val = sum(list(pattern))
#sum_Si val correspond à W
if sum_val == W:
exist = True
if exist:
print("Yes")
else:
pritn("No")
[Exemple d'entrée] 4 10 1 9 100 200 [Exemple de sortie] Yes
Si vous souhaitez en savoir plus sur itertools, la page suivante peut être utile. Si vous le lisez, vous serez impressionné par la commodité de la bibliothèque standard Python! Wow, itertools
Cliquez ici pour le chapitre 4 https://qiita.com/KevinST/items/f846d57e56242c6e1293
Recommended Posts