[PYTHON] Critique du concours AtCoder

Les résultats de cette fois

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.