[GO] Löse "AtCoder Version! Arimoto (Anfänger)" mit Python!
AtCoder-Version! Arimoto (Anfänger) wird mit Python detailliert gelöst.
1 Alle Grundlagen "Vollständige Suche"
1-1 Bit vollständige Suche
ABC 045 C-Viele Formeln
【Antworten】
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)
__ [Erklärung] __ Durchsuche alle Bits, um keine Boni zu erhalten. Nehmen Sie einen Bonus und wählen Sie die verbleibenden fehlenden Punkte aus dem mit der höchsten Punktzahl.
【Antworten】
D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))
#Sortieren Sie in absteigender Reihenfolge der Punktzahl
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 (Tiefenprioritätssuche)
ATC 001 A Suche nach Tiefenpriorität
__ [Erklärung] __
DFS (Tiefensuche) ist ein Bild, das ganz nach hinten sucht. Wenn nichts zu suchen ist, kehrt es an den Ort zurück, an dem Sie nicht gesucht haben, und sucht erneut.
Implementieren Sie mit Stack, LIFO (Last-In First-Out).
【Antworten】
from collections import deque
def dfs(maze, sh, sw):
#Initialisieren Sie die erreichte Liste
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)]
#Finde die Startposition
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 (Breitenprioritätssuche)
ABC 007 C-Breitenprioritätssuche
__ [Erklärung] __
BFS (Breitensuche) ist ein Bild der Suche von flach nach flach.
Implementieren Sie mit Queue FIFO (First-In First-Out).
【Antworten】
from collections import deque
def dfs(maze, sh, sw, gh ,gw):
#Initialisieren Sie die erreichte Liste
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 der Sonderbedingungen
__ [Erklärung] __ Verwenden Sie Permutationen, um alle Möglichkeiten zum Verbinden von Diagrammen aufzulisten. Beurteilen Sie, ob sie richtig angeschlossen sind, und zählen Sie sie.
【Antworten】
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)):
#Betrachten Sie den Ausgangspunkt von 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)
JOI 2009 Qualifying D Card Arrangement
__ [Erklärung] __ Verwenden Sie Permutationen, um die Anordnung von ganzen Zahlen aufzulisten. Erstellen Sie sortierte Ganzzahlen mithilfe von Map und Join, fügen Sie sie zu dic hinzu und beantworten Sie schließlich die Anzahl der Ganzzahlen in dic.
【Antworten】
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 Wahnsinn! "Gierige Methode"
__ Was ist Gier Methode __
- Teilen Sie das Problem in mehrere Unterprobleme auf
- Bewerten Sie die Lösung für jedes Teilproblem (es gibt mehrere mögliche Lösungsmuster für jedes Teilproblem).
- Bewerten Sie die Lösung des nächsten Teilproblems (das auch auf verschiedene Arten betrachtet werden kann), wobei die Lösung mit der besten Bewertung die Lösung dieses Teilproblems darstellt (= lokale optimale Lösung).
Zitat: Ich habe versucht, eine einfache Giermethode zu lösen
2-1 Problem der Münzen
JOI 2007 Qualifying A Change
__ [Erklärung] __ Zählen Sie die Anzahl der Münzen der größten Münze.
【Antworten】
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 Problem bei der Abschnittsplanung
Keyence Programming Contest 2020 B - Roboterarme
__ [Erklärung] __ Sortieren Sie zunächst nach der Position des rechten Endes des Roboterarms. Sehen Sie sich die Position ganz rechts in der Reihenfolge links an. Wenn sie sich überlappen, schließen Sie sie aus. Wenn sie sich nicht überlappen, aktualisieren Sie die Position ganz rechts.
【Antworten】
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 Gierig auf der Suche nach dem Kleinsten in lexikalischer Reihenfolge
__ [Erklärung] __ Was ist zunächst die Zeichenfolge von T und die Anzahl der verbleibenden Zeichen, wie unten gezeigt? Bereiten Sie die mit SS gefüllte Liste SS vor.
coder??
?coder?
??coder
Vergleichen Sie die erstellte Zeichenliste SS mit dem angegebenen S'-Zeichen nach Zeichen.
-
- Wenn der Buchstabe S'matches "?" Oder SS → Wie es ist
- Wenn der Buchstabe S'ist nicht "?" Und der Buchstabe SS ist "?" → Konvertiere SS "?" In S'character
-
- Andernfalls → Zeichenfolgen, die nicht erstellt werden können
Füllen Sie danach das in der SS verbleibende "?" Mit "a", damit es das kleinste in der Wörterbuchreihenfolge ist. 【Antworten】
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 Gierig einen strengeren Platz einnehmen
__ [Erklärung] __ Die kleinste, die größer als die vorherige Zahl ist und ein Vielfaches ist, wird verdoppelt. Verdoppeln Sie es daher und prüfen Sie, bis es Y überschreitet.
【Antworten】
X,Y = map(int,input().split())
cnt=0
while X<=Y:
cnt+=1
X = X*2
print(cnt)
ARC 006 C Stacking
__ [Erklärung] __ Schauen Sie sich das Gewicht der Box oben von vorne an, und wenn Sie sie anziehen können, setzen Sie sie auf. Wenn Sie es nicht anziehen können, wiederholen Sie den Vergleich mit der Box oben auf dem nächsten Berg.
【Antworten】
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 "Dynamische Planung" speichern und wiederverwenden
3-1 01 Rucksackproblem
AOJ-Kurs 0-1 Rucksackproblem
__ [Erklärung] __ dp [i] [j] ・ ・ ・ Dies bedeutet die optimale Lösung bis zum Gewicht j mit dem Gepäck bis zum i-ten. ・ Wenn w [i]> j Dieses Gepäck kann nicht abgelegt werden. Aktualisieren Sie daher mit der optimalen Lösung für das vorherige Gepäck.
・ Wenn w [i] ≤ j ist Überlegen Sie, wann Sie das i-te Gepäck abstellen sollen. Da das Gewicht w [i] zunimmt, wird der Wert v [i] zur optimalen Lösung des Gewichts von j-w [i] bis zum i-1 addiert. Nehmen Sie danach max, wenn das i-te Gepäck nicht eingelegt ist.
Zitat: Tsubasas Memorandum Dynamische Planungsmethode (zum Rucksackproblem) Es gibt eine Figur und sie ist sehr leicht zu verstehen.
【Antworten】
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]))
TDPC A Contest
__ [Erklärung] __ Teilsummenproblem.
Bei der Überprüfung, ob der Eingang 3 bis 5 sein kann Wenn 2 in 5-3 True ist, können Sie es auf 5 setzen! Ich werde mit dem Gefühl suchen.
Datenfluss dp zum Zeitpunkt der Eingabeliste [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] wird wahr.
【Antworten】
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