AtCoder Beginner Contest 180 Review
This time's results
Impressions of this time
It was a good grade. This F was difficult and I didn't feel like I could solve it at all. I understood it by looking at the answer, but it seems that it can not be applied, so I will not upsolve this time. I realized that the E problem was typical. It was a typical pattern that I had never solved before, so I will review it often.
Problem A
I thought that the problem was not established when $ n <a $, but $ n \ geqq a $ holds because of the constraint.
A.py
n,a,b=map(int,input().split())
print(n-a+b)
B problem
Just implement it according to the problem statement. Actually, there is no problem if you convert the input to an absolute value as it is.
B.py
n=input()
x=list(map(lambda y:abs(int(y)),input().split()))
print(sum(x),sum([i*i for i in x])**0.5,max(x))
C problem
I misread that it was okay to have extra cream puffs when I distributed it, and misunderstood that it was a problem of finding candidates for the value of $ [\ frac {n} {k}] $.
All you have to do is list the divisors as they will be distributed so that there is no excess.
C.py
def m():
n=int(input())
d=[]
for i in range(1,int(n**0.5)+1):
if n%i==0:
d+=[i]
if i!=n//i:d+=[n//i]
d.sort()
return d
for i in m():print(i)
D problem
It's just a matter of calmly classifying the cases, but I have issued 2WA ... As a result, it was a blue performance if 1WA was enough, so I'm disappointed.
Choose between multiplying A and adding B. The former and the latter make the best choice, but ** once the former is no longer optimal, the latter is always the best after that **. You can also see this by comparing the amount of change between $ \ times A $ and $ + B $.
Therefore, consider the case where it is best to multiply $ x $ by A (the value of $ x $ multiplied by A is smaller than the value of $ \ leftrightarrow $$ x $ plus B). At this time, it is natural to use $ x \ times A \ leqq x + B $ in the comparison conditional expression, but it is also necessary to set the condition ** so as to satisfy ** $ x \ <y $. If you implement it carefully inside the loop, the calculation of adding $ B $ after exiting the loop will only find $ ans + [\ frac {y-x-1} {b}] $.
D.py
x,y,a,b=map(int,input().split())
ans=0
while True:
if x*a<=x+b:
if x*a>=y:
print(ans)
exit()
else:
ans+=1
x*=a
else:
#From here+
#x*a>x+b
#x<y
break
print(ans+(y-x-1)//b)
E problem
It seems that it was a typical problem, but when I look at it after solving it, I feel that it is also the case.
The process of considering the contest is described below. In addition, the three-dimensional coordinates of the subject shall be stretched on the $ x $ axis, $ y $ axis, and $ z $ axis.
First, the maximum is $ n = 17 $, so ** $ n! $ Is not in time **. I couldn't try to apply it because the most common problem with $ 2 ^ n $ is a half full enumeration. Next, I thought about ** looking at the cost formula and seeing if it could be decided well **, but when connecting the two vertices, it seems better to connect from the larger $ z $ coordinate to the smaller one. I only know. Here, if you look at the constraint, you will notice that it passes ** if it is bitDP because it is ** $ 2 ^ {17} $. Therefore, considering the DP that manages the set of cities that have arrived, it is as follows.
$ dp [i] [j]: = $ (sum of the minimum costs when the cities contained in the subset $ i $ have been reached and are in the city $ j $)
** If you want to represent the set of cities you have reached in bits, you can think of it as long as you remember that it is bitDP **. This issue is also a variant of the famous TSP (Traveling Salesman Problem).
Here, the order of DP transitions should be as follows in the order of small states $ i $ (integer) ** (✳︎). Initialization is done only for $ dp [1] [0] = 1 $. (Consider the transition to the city $ k $ when you are in the city $ j $ for a certain $ i $. You don't have to think about it when $ j = k $. Also, $ dist [j] [k] $ is $ The cost of going from j $ to $ k $.)
From the above, $ dp [1 \ <\ <n-1] [0] $ is the answer because it ** will eventually return to City 1.
(✳︎)… I will prove that you can do it in ascending order. In other words, it is shown here that any way of movement can be expressed.
When moving from the state of $ i $ to $ j $ → $ k $, the state becomes $ i $ → $ i | (1 \ <\ <k) $. In other words, by taking ** bitwise or, the state (integer representing) is non-decreasing **. Therefore, if you make a transition (update) ** in ascending order of the state (integer representing), you can express all the movement methods. Also, when the transition is viewed as a directed edge with each state $ i $ as the apex, it can be updated from the smaller ** $ i $ if it is ** topologically sorted, and this is true for bitDP. I think it can be interpreted. Furthermore, you can understand that the integer representing the state in the transition is non-decreasing by thinking that $ j $ smaller than ** $ i $ does not include $ i $ **.
[Added on 2020/10/18]
The above discussion implicitly uses ** that it is shorter not to go through another city when moving from one city to another **, but this is because the triangle inequality is a cost equation. It can be shown from the fact that it holds **. Also, if it is shorter to go through other cities, you can ** first find the cost between all cities with Worshall Floyd and then ** do the same bitDP.
E.py
n=int(input())
tos=[list(map(int,input().split())) for i in range(n)]
#Cost from 1 to j
def co(i,j):
return abs(i[0]-j[0])+abs(i[1]-j[1])+max(0,j[2]-i[2])
inf=10**12
dp=[[inf for j in range(n)] for i in range(1<<n)]
dp[1][0]=0
for i in range(1,1<<n):
for j in range(n):
#Never return to myself
for k in range(n):
if j==k:continue
dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+co(tos[j],tos[k]))
ans=inf
for i in range(n):
ans=min(ans,dp[(1<<n)-1][i]+co(tos[i],tos[0]))
print(ans)
F problem
I will not solve this time.
Recommended Posts