[PYTHON] AtCoder Beginner Contest 051 Revue des questions précédentes

Temps requis

Impressions

Cette fois, il a été résolu de manière inattendue rapidement. J'ai fini par être capable de résoudre des problèmes typiques tels que DP et graphiques, mais je ne suis peut-être pas doué pour les problèmes que je comprends en expérimentant ou avec les nombres.

Problème A

J'ai réalisé que ce serait bien de le remplacer quand je pensais qu'il était propre ...

answerA.py

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

answerA_better.py

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

Problème B

Vous pouvez décider x et y avec O ($ k ^ 2 $).

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)

Problème C

Tout ce que vous avez à faire est de considérer l'itinéraire le plus court et l'itinéraire légèrement détour. Chaque chemin est connecté plus tard et émis.

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)

Problème D

Je suis content d'avoir trouvé ça tout de suite. Je veux m'assurer de ces problèmes typiques. Ce qui suit est une explication simplifiée de Explication. Pour plus de détails, reportez-vous à Explication. Tout d'abord, supposons que l'arête (i, j) est le coût du côté reliant le sommet i et le sommet j, et dist (i, j) est la distance la plus courte entre le sommet i et le sommet j. Considérons maintenant le cas où un côté i → j est inclus dans le chemin le plus court du sommet s au sommet t. À ce stade, nous pouvons voir que l'équation suivante est vraie. $ dist (s, t) = dist (s, i) + edge (i, j) + dist (j, t) $ Autrement dit, s'il n'y a pas de chemin le plus court qui satisfait cette équation, le côté i → On peut dire que j n'est inclus dans aucune des routes les plus courtes. Par conséquent, lorsque la route la plus courte est obtenue par la méthode WF ou la méthode Dikstra, si dist (i, j) n'est pas edge (i, j), on peut dire que le côté i → j n'est inclus dans aucune route la plus courte. De ce qui précède, après avoir trouvé la route la plus courte par la méthode WF, en comptant les arêtes (i, j) $ \ neq $ dist (i, j) pour chaque côté i → j, c'est comme suit. Ce sera le code.

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)