Acing Programming Contest 2020
This time's results
Impressions
It was the most difficult set in the ABC class, it was difficult.
D I was too confused about the policy of the problem and spent time, but when I experimented, I found out, the experiment is important.
I was watching the E problem for quite some time, but I didn't try the greedy algorithm. I'm still immature that I haven't learned the basics of the basics yet, so I want to do my best ... I want to grow to a level where I can call myself a competitive professional er.
Problem A
You can count how many multiples of D are from the smallest multiple of D above L to the maximum multiple of D below R.
This can be rephrased as ceil (l / d) * d, ceil (l / d) * d + d,…, floor (r / d) * d, so the number is floor (r / / d) -ceil (l / d) + 1.
A.py
from math import *
l,r,d=map(int,input().split())
print(floor(r/d)-ceil(l/d)+1)
Problem B
All you have to do is make sure that the number of squares written as odd is odd for all numbers.
B.py
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
ans+=(i%2==0 and a[i]%2==1)
print(ans)
C problem
I suspected factorization for a moment, but it's difficult. However, $ 1 \ leqq x \ leqq \ sqrt {n}, 1 \ leqq y \ leqq \ sqrt {n}, 1 \ leqq z \ leqq \ sqrt {n} $ was immediately understood by looking at the squared term. , You can search all the values of $ x, y, z $ ($ O (N \ sqrt {N}) $ is enough).
Also, what you want to find is the value of $ f (1), f (2),…, f (n) $, which is $ x ^ 2 + y ^ 2 + z ^ 2 + xy + yz during the full search. You can record the value of + zx $ from $ 1 $ to $ N $ one by one.
C.py
from math import *
n=int(input())
l=floor(sqrt(n))+1
ans=[0]*n
def f(a,b,c):
return a*a+b*b+c*c+a*b+b*c+c*a
for x in range(1,l+1):
for y in range(1,l+1):
for z in range(1,l+1):
g=f(x,y,z)
if g<=n:
ans[g-1]+=1
for i in range(n):
print(ans[i])
D problem
It took me a long time to solve the problem because I was thinking about it. It's difficult to choose a problem to solve ... If it's an ABC-class problem, I'd like to work hard enough to afford it.
In the following, the number given by input is $ x $ and its popcount is $ c $.
Obviously, even if you implement popcount ** honestly, it will not be in time ** because $ x $ will be a very large number. However, for a certain number of $ K $, the value of the popcount is about $ \ log {K} $, so due to the constraint of the subject, it only takes about 5 times to repeat ** popcount to 0 ** ( It can be said that it is almost a constant multiple under the constraint of the problem.)
Now, let's think about finding $ f (X_i) $ honestly for $ 1 \ leqq i \ leqq N $, but in the first operation, it costs $ O (N) $ to check all the digits. So the total complexity is $ O (N ^ 2) $. (** Think honestly and reduce that waste! **)
However, ** $ f (X_i) $ changes only the $ i $ digit **, so consider the difference due to the inversion of that digit after saving $ x $. Also, if the $ i $ digit is $ 0 $, it will change to $ 1 $, so this number of popcount will change to $ c-1 $, and if the $ i $ digit is $ 1 $, it will change to $ 0 $, so this number of popcount will change. It becomes $ c + 1 $, and there are only these two ways.
Therefore, it is possible to achieve this policy by preparing the following two in the pre-calculation (note that it is necessary to completely separate the case of $ c-1 $ and the case of $ c + 1 $. Is required.).
$ i $ Array $ m $ that stores the remainder of the difference when changing digits
→
These can be prepared by pre-calculation of $ O (N) $, each calculation of $ f (X_i) $ is $ O (1) $ for the first popcount difference calculation, and the subsequent popcounts are normal popcount. Since it can be done with a constant multiple of $ O (\ log {N}) $ using a function etc., it is possible to calculate with $ O (N \ log {N}) $ in total, and even Python can afford it. You can pass it with.
As an additional note, when c becomes 1, ** 0 division occurs **, so it is necessary to avoid it.
D.py
#Division by zero
import math
def popcount(x):
s=0
y=int(math.log2(x))+2
for i in range(y):
if(x>>i)&1:
s+=1
return x%s
n=int(input())
x=input()[::-1]
#What 1 will come out
c=x.count("1")
#c+1 and c-Just think about 1
#c=Time division of 1
#m[i][j]:2^mod when thinking up to i(c+j-1)
if c!=1:
m=[[1%(c-1),1%(c+1)]]
for i in range(n-1):
m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
l=[0,0]
for i in range(n):
if x[i]=="1":
l[0]+=m[i][0]
l[1]+=m[i][1]
l[0]%=(c-1)
l[1]%=(c+1)
else:
m=[[1%(c+1),1%(c+1)]]
for i in range(n-1):
m.append([(2*m[-1][0])%(c+1),(2*m[-1][1])%(c+1)])
l=[0,0]
for i in range(n):
if x[i]=="1":
l[0]+=m[i][0]
l[1]+=m[i][1]
l[0]%=(c+1)
l[1]%=(c+1)
#I want to change only one, so I want the whole
#Use popcount except for the first time
ans=[0]*n
for i in range(n):
if x[i]=="1":
if c-1==0:
ans[i]=0
continue
p=(l[0]+(c-1)-m[i][0])%(c-1)
ans[i]+=1
while p!=0:
p=popcount(p)
ans[i]+=1
else:
p=(l[1]+m[i][1])%(c+1)
ans[i]+=1
while p!=0:
p=popcount(p)
ans[i]+=1
ans=ans[::-1]
for i in range(n):
print(ans[i])
E problem
It is impossible to use a short-circuit idea such as choosing either → $ 2 ^ N $ → DP, so first consider the solution by the greedy method **.
Here, for the $ i $ th camel, you can get ** $ min (L_i, R_i) $ regardless of the order of getting $ L_i or R_i
During the contest, I could only come up with the idea so far, but ** I think about camels that want to choose the left side and camels that want to choose the right side ** (($ L_i-R_i, 0
Under this, it can be said that the camel who wants to choose the left side and the camel who wants to choose the right side ** do not interfere (independently) ** how to choose the position of the camel. This is because the camel position can be moved as shown in the figure below if the former is a red circle and the latter is a blue circle.
Therefore, in the following, we will first consider greedily deciding the position of the camel you want to choose the left side. At this time, we will greedily choose from the ones with the largest $ L_i-R_i $ (within the $ K_i $ th), so consider the optimum position. ** The optimal position can be rephrased as the position that does not hurt the selection of subsequent elements **. At this time, you can see that the $ K_i $ th, which has the most selectable positions for other camels after that, is optimal. Also, since there is no position that you can get more than this when you place it on the left side of ** $ K_i $ th, you can see that it is correct from this idea. Furthermore, if the $ K_i $ th is already selected, you can select the rightmost position on the left side of it.
From the above, save the unselected positions in ascending order (use set), select the largest position below $ K_i $ (next to one of the elements selected by upper_bound) as the position, and then delete it from the set. Just do it. Also, at this time, if there is no corresponding position, that element cannot be selected, so consider the next element. Then, consider this not only on the left side but also on the right side, and the sum of all the selected elements is the answer.
New findings about greedy algorithm
→ ** You may move it in a direction that does not damage **! !! To put it the other way around, consider ** Is there a pattern that can be obtained in cases other than how to move it **?
F problem
I will skip this time.
Recommended Posts