[PYTHON] AtCoder Beginner Contest 051 Review of past questions

Time required

Impressions

This time it was solved unexpectedly quickly. I have come to be able to solve typical problems such as DP and graphs, but I may not be good at problems such as experimental grasps and sequence problems.

Problem A

I realized that it would be good to replace it when I thought it was clean ...

answerA.py

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

answerA_better.py

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

B problem

You can decide x and y with 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)

C problem

All you have to do is consider the shortest route and the slightly detour route. Each Path is connected later and output.

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

I'm glad I came up with it right away. I want to make sure of these typical problems. The following is a simplified explanation of Explanation. For details, please refer to Explanation. First, assume that edge (i, j) is the cost of the edge connecting vertex i and vertex j, and dist (i, j) is the shortest distance from vertex i to vertex j. Now consider the case where an edge i → j is included in the shortest path from vertex s to vertex t. At this time, we can see that the following equation holds. $ dist (s, t) = dist (s, i) + edge (i, j) + dist (j, t) $ That is, if there is no shortest path that satisfies this equation, the edge i → It can be said that j is not included in any shortest path. Therefore, when the shortest path is obtained by the WF method or Dijkstra method, if dist (i, j) is not edge (i, j), it can be said that the edge i → j is not included in any shortest path. From the above, after finding the shortest path by the WF method, by counting the edges (i, j) $ \ neq $ dist (i, j) for each side i → j, it is as follows. It will be the 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)