** Visez un codeur bleu clair! !! !! !! !! !! ** **
Alors [Directives pour améliorer AtCoder, un pro de la compétition enseigné par Red Coder [Édition intermédiaire: Visez Light Blue 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 a rassemblé 100 bonnes questions éducatives qui conviennent aux codeurs marron et vert afin d'obtenir un codeur bleu clair, ou une note de 1200, avec un petit nombre de questions.
100 questions passées que les débutants et les intermédiaires devraient résoudre dans cet article`
Sera résolu avec ** Python **!
Merci à @ e869120! !! !! !! !! !!
** Rechercher tout: Tout lister ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part1 / 22] ** Recherche complète: toute énumération pour réduire le nombre de rues en concevant ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part2 / 22] ** Recherche complète: recherche complète de bits ** [[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Recherche complète: avant la recherche complète ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part4 / 22] ** Recherche par section ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part5 / 22] ** Recherche de priorité de profondeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part6 / 22] ** Recherche de priorité de largeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part7 / 22]
Nous allons résoudre les 4 questions suivantes!
24 ALDS_11_B --Recherche de priorité en profondeur Il s'agit d'un problème de base. 25 AOJ 1160-Combien d'îles y a-t-il? Le nombre de composants connectés dans le graphique peut être calculé par recherche de priorité de profondeur. 26 Concours AtCoder Débutant 138 D --Ki De nombreux problèmes d'arborescence utilisent la recherche de priorité en profondeur. 27 JOI 2009 Qualification 4-Traversée de glace mince La recherche de priorité en profondeur n'est pas seulement une structure arborescente, c'est un problème qui nous le révèle. Il peut être résolu à l'aide d'une fonction récursive.
・ J'écrirai un article basé sur les trois points suivants! ** ① À propos des piles et des files d'attente ** Tout d'abord, l'article de Kencho Maîtrisez les piles et les files d'attente! ~ Dossier spécial sur les idées et les utilisations ~ En savoir plus sur ** Atmosphere About Stacks and Queues! ** **
** ② À propos de DFS et graphique ** Un autre article de Kencho DFS (Depth Priority Search) Super Introduction! ~ Entrée dans le monde des algorithmes graphiques ~ [Partie 1] DFS (Depth Priority Search) Super Introduction! ~ Entrée dans le monde des algorithmes graphiques ~ [Partie 2] En savoir plus sur DFS et les graphiques ** Comprenez l'atmosphère! ** **
** ③ Après cela, comment implémenter DFS en Python ** Comme Les sites suivants étaient faciles à comprendre, donc ces deux sites ** ◆ Pour les graphiques ou les arbres ordinaires ** Algorithme en Python (recherche de priorité en profondeur, dfs) ** ◆ Pour le quadrillage ** Implémentation de la recherche de priorité en profondeur (DFS) dans Python-ATC001 ** Soigneusement ** En savoir plus sur DFS et graphiques **! ** **
Si vous avez la prémisse de ①②③, vous pouvez l'apprendre en bougeant réellement vos mains! !! !!
Supplément 1 DFS a deux méthodes d'implémentation, ** Recursive Ver ** et ** Stack Ver **. ** Dans cet article, nous unifierons l'implémentation de Stack Ver! !! !! ** ** (Facile à appliquer à BFS? + Vitesse rapide? + Ne provoque pas de débordement de pile?)
Supplément 2
Entrez à partir de cet article (** Partie 6 **)
input()→sys.stdin.readline().rstrip()
Je change pour!
[Python] Competitive Pro Template [At Coder]
J'ai également fait un article pour le modèle, alors veuillez l'utiliser si vous le souhaitez ~
Problème de graphe typique!
graph = {i:collections.deque() for i in range(1,N+1)}
Ou
graph = {i:[] for i in range(1,N+1)}
** Ceci est le modèle de graphique! ** **
C'était la première fois que je implémentais DFS, J'ai essayé de l'implémenter selon le site ci-dessus ** J'ai réussi à l'implémenter! ** ** Le code est long, mais ** la difficulté n'est pas si grande! !! !! ** **
Le point est ces deux lignes! !! !!
seen[j] = 1
stack.append(j)
seen[g_NO] = 1
stack.append(g_NO)
~ Comment se souvenir ~
① ** J'ai vu la femme de ménage! ** (drame), donc
Remplacez vu par 0 (False) → 1 (True)!
② Si vous voyez la femme de ménage, mettez-la en stock! !! !!
** (La femme de ménage a vu la poubelle, alors je l'ai mise à la poubelle !!!) **
Si vous avez cette image en tête, vous pouvez écrire du code avec la mort cérébrale au moment de la mise en œuvre!
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)
Je n'ai pas besoin d'écrire def dfs (), mais j'ai essayé de le faire def pour qu'il soit facile à comprendre avec la description de DFS!
Aussi, le problème du graphique
Je pense que la plupart du temps, cela commence par "1" au lieu de "0"
Unifiez tout le code avec 1_indexed!
J'ai aussi essayé d'utiliser global pour la première fois, mais je vois! C'est comme ressentir!
Une autre chose dont j'étais conscient lors de l'écriture du code
** J'ai utilisé continue autant que possible pour éviter d'exécuter du code en dessous des conditions pour améliorer la lisibilité! ** **
DFS a tendance à être particulièrement imbriqué! (= A tendance à être compliqué = facile à créer des bogues!)
** La femme de ménage a vu! (Deuxième fois)**
Problème typique de grille graphique! Le problème et la façon de penser d'un graphe normal sont les mêmes! J'ai fait référence au site ci-dessus, mais ** j'ai été surpris! ** ** ** La femme de ménage a vu! (Troisième fois)**
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 ** Je n'ai pas pu le résoudre à première vue! !! !! ** ** Je suis tombé sur la quantité de calcul et suis tombé sur l'idée de racines! Cependant, à partir de maintenant, il y aura un ** "arbre" ** qui peut résoudre des problèmes similaires! !! !!
Ces deux points!
Tous les sommets sous la racine donnent l'impression d'ajouter des points de racine de référence ~ Si vous n'êtes pas devenu AC, veuillez vous référer à cet article! !! !! AtCoder Beginner Contest 138 D - Les cas de test de Ki augmentent après le concours (version modifiée)
** La femme de ménage a vu! (4e) **
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:])
Au fait, Décrit dans le Supplément 2 au début
Entrez à partir de cet article (** Partie 6 **)
input()→sys.stdin.readline().rstrip()
Je change pour!
La cause de ceci est ce problème w
J'avais du mal avec TLE, mais quand j'ai vu le code de quelqu'un qui pouvait le faire,
sys.stdin.readline()
J'utilise ...
Quand j'ai essayé de l'utiliser pour le moment, j'ai été surpris qu'il devienne un AC!
Après examen, il s'avère que ** ʻinput () `est extrêmement lent! !! !! ** **
Article de référence
8 petites différences de vitesse de traitement que Python devrait connaître
Il y a place à amélioration dans le code concernant le montant du calcul,
(Par exemple, là où vous recevez ʻab ou px`)
C'est AC, donc non ~
** Je n'ai pas pu résoudre ça à première vue non plus! !! !! ** **
Pas question ** J'ai vu la femme de ménage! Le problème qui (vu) ** ne peut pas être utilisé! !! !! Articles précédents [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22] Le problème de la somme partielle de est également un problème qui peut être résolu par DFS. ** La femme de ménage a vu! Si (vu) ** n'est pas disponible, ** la femme de ménage a vu! Le niveau de difficulté est plus élevé car il faut penser à ce qui va changer en (vu) **!
** Vous devez résoudre beaucoup de problèmes difficiles et vous y habituer! ** **
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 au moment de l'empilement, histoire passée
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)}
de
| est un ensemble de somme! (Aussi un peu opérateur OU)
Aussi,
& est le jeu de produits! (Aussi un peu opérateur ET)
^ Est un ensemble de l'un ou l'autre `! (Aussi un peu opérateur XOR)
La prochaine fois, je résoudrai les 6 questions suivantes!
28 ALDS_11_C --Width priority search C'est un problème de base. 29 AtCoder Beginner Contest 007 C - Recherche avec priorité à la largeur Le problème de l'itinéraire le plus court des graphiques non pondérés peut être résolu par une recherche avec priorité à la largeur. 30 5 fromages de qualification JOI 2011 31 JOI 2012 Qualifying 5-Illumination La mise en œuvre est un peu lourde, mais si vous faites de votre mieux, vous pouvez la résoudre. 32 AOJ 1166 - L'implémentation est un peu lourde. 33 Concours AtCoder Débutant 088 D - Repeindre la grille Si cela est résolu, vous pouvez penser que vous êtes habitué à la recherche de priorité de largeur.
Part6/22 fin!
Recommended Posts