AtCoder Beginner Contest 180 Review

This time's results

スクリーンショット 2020-10-18 10.35.02.png

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 $.)

dp[i|(1\<\

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

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions