[PYTHON] AtCoder Anfängerwettbewerb 176 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Diesmal habe ich es in letzter Minute ertragen ... Das D-Problem hat nicht funktioniert und ich habe einen Fehler in der C ++ - Implementierung bekommen und es war zu schrecklich. Immerhin ist ** Mentalität bei Ungeduld ** das größte Problem. Außerdem denke ich über das D-Problem nach, weil ich ** nicht wesentliche Beschleunigung ** durchgeführt habe, ohne es zu berücksichtigen. Ich denke, ich werde mein Bestes geben, um die Genauigkeit meiner Überlegungen zu verbessern.

Problem A

Sie können $ x $ gleichzeitig brennen, sodass Sie $ lid (\ frac {n} {x}) $ nur so oft brennen müssen, wie Sie möchten. Da zum Backen $ t $ benötigt wird, wird $ lid (\ frac {n} {x}) \ times t $ ausgegeben.

A.py

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

B-Problem

Sie können sich die Summe vorstellen, indem Sie jedes Zeichen in eine Zahl umwandeln. Konvertieren Sie daher jedes Zeichen mit "int".

B.py

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

C-Problem

Sie können entscheiden, ob Sie eine Stufe benötigen, und die Höhe der Stufe von vorne. Mit anderen Worten, wenn $ a \ _ {i-1}> a \ _i $, sollte die Höhe der Plattform in der angegebenen Reihenfolge als $ a \ _ {i-1} -a \ _i $ angesehen werden.

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)

D Problem

Erstens handelt es sich um ein Rastersuchproblem, und da es sich um die minimale Anzahl von Warp-Magien handelt, stellt sich heraus, dass es gut erscheint, normales BFS oder DFS zu verwenden.

Wenn es jedoch normal implementiert wird, wird es einige Zeit dauern, nach der $ 5 \ times 5 $ -Zelle der Bewegung B ** zu suchen, damit wir die Effizienz verbessern. Ich dachte, dass meine Implementierung schlecht war und versuchte, die Effizienz um einen konstanten Faktor zu steigern, aber ich kann deutlich sehen, dass der ** Engpass hier beseitigt werden sollte **.

Hierbei ist zu beachten, dass Bewegung A nicht die Anzahl der Warp-Magien verwendet, sodass Bewegung A optimal ist, wenn sie nur durch Bewegung A ** verfolgt werden kann. Betrachten Sie daher ein BFS oder DFS wie **, wählen Sie vorzugsweise Zug A ** aus und suchen Sie danach. Da es für DFS schwierig ist, die Suchreihenfolge willkürlich zu ändern, werden wir die Verwendung von BFS in Betracht ziehen. Verwenden Sie in BFS die Warteschlange, um ** nach ** einzufügen und ** von vorne zu suchen **. In diesem Fall ** hat der Zug jedoch keine Priorität ** und folgt nur den eingefügten in der angegebenen Reihenfolge. Daher kann diese Priorität erreicht werden, indem hier in BFS deque verwendet wird, bei Bewegung A vorne und bei Bewegung B hinten eingefügt wird. Außerdem wird BFS **, das zuvor eingefügt wurde, wenn es seitlich mit Kosten 0 verbunden war, und hinten eingefügt, wenn es seitlich mit Kosten 1 verbunden wurde, als ** 01-BFS ** bezeichnet.

Da beide Bewegungen A und B kostenintensive Bewegungen ** sind, wird dies als eine ziemlich natürliche Lösung angesehen, die mit der ** Dyxtra-Methode ** gelöst werden kann. Mit anderen Worten, wenn Sie sich Bewegung A als die Seite mit den Kosten 0 und Bewegung B als die Seite mit den Kosten 1 vorstellen, können Sie auf das Problem zurückkommen, über das Bewegen zu den niedrigsten Kosten nachzudenken. In Kombination mit der Tatsache, dass die ** Kosten nicht negativ sind **, können sie daher nach der Dikstra-Methode ** mit dem Gitter als Scheitelpunkt als $ O (HW \ log {HW}) $ berechnet werden. (Wenn Sie 01-BFS nicht kennen, ist dies eine natürliche Idee, aber ich bin nicht auf die Idee gekommen, weil ich das Problem der kürzesten Route in letzter Zeit nicht gelöst habe ...)

(✳︎) Das folgende BFS hat die Richtlinie nach dem Wettbewerb nicht verstanden, wurde jedoch danach neu geschrieben. ** Bei der Suche im Raster ist es einfach zu implementieren und zu verstehen, ** indem Sie das nächste Raster schreiben, auf das eine for-Anweisung folgt.

D.py

#Seitengewicht(Änderungsbetrag)Wenn 0 ist, ist 01DFS eine spezielle
#Wenn es 0 ist, können Sie dort BFS
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 im Raster ist eine for-Anweisung
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 Problem

Dank dieses Problems konnte ich der Wasserleistung standhalten. Die Unfähigkeit, das D-Problem zu berücksichtigen, war ungewöhnlich, aber ich denke, es war eine beträchtliche Ernte, um hier zu ertragen.

Wenn Sie normal darüber nachdenken, ist es zunächst am besten, die Zeile ($ MAXR ) und die Spalte ( MAXC $) auszuwählen, die die meisten Explosionsziele haben **, und die Antwort lautet $ MAXR + MAXC $. Wenn sich jedoch ein Explosionsziel auf diesem ** sich überschneidenden Gitter ** befindet, lautet die Antwort $ MAXR + MAXC-1 $.

Wenn Sie zu diesem Zeitpunkt eine Zeile oder Spalte auswählen, die nicht die maximale Anzahl von Explosionszielen aufweist, beträgt die Anzahl der in dieser Zeile und Spalte enthaltenen Explosionsziele $ MAXR + MAXC-1 $ oder weniger, also ** die Zeile mit der maximalen Anzahl von Explosionszielen Und Sie sollten eine Spalte ** wählen.

Hier kann es ** mehrere Zeilen und Spalten mit der größten Anzahl von Explosionszielen ** geben, und das Array, das jedes enthält, wird als "xr", "xc" angenommen. Zu diesem Zeitpunkt gibt es nur "len (xr) × len (xc)" - Kombinationen dieser Zeilen und Spalten. Suchen Sie nach mindestens einer Zeilen- / Spaltenkombination, die sich nicht am Schnittpunkt der Explosionsziele befindet. Außerdem hat "len (xr) × len (xc)" ein Maximum von $ (3 \ times 10 ^ 6) $, so dass es ** schwierig ist, alle Kombinationen ** auszuprobieren.

Anstatt jede Zeilen- und Spaltenkombination auszuprobieren, ** suchen Sie umgekehrt nach jedem Explosionsziel in dieser Kombination **. Mit anderen Worten, indem Sie "xr" und "xc" in einen Satz konvertieren und prüfen, ob der Index jedes Explosionsziels in diesem Satz enthalten ist, können Sie herausfinden, wie viele Explosionsziele in dieser Kombination enthalten sind. Sie können (check). ** Wenn check kleiner als len (xr) x len (xc) ** ist, gibt es mindestens eine Möglichkeit, Zeilen und Spalten so auszuwählen, dass sich an der Kreuzung kein Explosionsziel befindet, also $ MAXR Wenn + MAXC $ die Lösung ist und ** check gleich len (xr) × len (xc) ** ist, dann ist $ MAXR + MAXC-1 $ die Lösung.

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)

F Problem

Ich habe mir anhand der Erklärung ein Bild von der Richtlinie gemacht, daher werde ich sie innerhalb weniger Tage lösen.