[PYTHON] AtCoder Beginner Contest 051 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Diesmal wurde es unerwartet schnell gelöst. Ich bin in der Lage, typische Probleme wie DP und Grafiken zu lösen, aber ich bin möglicherweise nicht gut in Problemen, die ich durch Experimentieren oder Probleme mit Zahlen verstehe.

Problem A

Ich erkannte, dass es gut wäre, es zu ersetzen, wenn ich dachte, es sei sauber ...

answerA.py

print(" ".join(input().split(",")))

answerA_better.py

print(input().replace(',',' '))

B-Problem

Sie können x und y mit O ($ k ^ 2 $) entscheiden.

answerB.py

k,s=map(int,input().split())
cnt=0
for i in range(k+1):
    for j in range(k+1):
        if 0<=s-i-j<=k:
            cnt+=1
print(cnt)

C-Problem

Alles was Sie tun müssen, ist die kürzeste Route und die leicht umlaufende Route zu berücksichtigen. Jeder Pfad wird später verbunden und ausgegeben.

answerC.py

sx,sy,tx,ty=map(int,input().split())
path1=(tx-sx)*"R"+(ty-sy)*"U"
path2=(tx-sx)*"L"+(ty-sy)*"D"
path3="D"+(tx-sx+1)*"R"+(ty-sy+1)*"U"+"L"
path4="U"+(tx-sx+1)*"L"+(ty-sy+1)*"D"+"R"
print(path1+path2+path3+path4)

D Problem

Ich bin froh, dass ich es mir sofort ausgedacht habe. Ich möchte auf diese typischen Probleme achten. Das Folgende ist eine vereinfachte Erklärung von Erklärung. Weitere Informationen finden Sie unter Erläuterung. Angenommen, Kante (i, j) sind die Kosten der Seite, die den Scheitelpunkt i und den Scheitelpunkt j verbindet, und dist (i, j) ist der kürzeste Abstand vom Scheitelpunkt i zum Scheitelpunkt j. Betrachten Sie nun den Fall, in dem eine Seite i → j auf dem kürzesten Weg vom Scheitelpunkt s zum Scheitelpunkt t enthalten ist. Zu diesem Zeitpunkt können wir sehen, dass die folgende Gleichung gilt. $ dist (s, t) = dist (s, i) + Kante (i, j) + dist (j, t) $ Das heißt, wenn es keinen kürzesten Weg gibt, der diese Gleichung erfüllt, ist die Seite i → Es kann gesagt werden, dass j in keiner der kürzesten Routen enthalten ist. Wenn daher die kürzeste Route durch die WF-Methode oder die Dikstra-Methode erhalten wird und dist (i, j) nicht die Kante (i, j) ist, kann gesagt werden, dass die Seite i → j in keiner kürzesten Route enthalten ist. Nach dem Finden des kürzesten Weges durch das WF-Verfahren ist nach dem Obigen durch Zählen der Kanten (i, j) $ \ neq $ dist (i, j) für jede Seite i → j wie folgt. Es wird der Code sein.

answerD.py

n,m=map(int,input().split())
inf=100000000
wf=[[inf]*n for i in range(n)]
wf_sub=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0
    wf_sub[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf_sub[a-1][b-1]=c
    wf[b-1][a-1]=c
    wf_sub[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j])
cnt=0
for i in range(n):
    for j in range(n):
        if wf_sub[i][j]!=0 and wf_sub[i][j]!=inf:
            if wf[i][j]!=wf_sub[i][j]:
                cnt+=1

print(cnt//2)