[PYTHON] M-SOLUTIONS Procon Open 2020 Review
This time's results
Impressions
It's the backwater team ... Highest updated! I was thinking ... The case of D did not work well, and I felt like I could move to F and solve it, but I misunderstood the problem. The solution I came up with 15 minutes ago was correct and I was able to solve it myself after the contest, so I thought I should concentrate on my efforts during the contest with the intention of dying. Specifically, I thought it would be better to restart the virtual console (ABC has solved quite a bit, so Codeforces div2, 3) or solve the problem of water blue yellow diff with a time limit of 30 minutes to 1 hour. It was.
Posting a review article has been delayed for a week. I want to be careful after that ... I haven't been excited at all lately, but I have no choice but to believe that it will grow someday. Because the earth power should be following.
Problem A
It was a little troublesome problem from the first question. However, if you put ** values to compare ** in an array, you can think about it just by turning the loop.
A.py
x=int(input())
h=[1800,1600,1400,1200,1000,800,600,400]
for i in range(8):
if x>=h[i]:
print(i+1)
break
Problem B
Consider the number of times it takes to make $ a <b <c $, and consider whether it exceeds $ k $ times. You can double $ b and c $ respectively so that the equal sign holds in the order of $ a <b $ → $ b <c $.
B.py
a,b,c=map(int,input().split())
k=int(input())
ans=0
while a>=b:
ans+=1
b*=2
while b>=c:
ans+=1
c*=2
print("Yes" if ans<=k else "No")
C problem
If you multiply all the numbers, it will take time to calculate, so consider omitting it. The score for the latest $ K $ semester is required, and the score will be off by only one semester between the previous and next semesters, so ** consider the difference **.
This deviation is the red part above, so when the $ i $ semester rating is higher than the $ i-1 $ semester rating, the $ i $ semester final exam score is the $ ik $ semester final exam score. The higher it is, the better.
C.py
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*(n-k)
for i in range(k,n):
ans[i-k]=(a[i]>a[i-k])
for i in range(0,n-k):
print("Yes" if ans[i] else "No")
D problem
Since the implementation did not fit and it seemed to take time, I discarded D and solved F. I couldn't match the implementation in one shot, so it's totally useless. The cause is that I solved it with ** rough policy **.
First, I tried to save the state with DP, but I couldn't think of how to hold the state. When I think about it now, the state of money I have is limited, so considering the implementation, DP may be better ... For details, please refer to Explanation.
It was difficult to grasp the movement of the amount of money per share, so I thought about ** line graph **, but I think this was a good move. (If you are in trouble, ** illustrated! Experiment! **)
As shown in the above figure, the method of receiving the maximum profit of the stock is to obtain all the increase and decrease as profits (you can not receive any more profits by considering the total absolute value of the amount of change. .). Therefore, you only have to save the ** bottom value and ceiling value **, buy at the bottom and sell at the ceiling, and save the values where the positive and negative changes are interchanged. Also, as of ** $ N $ day, ** all stocks must be sold, so if the stock price is rising on $ N $ day, all stocks will be sold on $ N $ day, and vice versa. If it doesn't rise to, you don't need to buy or sell stocks on the $ N $ day as you have already sold out all the stocks.
If the above is implemented, it will be as follows. Sorry for the hard-to-read code.
D.py
#bottom or top
n=int(input())
a=list(map(int,input().split()))
an=[]
for i in range(1,n):
if a[i]>a[i-1]:
an.append(a[i-1])
if i==n-1:
an.append(a[i])
break
pm=0
for j in range(i+1,n):
if pm==0:
if a[j]>=a[j-1]:
if j==n-1:
an.append(a[j])
continue
else:
an.append(a[j-1])
pm=1
else:
if a[j]<=a[j-1]:
continue
else:
an.append(a[j-1])
pm=0
if j==n-1:
an.append(a[j])
ans=1000
k=0
for i in range(len(an)):
if i%2==0:
k=ans//an[i]
ans-=k*an[i]
else:
ans+=k*an[i]
k=0
print(ans)
E problem
I will not solve this time.
F problem
I couldn't solve it even after an hour during the contest, but it was a problem that I felt I could have solved if I could ** organize the information properly **. Also, my implementation code is pretty dirty, so please refer to the other person's code.
The following U, D, R, and L are the directions in which the airplane travels, and are the same as the notation in the problem statement.
First of all, ** airplanes facing in the opposite direction ** are likely to collide. That is, there are two combinations, one with the same $ x $ coordinates and the direction of travel U-D, and the other with the same $ y $ coordinates and the direction of travel R-L. Also, in the former case, the U coordinate must be smaller than the D coordinate, and in the latter case, the R coordinate must be smaller than the L coordinate.
Also, since we want to find the pair with the closest initial position of each airplane, ** the optimum D for the pair of U airplanes ** is the $ y $ coordinate with the same $ x $ coordinates and the $ y $ coordinate of U. With that, if you save the possible $ y $ coordinates for each $ x $ coordinate in ascending order, you can find the initial position of the airplane using bisect_left. Similarly, R-L can be searched by saving it for each $ y $ coordinate. Then, the set of airplanes in the closest initial position is obtained, and this value is multiplied by ** 5 ** to obtain the number of seconds.
Actually, there are ** other patterns ** as airplanes that can collide (I came up with it about 15 minutes before the end of the contest, so I gave up implementing it). Specifically, it is a pattern of U-R, U-L, D-R, D-L. However, unlike before, it is difficult to manage the $ x $ or $ y $ coordinates. Therefore, how far the collision position is from the initial position is $ t (\ geqq 0) $, and the initial position of the airplane included in U (or R) is $ (x_1, y_1) $, D (or L). Assuming that the initial position of the airplane included in is $ (x_2, y_2) $, we considered the condition of the initial position of the set of colliding airplanes (** generalization **!). Then, it became as follows.
(1) At the time of U-R
(2) At the time of U-L
(3) At the time of D-R
(4) At the time of D-L
Therefore, in each case, you can save ** separately for each initial position where the addition or subtraction of the x-coordinate and y-coordinate of the initial position is equal. Also, in the case of (1) and (3), $ x1> x2 $, and in the case of (2), (4), we want to find the set with the smallest initial position distance among satisfying $ x1 <x2 $. If you save only the $ x $ coordinates in ascending order when dividing by initial position, the closest initial position pair can be found using bisect_left, bisect_right. Then, what we want is the difference between the $ x $ coordinates of the initial position, which corresponds to $ t $, so the answer is a candidate for this value multiplied by ** 10 **.
F.py
#When merging at a cross
#The position of the if statement was wrong
n=int(input())
ud=[[[],[]] for i in range(200001)]
rl=[[[],[]] for i in range(200001)]
from bisect import *
cross=[[dict(),dict()] for i in range(4)]
for i in range(n):
x,y,u=input().split()
x,y=int(x),int(y)
if u=="U":
ud[x][0].append(y)
if x+y in cross[0][1]:
cross[0][1][x+y].append(x)
else:
cross[0][1][x+y]=[x]
if x-y in cross[1][1]:
cross[1][1][x-y].append(x)
else:
cross[1][1][x-y]=[x]
elif u=="D":
ud[x][1].append(y)
if x+y in cross[3][1]:
cross[3][1][x+y].append(x)
else:
cross[3][1][x+y]=[x]
if x-y in cross[2][1]:
cross[2][1][x-y].append(x)
else:
cross[2][1][x-y]=[x]
elif u=="R":
rl[y][0].append(x)
if x+y in cross[0][0]:
cross[0][0][x+y].append(x)
else:
cross[0][0][x+y]=[x]
if x-y in cross[2][0]:
cross[2][0][x-y].append(x)
else:
cross[2][0][x-y]=[x]
else:
rl[y][1].append(x)
if x+y in cross[3][0]:
cross[3][0][x+y].append(x)
else:
cross[3][0][x+y]=[x]
if x-y in cross[1][0]:
cross[1][0][x-y].append(x)
else:
cross[1][0][x-y]=[x]
for i in range(200001):
ud[i][0].sort()
ud[i][1].sort()
rl[i][0].sort()
rl[i][1].sort()
ans=[]
for i in range(200001):
l1,l2=len(ud[i][0]),len(ud[i][1])
if l1 and l2:
for j in ud[i][0]:
b=bisect_left(ud[i][1],j)
if b!=l2:
ans.append(ud[i][1][b]-j)
l1,l2=len(rl[i][0]),len(rl[i][1])
if l1 and l2:
for j in rl[i][0]:
b=bisect_left(rl[i][1],j)
if b!=l2:
ans.append(rl[i][1][b]-j)
for i in range(4):
for j in range(2):
for k in cross[i][j]:
cross[i][j][k].sort()
for i in range(4):
for j in cross[i][1]:
if j in cross[i][0]:
l=len(cross[i][0][j])
if i%2==1:
for k in cross[i][1][j]:
b=bisect_left(cross[i][0][j],k)
if b!=l:
ans.append(2*cross[i][0][j][b]-2*k)
else:
for k in cross[i][1][j]:
b=bisect_right(cross[i][0][j],k)-1
if b!=-1:
ans.append(2*k-2*cross[i][0][j][b])
if len(ans):
print(min(ans)*5)
else:
print("SAFE")