This is a review article for beginners of competition professionals.
The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
A - Coffee It is a problem to determine whether the 3rd and 4th characters of a given character string are the same, and the 5th and 6th characters are the same.
The following code is implemented as it is. This is OK.
s = input()
if s[2] == s[3] and s[4] == s[5]:
print('Yes')
else: print('No')
B - Golden Coins
If you exchange the given amount of money n and convert it to 1000 for each 500-yen coin and 5 for each 5-yen coin, what is the maximum value? Is the problem.
The number of 500-yen coins is n // 500, and the number of 5-yen coins is n% 500 // 5.
I implemented it as follows.
n = int(input())
print(n//500*1000 + n%500//5*5)
C - Traveling Salesman around Lake Given the location of the houses that exist around the lake, it is a matter of considering the distance to go around all the houses in the shortest path.
The position of the northern end of the lake was set to 0, and the positions of the houses were stored in the array for two laps clockwise from there. Starting from one of the houses on the first lap, we calculated the distance to go around all the houses and calculated the maximum value.
K, N = map(int, input().split())
A = list(map(int, input().split()))
A += [a+K for a in A]
minD = 1e6
for n in range(N):
minD = min(minD, A[n+N-1] - A[n])
print(minD)
The way of writing was different in the commentary. The lake goes around almost all but a part. The part that doesn't pass is between the farthest houses.
I rewrote it a little. This is more beautiful.
K, N = map(int, input().split())
A = list(map(int, input().split()))
A.append(A[0]+K)
maxD = 0
for n in range(N+1):
maxD = max(maxD, A[n+1] - A[n])
print(K-maxD)
Postscript: Since python can take a negative index like li [-1], there is no need to increase the array.
D - Line++
It is a problem to get the distribution of the shortest path length from a given graph.
There is a library called networkx that can handle graph theory in python. It is a very convenient library that can get each parameter from the graph creation. Now let's calculate the distribution.
import networkx as nx
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
out = [0] * N
G = nx.Graph()
G.add_nodes_from(list(range(N)))
G.add_edges_from([(i, i+1) for i in range(N-1)] + [(X, Y)])
for i in range(N-1):
for j in range(i+1, N):
out[nx.shortest_path_length(G, i, j)] += 1
for i in range(1, N):
print(out[i])
Well, I can't use this library with atcoder.
I couldn't study graph search, so I gave up and went to the next problem.
I saw the commentary. This problem doesn't seem to require any difficult search. There are only two choices for the distance from point A to point B: BA (when proceeding one by one) or ʻabs (AX) + 1 + abs (BY)` (when passing through the XY shortcut). There is none. The shorter of these two is the shortest path.
So, the following code is a rewrite of the above code only for the shortest path search method.
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
out = [0] * N
for i in range(N-1):
for j in range(i+1, N):
out[min(j-i, abs(i-X)+1+abs(j-Y))] += 1
for i in range(1, N):
print(out[i])
I passed by this.
E - Red and Green Apples You will be given a red apple with a deliciousness of $ p_i $, a green apple with a deliciousness of $ q_i $, and a colorless apple with a deliciousness of $ r_i $. It is a problem to find the maximum taste when eating X red apples and Y green apples. The key is how to handle colorless apples.
Take X from the red apples in order of deliciousness and Y from the green apples in order of deliciousness. All you have to do is replace the X + Y apples with colorless apples one by one.
X, Y, A, B, C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort()
Q.sort()
R.sort()
out = P[-X:] + Q[-Y:]
out.sort()
for i in range(min(C, X+Y)):
if R[-i-1] > out[i]:
out[i] = R[-i-1]
else:
break
print(sum(out))
With this, I was able to solve it with plenty of calculation time.
That's all for this article.
Recommended Posts