AtCoder Beginner Contest 051 Revue des questions précédentes

Temps requis

スクリーンショット 2020-01-15 22.23.51.png

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)

Recommended Posts

AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 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 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 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
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes