[GO] Résolvez "AtCoder version! Arimoto (Débutant)" avec Python!
Version AtCoder! Arimoto (Débutant) sera résolu en détail avec Python.
1 Toutes les bases "Recherche complète"
Recherche complète 1-1 bit
ABC 045 C-Many formules
【répondre】
S = list(input())
ans = 0
for i in range(2**(len(S)-1)):
plus = [""]*(len(S))
fomula = ""
for j in range(len(S)-1):
if(i>>j & 1):
plus[j] = "+"
for i in range(len(S)):
fomula += S[i] + plus[i]
ans += eval(fomula)
print(ans)
__ [Explication] __ Recherchez tous les bits pour ne pas prendre de bonus. Prenez un bonus et choisissez les points manquants restants parmi celui avec le score le plus élevé.
【répondre】
D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))
#Trier par ordre décroissant de score
l = l[::-1]
ans = float("inf")
for i in range(2**D):
total = 0
cnt = 0
for j in range(D):
if (i>>j)&1:
total += 100*(D-j)*l[j][0] + l[j][1]
cnt += l[j][0]
if total >= G:
ans = min(ans,cnt)
continue
for j in range(D):
if (i>>j)&1 == False:
for k in range(l[j][0]):
total += 100*(D-j)
cnt+=1
if total >= G:
ans = min(ans,cnt)
break
break
print(ans)
1-2 DFS (recherche de priorité de profondeur)
Recherche prioritaire ATC 001 A en profondeur
__ [Explication] __
DFS (Depth-First Search) est une image qui recherche tout le chemin vers l'arrière, et lorsqu'il n'y a rien à rechercher, retourne à l'endroit où vous n'avez pas cherché et recherche à nouveau.
Implémentez en utilisant Stack qui est LIFO (Last-In First-Out).
【répondre】
from collections import deque
def dfs(maze, sh, sw):
#Initialiser la liste atteinte
visited = [[0]*W for _ in range(H)]
stack = deque([[sh,sw]])
visited[sh][sw] = 1
while stack:
h, w = stack.pop()
if maze[h][w] == "g":
return("Yes")
for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
new_h, new_w = h+i, w+j
if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
continue
elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == 0:
visited[new_h][new_w] = 1
stack.append([new_h, new_w])
return("No")
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
#Trouvez la position de départ
for i in range(H):
if maze[i].find("s") != -1:
sh = i
sw = maze[i].find("s")
print(dfs(maze, sh, sw))
1-3 BFS (recherche de priorité de largeur)
Recherche de priorité de largeur ABC 007 C
__ [Explication] __
BFS (recherche en largeur en premier) est une image de recherche de peu profonde à superficielle.
Implémentez en utilisant Queue qui est FIFO (First-In First-Out).
【répondre】
from collections import deque
def dfs(maze, sh, sw, gh ,gw):
#Initialiser la liste atteinte
visited = [[-1]*W for _ in range(H)]
stack = deque([[sh,sw]])
visited[sh][sw] = 0
while stack:
h, w = stack.popleft()
if h == gh and w == gw :
return(visited[h][w])
for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
new_h, new_w = h+i, w+j
if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
continue
elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == -1:
visited[new_h][new_w] = visited[h][w] + 1
stack.append([new_h, new_w])
return("No")
H,W = map(int,input().split())
sh,sw = map(int, input().split())
gh,gw = map(int, input().split())
maze = [input() for _ in range(H)]
print(dfs(maze, sh-1, sw-1, gh-1, gw-1))
1-4 Liste des conditions spéciales
__ [Explication] __ Utilisez des permutations pour énumérer toutes les façons de connecter des graphiques. Jugez s'ils sont correctement connectés et comptez-les.
【répondre】
from itertools import permutations
N,M = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(M)]
graph = [[False]*(N+1) for _ in range(N+1)]
for i in l:
graph[i[0]][i[1]] = True
graph[i[1]][i[0]] = True
cnt = 0
for i in permutations(range(1,N+1)):
#Considérez le point de départ à partir de 1
if i[0] != 1:
continue
isJoin = True
for j in range(1,N):
if not graph[i[j-1]][i[j]]:
isJoin = False
break
if isJoin:
cnt += 1
print(cnt)
Arrangement de carte J de qualification JOI 2009
__ [Explication] __ Utilisez des permutations pour énumérer la disposition des entiers. Créez des entiers triés à l'aide de map et join, ajoutez-les à dic et répondez enfin au nombre d'entiers dans dic.
【répondre】
from itertools import permutations
N = int(input())
S = int(input())
l = [int(input()) for _ in range(N)]
dic = {}
for i in permutations(l,S):
i = map(str,i)
dic[("".join(i))] = 1
print(len(dic))
2 Ruée vers la folie! "Méthode gourmande"
__ Qu'est-ce que la méthode de la cupidité __
- Divisez le problème en plusieurs sous-problèmes
- Évaluer la solution pour chaque sous-problème (il existe plusieurs modèles de solution possibles pour chaque sous-problème)
- Évaluer la solution du sous-problème suivant (également possible de plusieurs manières), avec celle avec la meilleure évaluation comme solution de ce sous-problème (= solution optimale locale)
Citation: j'ai essayé de résoudre une méthode simple de cupidité
2-1 Problème des pièces
JOI 2007 Qualifying A Change
__ [Explication] __ Comptez le nombre de pièces de la plus grosse pièce.
【répondre】
N = int(input())
N = 1000 - N
cnt = 0
l = [500,100,50,10,5,1]
for i in l:
cnt += N // i
N = N - i*(N//i)
print(cnt)
2-2 Problème de planification de section
Concours de programmation Keyence 2020 B - Robot Arms
__ [Explication] __ Tout d'abord, triez par la position de l'extrémité droite du bras du robot. Regardez la position la plus à droite dans l'ordre de gauche, et si elles se chevauchent, excluez-les. S'ils ne se chevauchent pas, mettez à jour la position la plus à droite.
【répondre】
N = int(input())
l = [list(map(int,input().split())) for _ in range(N)]
ans = N
for i in l:
x = 0 if i[0]-i[1] < 0 else i[0]-i[1]
i[1] = i[0]+i[1]
i[0] = x
l.sort(key=lambda x:x[1])
right = 0
for i in range(N):
if right > l[i][0]:
ans-=1
else:
right = l[i][1]
print(ans)
2-3 Gourmand cherchant le plus petit dans l'ordre lexical
__ [Explication] __ Tout d'abord, quelle est la chaîne de caractères de T et le nombre de caractères restants comme indiqué ci-dessous? Préparez la liste SS remplie.
coder??
?coder?
??coder
Comparez la liste de caractères créée SS avec le caractère donné par caractère.
-
- Si la lettre S'correspond à "?" Ou SS → Tel quel
- Quand la lettre S n'est pas "?" Et la lettre SS est "?" → Convertir SS "?" En S'character
-
- Autrement → Chaînes de caractères qui ne peuvent pas être créées
Après cela, remplissez le "?" Restant dans le SS avec "a" pour qu'il soit le plus petit dans l'ordre du dictionnaire. 【répondre】
S = input()
T = input()
n = len(S)-len(T)+1
ans = []
for i in range(n):
SS = list("?"*(i) + T + "?"*(n-i-1))
flag = True
for i in range(len(S)):
if S[i]=="?" or S[i]==SS[i]:
pass
elif S[i]!="?" and SS[i]=="?":
SS[i] = S[i]
else:
flag = False
if flag:
ans.append("".join(SS).replace("?","a"))
if ans:
ans.sort()
print(ans[0])
else:
print("UNRESTORABLE")
2-4 Greedy prend une place plus stricte
__ [Explication] __ Le plus petit qui est plus grand que le nombre précédent et est un multiple est doublé. Par conséquent, doublez-le et vérifiez jusqu'à ce qu'il dépasse Y.
【répondre】
X,Y = map(int,input().split())
cnt=0
while X<=Y:
cnt+=1
X = X*2
print(cnt)
Empilement ARC 006 C
__ [Explication] __ Regardez le poids de la boîte en haut de l'avant, et si vous pouvez la mettre, mettez-la. Si vous ne pouvez pas le mettre, répétez la comparaison avec la boîte au sommet de la montagne suivante.
【répondre】
N = int(input())
W = [int(input()) for _ in range(N)]
l=[float("inf")]
for w in W:
flag=True
for i in range(len(l)):
if l[i]>=w:
l[i] = w
flag=False
break
if flag:
l.append(w)
print(len(l))
3 Souvenez-vous et réutilisez la «planification dynamique»
3-1 01 Problème de sac à dos
AOJ Course 0-1 Knapsack Problem
__ [Explication] __ dp [i] [j] ・ ・ ・ Cela signifie la solution optimale jusqu'au poids j en utilisant les bagages jusqu'au i-ème. ・ Lorsque w [i]> j Ce bagage ne peut pas être mis, alors mettez à jour avec la solution optimale pour le bagage précédent.
・ Lorsque w [i] ≤ j Pensez à quand mettre le i-ème bagage. Puisque le poids w [i] augmentera, la valeur v [i] sera ajoutée à la solution optimale du poids de j-w [i] jusqu'au i-1er. Après cela, prenez le maximum lorsque le i-ème bagage n'est pas déposé.
Citation: Mémorandum de Tsubasa Méthode de planification dynamique (sur le problème du sac à dos) Il y a un chiffre et c'est très facile à comprendre.
【répondre】
N,W = map(int,input().split())
v = [0] * N
w = [0] * N
for i in range(N):
v[i],w[i] = map(int,input().split())
dp = [[0] * (W+1) for _ in range(N)]
for i in range(N):
for j in range(1, W+1):
if w[i] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])
print(max(dp[N-1]))
Concours TDPC A
__ [Explication] __ Problème de somme partielle.
Lors de la vérification si l'entrée peut être de 3 à 5 Si 2 en 5-3 est True, vous pouvez le définir sur 5! Je vais chercher avec le sentiment.
Flux de données dp au moment de la liste d'entrée [2,3]. dp[1][2] = dp[0][2-2] = dp[0][0] = True dp[2][3] = dp[1][3-3] = dp[1][0] = True dp[2][5] = dp[1][5-3] = dp[1][2] = True [0,2,3,5] devient Vrai.
【répondre】
N = int(input())
l = list(map(int,input().split()))
_sum = sum(l)
dp = [[False]*(_sum+1) for _ in range(N+1)]
dp[0][0] = True
for i in range(1,N+1):
for j in range(_sum+1):
if l[i-1]>j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-l[i-1]]
print(sum(dp[N]))
Recommended Posts