[PYTHON] AtCoder Beginner Contest 087 Review of past questions

Time required

Impressions

I solved 087 in succession with ABC085. I spent an hour unsolving the D problem, but probably didn't notice a common mistake. I would like to mention it in the D problem chapter.

Problem A

Just buy one cake and the rest with donuts,

answerA1.py

x,a,b=int(input()),int(input()),int(input())
print(x-a-((x-a)//b)*b)

answerA2.py

s=list(input())
s[3]="8"
print("".join(s))

B problem

Since x is a multiple of 50, you can divide it by 50 and think about the equation 10i + 2j + k = x (0 <= i, j, k <= n, i + j + k = n). You can think of different pairs of i, j, and k, so count them up and answer.

answerB.py

a,b,c,x=int(input()),int(input()),int(input()),int(input())
x//=50
ans=0
for i in range(x//10+1):
    k=x-i*10
    for j in range(k//2+1):
        l=k-j*2
        ans+=(0<=i<=a and 0<=j<=b and 0<=l<=c)
print(ans)

C problem

There are only 2 squares in the vertical direction, so you only have to think about where to go down, O (n).

answerC.py

n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
ans=0
for i in range(n):
    ans=max(ans,sum(a[0][:(i+1)])+sum(a[1][i:]))
print(ans)

D problem

The ** positional relationship ** of each person is important. Therefore, if you use ** graph ** to show the positional relationship, you can proceed with the consideration well. First, in this problem, ** the positional relationship of people is relative **, so ** the position of the starting point is set as 0 **. Then, you should decide in order from the person who has a positional relationship with that person. For that purpose, first prepare an array that stores the positional relationship of each person with which person and the distance, and when the information (Li, Ri, Di) is received by input, the array corresponding to Li and Ri Put that information in each element. Then, starting from ** one or more elements and connected elements **, the other elements are traced in order to determine the position of each person, but at this time the information stored in the array may be inconsistent. In that case, No is output. Also, at this time, be careful when the graph is ** unconnected **. First, decide the first element to follow, but ** If it is an element that is not connected to any element, skip it because there is no possibility of inconsistent information ** (For the check array prepared in the next sentence Check it.). In addition, prepare an array to determine whether each element has been checked, and perform the above operations using BFS in order from the unchecked array in that array, which inconsistent with all information. You can check if you want to. When I solved it, I couldn't judge this unconnected element well. Keep in mind that the graph problem may be ** unconnected **, and I would like to solve it from now on.

✳︎ There are two codes below, the first code is the code that outputs No at the moment of inconsistency and exits to terminate the program, and the second code is the information after checking all the elements. Is the code that checks for contradictions (of course, the former is faster).

answerD.py

import sys
sys.setrecursionlimit(400000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
check=[True]*n

lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
def bfs(z):
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                print("No")
                sys.exit()
st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)
print("Yes")

answerD2.py

import sys
sys.setrecursionlimit(100000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
check=[True]*n
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
st=-1
for i in range(n):
    if len(lrd[i])>=1:
        st=i
        break

def bfs(z):
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])

st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)

for i in range(n):
    l=len(lrd[i])
    for j in range(l):
        k=lrd[i][j]
        if x[k[0]]!=x[i]+k[1]:
            print("No")
            sys.exit()
print("Yes")