Critique du concours AtCoder

Les résultats de cette fois

スクリーンショット 2020-08-23 9.33.26.png

Impressions de cette époque

Cette fois, je l'ai enduré à la dernière minute ... Le problème D n'a pas fonctionné et j'ai eu un bogue dans l'implémentation C ++ et c'était trop terrible. Après tout, la ** mentalité en cas d'impatience ** est le plus gros problème. De plus, je réfléchis au problème D parce que je faisais ** une accélération non essentielle ** sans le considérer. Je pense que je ferai de mon mieux pour améliorer l'exactitude de ma considération.

Problème A

Vous pouvez graver $ x $ à la fois, vous n'avez donc qu'à graver $ ceil (\ frac {n} {x}) $ autant de fois que vous le souhaitez. De plus, comme il faut $ t $ pour cuire, $ ceil (\ frac {n} {x}) \ times t $ est affiché.

A.py


n,x,t=map(int,input().split())
y=-((-n)//x)
print(y*t)

Problème B

Vous pouvez penser à la somme en convertissant chaque caractère en un nombre. Par conséquent, convertissez caractère par caractère avec ʻint`.

B.py


n=input()
ans=0
for i in n:
    ans+=int(i)
print("Yes" if ans%9==0 else "No")

Problème C

Vous pouvez décider si vous avez besoin d'une marche et la hauteur de la marche de l'avant. En d'autres termes, lorsque $ a \ _ {i-1}> a \ _i $, la hauteur de la plate-forme doit être considérée comme $ a \ _ {i-1} -a \ _i $ dans l'ordre.

C.py


n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n):
    if a[i]<a[i-1]:
        ans+=(a[i-1]-a[i])
        a[i]=a[i-1]
print(ans)

Problème D

Tout d'abord, c'est un problème de recherche de grille, et comme il s'agit du nombre minimum de magies de distorsion, il s'avère qu'il semble bon d'utiliser un BFS ou un DFS normal.

Cependant, s'il est mis en œuvre normalement, il faudra du temps pour rechercher la cellule $ 5 \ times 5 $ du mouvement B **, donc nous améliorerons l'efficacité. J'ai pensé que mon implémentation était mauvaise et j'ai essayé d'augmenter l'efficacité par un facteur constant, mais je peux clairement voir que le ** goulot d'étranglement ici devrait être éliminé **.

Il faut noter ici que le mouvement A n'utilise pas le nombre de magies de distorsion, donc le mouvement A est optimal s'il ne peut être tracé que par le mouvement A **. Par conséquent, considérez un BFS ou un DFS tel que ** de préférence sélectionnez et recherchez le déplacement A **. Comme il est difficile pour DFS de modifier arbitrairement l'ordre de recherche, nous envisagerons d'utiliser BFS. Dans BFS, utilisez la file d'attente pour ** insérer à la fin ** et ** rechercher par l'avant dans l'ordre **. Cependant, dans ce cas ** le déplacement n'a pas de priorité ** et il suit simplement ceux insérés dans l'ordre. Par conséquent, cette priorité peut être obtenue en utilisant ici deque dans BFS, en l'insérant à l'avant lors du déplacement A et en l'insérant à l'arrière lors du déplacement B. De plus, le BFS ** qui est inséré avant lorsqu'il est connecté sur le côté avec un coût 0 et inséré à l'arrière lorsqu'il est connecté sur le côté avec un coût 1 est appelé ** 01-BFS **.

De plus, comme les mouvements A et B sont des mouvements coûteux **, il est considéré comme une solution assez naturelle à résoudre par la ** méthode Dyxtra **. En d'autres termes, si vous considérez le mouvement A comme le côté avec un coût 0 et le mouvement B comme le côté avec un coût 1, vous pouvez vous résumer au problème de penser à vous déplacer au moindre coût. Par conséquent, lorsqu'il est combiné avec le fait que le ** coût est non négatif **, il peut être calculé comme $ O (HW \ log {HW}) $ par la méthode Dikstra ** avec la grille comme sommet. (Si vous ne connaissez pas 01-BFS, c'est une idée naturelle, mais je n'ai pas eu l'idée car je n'ai pas résolu le problème de l'itinéraire le plus court récemment ...)

(✳︎) Le BFS suivant n'a pas compris la politique après le concours, mais a été réécrit après cela. ** Dans le cas d'une recherche sur la grille, il est facile à implémenter et à comprendre ** en écrivant la grille suivante à suivre d'une instruction for.

D.py


#Poids latéral(Montant du changement)Si est 0, 01DFS est spécial
#Si c'est 0, vous pouvez BFS là
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
#Bfs sur la grille est une instruction for
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        for k,l in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:
            if 0<=k<h and 0<=l<w:
                if dp[k][l]!=-1:
                    if dp[k][l]>dp[i][j]:
                        dp[k][l]=dp[i][j]
                        now.appendleft([k,l])
        for k in range(i-2,i+3):
            for l in range(j-2,j+3):
                if 0<=k<h and 0<=l<w:
                    if dp[k][l]!=-1:
                        if dp[k][l]>dp[i][j]+1:
                            dp[k][l]=dp[i][j]+1
                            now.append([k,l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

E problème

Grâce à ce problème, j'ai pu résister aux performances de l'eau. L'incapacité de considérer le problème D était inhabituelle, mais je pense que c'était une récolte considérable à supporter ici.

Tout d'abord, si vous y réfléchissez normalement, il est préférable de sélectionner la ligne ($ MAXR ) et la colonne ( MAXC $) qui ont le plus grand nombre de cibles d'explosion **, et la réponse est $ MAXR + MAXC $. Cependant, s'il y a une cible d'explosion sur cette ** grille d'intersection **, la réponse est $ MAXR + MAXC-1 $.

À ce stade, si vous sélectionnez une ligne ou une colonne qui n'a pas le nombre maximum de cibles de souffle, le nombre de cibles de souffle incluses dans cette ligne et cette colonne sera de $ MAXR + MAXC-1 $ ou moins, donc ** la ligne avec le nombre maximum de cibles de souffle Et vous devriez choisir une colonne **.

Ici, il peut y avoir ** plusieurs lignes et colonnes avec le plus grand nombre de cibles d'explosion **, et le tableau contenant chacune est supposé être «xr», «xc». Pour le moment, il n'y a que des combinaisons len (xr) × len (xc) de ces lignes et colonnes. Recherchez au moins une combinaison ligne / colonne qui n'est pas à l'intersection des cibles de l'explosion. De plus, len (xr) × len (xc) a un maximum de $ (3 \ fois 10 ^ 6) $, il est donc ** difficile d'essayer toutes les combinaisons **.

Par conséquent, au lieu d'essayer toutes les combinaisons de lignes et de colonnes, ** à l'inverse, recherchez chaque cible d'explosion dans cette combinaison **. En d'autres termes, en convertissant «xr» et «xc» en un ensemble et en vérifiant si l'indice de chaque cible d'explosion est inclus dans cet ensemble, il est possible de savoir combien de cibles d'explosion sont dans cette combinaison. Vous pouvez (check). ** Si check est plus petit que len (xr) x len (xc) **, il existe au moins une façon de sélectionner des lignes et des colonnes afin qu'il n'y ait pas de cible d'explosion à l'intersection, donc $ MAXR Si + MAXC $ est la solution et ** check est égal à len (xr) x len (xc) **, alors $ MAXR + MAXC-1 $ est la solution.

E.py


h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)

Problème F

J'ai eu une image de la politique en me référant à l'explication, donc je vais la résoudre dans quelques jours.

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
Critique du concours AtCoder
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes