** Streben Sie einen hellblauen Codierer an! !! !! !! !! !! ** ** **
Damit [Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)
AtCoder hat 100 gute pädagogische Fragen gesammelt, die für braune und grüne Codierer geeignet sind, um mit einer kleinen Anzahl von Fragen einen hellblauen Codierer oder eine Bewertung von 1200 zu erreichen.
Die 100 früheren Fragen dieses Artikels, die Anfänger und Fortgeschrittene lösen sollten Wird mit ** Python ** gelöst! Vielen Dank an @ e869120! !! !! !! !! !!
** Alle durchsuchen: Alle auflisten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 1/22] ** Vollständige Suche: Alle Aufzählungen zur Reduzierung der Anzahl der Straßen durch Ausarbeitung ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part2 / 22] ** Vollständige Suche: Bit vollständige Suche ** [[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Vollständige Suche: Vollständige Suche weiterleiten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part4 / 22] ** Halbierungssuche ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part5 / 22] ** Suche nach Tiefenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part6 / 22] ** Suche nach Breitenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part7 / 22]
Wir werden die folgenden 4 Fragen lösen!
24 ALDS_11_B - Tiefe Prioritätssuche Dies ist ein Grundproblem. 25 AOJ 1160-Wie viele Inseln gibt es? Die Anzahl der verbundenen Komponenten im Diagramm kann durch Suche nach Tiefenpriorität berechnet werden. 26 AtCoder-Anfängerwettbewerb 138 D - Ki Viele Baumstrukturprobleme verwenden die Suche nach Tiefenprioritäten. 27 JOI 2009 Qualifizieren der 4-dünnen Eisüberquerung Die Suche nach Tiefenprioritäten ist nicht nur eine Baumstruktur, sondern ein Problem, das uns sagt. Es kann mit einer rekursiven Funktion gelöst werden.
・ Ich werde einen Artikel schreiben, der auf den folgenden drei Punkten basiert! ** ① Über Stapel und Warteschlangen ** Zunächst Kenchos Artikel Master-Stapel und Warteschlangen! ~ Besonderheit bei Ideen und Verwendungen ~ Lesen Sie mehr über ** Atmosphäre über Stapel und Warteschlangen! ** ** **
** ② Über DFS und Grafik ** Ein weiterer Artikel von Kencho DFS (Depth Priority Search) Super Einführung! ~ Einstieg in die Welt der Graph-Algorithmen ~ [Teil 1] DFS (Depth Priority Search) Super Einführung! ~ Einstieg in die Welt der Graph-Algorithmen ~ [Teil 2] Lesen Sie mehr über DFS und Grafiken ** Verstehen Sie die Atmosphäre! ** ** **
** ③ Danach, wie man DFS in Python implementiert ** Wie Die folgenden Sites waren leicht zu verstehen, also diese beiden Sites ** ◆ Für gewöhnliche Grafiken oder Bäume ** Algorithmus in Python (Tiefenprioritätssuche, dfs) ** ◆ Für Rasterdiagramm ** Implementieren der Tiefenprioritätssuche (DFS) in Python-ATC001 ** Vorsichtig ** Lesen Sie mehr über DFS und Grafiken **! ** ** **
Wenn Sie die Prämisse von ①②③ haben, können Sie es lernen, indem Sie tatsächlich Ihre Hände bewegen! !! !!
Ergänzung 1 DFS verfügt über zwei Implementierungsmethoden: ** Recursive Ver ** und ** Stack Ver **. ** In diesem Artikel werden wir die Implementierung von Stack Ver! !! !! ** ** ** (Einfach auf BFS anzuwenden? + Schnelle Geschwindigkeit? + Verursacht kein Stapelüberlauf?)
Ergänzung 2
Geben Sie aus diesem Artikel (** Teil 6 **)
input()→sys.stdin.readline().rstrip()
Ich wechsle zu!
[Python] Competitive Pro-Vorlage [At Coder]
Ich habe auch einen Artikel für die Vorlage erstellt. Bitte verwenden Sie ihn, wenn Sie ~ mögen
Typisches Grafikproblem!
graph = {i:collections.deque() for i in range(1,N+1)}
Oder
graph = {i:[] for i in range(1,N+1)}
** Dies ist die Grafikvorlage! ** ** **
Ich habe DFS zum ersten Mal implementiert. Als ich es gemäß der obigen Seite implementiert habe ** habe ich es geschafft, es zu implementieren! ** ** ** Der Code ist lang, aber ** die Schwierigkeit ist nicht so groß! !! !! ** ** **
Der Punkt sind diese beiden Linien! !! !!
seen[j] = 1
stack.append(j)
seen[g_NO] = 1
stack.append(g_NO)
~ Wie man sich erinnert ~ ① ** Ich habe die Haushälterin gesehen! ** (Drama), also Ändern Sie "gesehen" in "0 (falsch)" → "1 (wahr)"! ② Wenn Sie die Haushälterin sehen, legen Sie sie auf Lager! !! !! ** (Die Haushälterin hat den Müll gesehen, also habe ich ihn in den Mülleimer gelegt !!!) **
Wenn Sie dieses Bild im Sinn haben, können Sie zum Zeitpunkt der Implementierung Code mit Hirntod schreiben!
test.py
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
u,k,*v = x
for y in v:
graph[u].append(y)
seen = [0]*(n+1) #1_indexed
stack = []
time = 0
seentime = [0]*(n+1) #1_indexed
donetime = [0]*(n+1) #1_indexed
def dfs(j):
global time
seen[j] = 1
stack.append(j)
time += 1
seentime[j] = time
while stack:
s = stack[-1]
if not graph[s]:
stack.pop()
time += 1
donetime[s] = time
continue
g_NO = graph[s].popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
stack.append(g_NO)
time += 1
seentime[g_NO] = time
for j in range(1,n+1):
if seen[j]:
continue
dfs(j)
for k,a,b in zip(range(1,n+1),seentime[1:],donetime[1:]):
print(k,a,b)
Ich muss nicht "def dfs ()" schreiben, aber ich habe versucht, es "def" zu machen, damit es mit der Beschreibung von DFS leicht zu verstehen ist!
Auch das Grafikproblem
Ich denke, die meiste Zeit beginnt es mit "1" anstelle von "0".
Vereinheitlichen Sie den gesamten Code mit 1_indexed!
Ich habe auch zum ersten Mal versucht, "global" zu verwenden, aber ich verstehe! Es fühlt sich an wie!
Eine andere Sache, die mir beim Schreiben des Codes bewusst war ** Ich habe so oft wie möglich "Weiter" verwendet, um zu verhindern, dass Code unter den Bedingungen ausgeführt wird, um die Lesbarkeit zu verbessern! ** ** ** DFS ist besonders tief verschachtelt! (= Neigt dazu, kompliziert zu sein = Einfach, Fehler zu erstellen!)
** Die Haushälterin sah! (Zweites Mal)**
Typisches Rasterdiagrammproblem! Das Problem und die Denkweise eines normalen Graphen sind gleich! Ich habe auf die obige Seite verwiesen, aber ** ich war überrascht! ** ** ** ** Die Haushälterin sah! (Drittes Mal)**
test.py
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
w,h = LI()
if w==h==0:
break
ans = 0
c = [LI() for _ in range(h)]
seen = [[0]*w for _ in range(h)]
stack = []
dhdw = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
def dfs(H,W):
seen[H][W] = 1
stack.append([H,W])
while stack:
sh,sw = stack.pop()
for dh,dw in dhdw:
nh,nw = sh+dh,sw+dw
if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or c[nh][nw]==0:
continue
seen[nh][nw] = 1
stack.append([nh,nw])
for H,W in itertools.product(range(h),range(w)):
if seen[H][W] or c[H][W]==0:
continue
ans += 1
dfs(H,W)
print(ans)
26 AtCoder Beginner Contest 138 D - Ki Difficulty:923 ** Ich konnte es auf den ersten Blick nicht lösen! !! !! ** ** ** Ich stolperte über den Rechenaufwand und über die Idee der Wurzeln! Von nun an wird es jedoch einen ** "Baum" ** geben, der ähnliche Probleme lösen kann! !! !!
Diese beiden Punkte!
Alle Eckpunkte unterhalb der Wurzel fühlen sich an, als würden Sie Referenzwurzelpunkte ~ hinzufügen Wenn Sie nicht AC geworden sind, lesen Sie bitte diesen Artikel! !! !! AtCoder Beginner Contest 138 D - Die Testfälle von Ki nehmen nach dem Wettbewerb zu (modifizierte Version)
** Die Haushälterin sah! (4.) **
test.py
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_indexed
graph = {i:collections.deque() for i in range(1,N+1)} #1_indexed
for a,b in ab:
graph[a].append(b)
graph[b].append(a)
for p,x in px:
ans[p] += x
seen = [0]*(N+1) #1_indexed
stack = []
def dfs():
seen[1] = 1
stack.append(1)
while stack:
s = stack.pop()
if not graph[s]:
continue
for j in range(len(graph[s])):
g_NO = graph[s].popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
stack.append(g_NO)
ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
Apropos, Beschrieben in Anhang 2 am Anfang
Geben Sie aus diesem Artikel (** Teil 6 **)
input()→sys.stdin.readline().rstrip()
Ich wechsle zu!
Die Ursache hierfür ist dieses Problem w
Ich hatte Probleme mit TLE, aber als ich den Code von jemandem sah, der das konnte,
sys.stdin.readline()
Ich benutze ...
Als ich es vorerst versuchte, war ich überrascht, dass es eine Klimaanlage wurde!
Bei der Untersuchung stellt sich heraus, dass ** input () extrem langsam ist! !! !! ** ** **
Referenzartikel
8 kleine Unterschiede in der Verarbeitungsgeschwindigkeit, die Python kennen sollte
Der Code kann hinsichtlich des Rechenaufwands verbessert werden. (Zum Beispiel, wenn Sie "ab" oder "px" erhalten) Es ist AC, also nein ~
** Ich konnte das auch nicht auf den ersten Blick lösen! !! !! ** ** **
Auf keinen Fall ** Ich habe die Haushälterin gesehen! Das Problem, dass (gesehen) ** nicht verwendet werden kann! !! !! Frühere Artikel [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil3 / 22] Das Teilsummenproblem von ist auch ein Problem, das von der DFS gelöst werden kann. ** Die Haushälterin sah! Wenn (gesehen) ** nicht verfügbar ist **, hat die Haushälterin gesehen! Der Schwierigkeitsgrad ist höher, weil Sie über etwas nachdenken müssen, das sich in (gesehen) ** ändert!
** Sie müssen viele schwierige Probleme lösen und sich daran gewöhnen! ** ** **
test.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
m = I()
n = I()
area = [LI() for _ in range(n)]
ans = 0
dndm = [[1,0],[-1,0],[0,1],[0,-1]]
stack = [] #Position zum Zeitpunkt des Stapelns, Vergangenheit
def dfs(i,j):
global ans
stack.append([[i,j],set()])
while stack:
[sn,sm],history = stack.pop()
ans = max(ans,len(history))
for dn,dm in dndm:
nn,nm = sn+dn,sm+dm
if not(0<=nn<=n-1) or not(0<=nm<=m-1) or area[nn][nm]==0 or ((nn,nm) in history):
continue
stack.append([[nn,nm],history | {(nn,nm)}])
for i,j in itertools.product(range(n),range(m)):
if area[i][j]==1:
dfs(i,j)
print(ans)
history | {(nn,nm)}
von
| ist ein Summensatz! (Auch ein Bitoperator ODER)
Ebenfalls,
& ist das Produktset! (Auch ein Bitoperator AND)
^ Ist eine Menge von beidem`! (Auch ein Bitoperator XOR)
Nächstes Mal werde ich die folgenden 6 Fragen lösen!
28 ALDS_11_C - Breite Prioritätssuche Dies ist ein grundlegendes Problem. 29 AtCoder-Anfängerwettbewerb 007 C - Suche nach Breite mit Priorität Das Problem der kürzesten Route bei ungewichteten Diagrammen kann durch Suche nach Breite und Priorität gelöst werden. 30 JOI 2011 Qualifying 5-Cheese 31 JOI 2012 Qualifying 5-Illumination Die Implementierung ist etwas schwer, aber wenn Sie Ihr Bestes geben, können Sie sie lösen. 32 AOJ 1166 - Die Implementierung ist etwas schwer. 33 AtCoder Anfängerwettbewerb 088 D --Grid Repainting Wenn dies behoben ist, können Sie denken, dass Sie an die Suche nach Breitenprioritäten gewöhnt sind.
Part6/22 Ende!