[PYTHON] AtCoder Beginner Contest 162 Review
This time's results
Impressions of this time
It's not bad in terms of performance, but I'm very sorry because I couldn't solve both E and F (even though it took an hour). For the time being, I would like to review what E and F lacked.
Problem A
Whether or not 7 is included can be handled as a character string. Why are you converting to a list? I'm too crazy.
A.py
n=list(input())
print("Yes" if "7" in n else "No")
B problem
You can think of the sum of things that can't be broken by either 3 or 5. It took a few minutes because I set i% 3 == 0 and i% 5 == 0. ** If it doesn't work, it doesn't work from the beginning **. I would like to fix it from the next contest.
B.py
ans=0
n=int(input())
for i in range(1,n+1):
if i%3!=0 and i%5!=0:
ans+=i
print(ans)
C problem
I have issued WA ... You can understand that it will not pass unless you think calmly and devise a little. ** You can see the result of gcd (i, j) at the time of the outer double loop **, so if you calculate gcd (i, j) in the innermost loop, it will be calculated more and it will be in time for the time limit not. (I was too impatient during the contest and passed it in C ++, but it also passes normally in Python.)
C_TLE.py
from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
for j in range(1,k+1):
for l in range(1,k+1):
ans+=gcd(gcd(i,j),l)
print(ans)
C.py
from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
for j in range(1,k+1):
ans_=gcd(i,j)
for l in range(1,k+1):
ans+=gcd(ans_,l)
print(ans)
D problem
I also solved the D problem with a lot of impatience. After all, it may be that ** if you put too much effort into it, it will fail on the contrary **. The first thing that is easy to understand from this problem is that the three letters to choose are ** R, G, and B, respectively **. Also, since the relationship between the indexes of each character becomes a problem, I decided to store the indexes of characters R, G, and B separately in an array **. Also, if you think in the shortest way under this, you should decide in the order of r → g → b and consider whether the index satisfies the theme. However, ** If nothing is done, N <= 4000 will result in O ($ N ^ 3 `x-(yx)`, You can see that there are three ways of `x + (yx)` `,` `(x + y) / 2 (the evenness of x and y is the same)` (index size of R, G, B) It was found by illustrating the relationship between the two.) Once you know this, you can find the answer by managing the index of B with set and subtracting only the index that is not a candidate.
answerD.py
n=int(input())
s=input()
r,g,b=[],[],[]
for i in range(n):
if s[i]=="R":
r.append(i)
elif s[i]=="G":
g.append(i)
else:
b.append(i)
b=set(b)
lb=len(b)
ans=0
for i in r:
for j in g:
x,y=min(i,j),max(i,j)
ans_=lb
if x-(y-x) in b:
ans_-=1
if y+(y-x) in b:
ans_-=1
if (x%2==y%2) and (y-x)//2+x in b:
ans_-=1
ans+=ans_
print(ans)
E problem
Continuing from the last time, the E and F problems were very educational, so it is worth studying. If this level band (light blue, blue) can be solved stably, it seems that the results will be stable, so I would like to solve the problem in this level band as much as possible. In this problem, we consider the gcd of the combination of $ K ^ N $, so we can see that ** counting everything is not enough **. Therefore, let's consider how many ** gcd values ** there are. Also, since the value of gcd is 1 ~ k from the definition of gcd, look for the sequence $ A_1, A_2,…, A_n $ where gcd is x ($ 1 \ leqq x \ leqq k $). Here, the necessary and sufficient condition ** for ** gcd to be a multiple of x is ** $ A_1, A_2,…, A_n $ is a multiple of x **, so $ (k // x) ^ There are n $ streets. However, the necessary and sufficient condition ** for ** gcd to be exactly x is that it is a multiple of ** x and not 2x, 3x,… **. Therefore, in order to find the number of cases where gcd is x, we have to subtract the cases where gcd is 2x, 3x,… from $ (k // x) ^ n $. However, if you move x from 1 to k, you will need to check if 2x, 3x, ... is less than or equal to k and subtract the number in that case. In this case ** 2x, 3x, The number of cases of… is not always fixed **. An effective idea here is to think of ** x in the reverse order of k → 1 instead of 1 → k **. In this case, it can be calculated by first calculating how many sequences such that gcd is 2y, 3y, ... and subtracting from the candidates of the sequence such that gcd is y. Also, since we want to consider y for which $ x = l \ times y (l \ geqq 1) $ holds, you can easily see that ** y is a divisor of x **. From the above, regarding the number of candidates in the sequence when gcd is a divisor of y excluding y itself $ x_1, x_2,…, x_m $, it is sufficient to subtract the number of candidates in the sequence where gcd is y. Implementing these, it looks like this: Also, the answer is that you have to find the remainder of $ 10 ^ 9 + 7 $, and when you initialize the memo array, specify $ 10 ^ 9 + 7 $ as the third argument of pow to get $ 10 ^ 9 + 7 $. It is also important to note that the calculation can be speeded up by asking too much.
answerE.py
def make_divisors(n):
divisors=[]
for i in range(1, int(n**0.5)+1):
if n%i==0:
divisors.append(i)
if i!=n//i:
divisors.append(n//i)
divisors.sort()
return divisors
n,k=map(int,input().split())
mod=10**9+7
memo=[pow(k//i,n,mod) for i in range(1,k+1)] #gcd is 1~Make a note of when it becomes k
for i in range(k-1,-1,-1):
x=make_divisors(i+1)
for j in x:
if j!=i+1:
memo[j-1]-=memo[i]
ans=0
for i in range(k):
ans+=(memo[i]*(i+1))
ans%=mod
print(ans)
F problem
I was so used to the shape of the knapsack DP that I didn't notice the state transition DP (it's not the official name because I just call it that way). ** I tried to solve the dark clouds like a puzzle ** and I didn't understand. Problems like this can be ** surprisingly visible with a little abstraction **. First, since the upper limit of the number that can be selected is n // 2, isn't there an upper limit to the number that can be selected up to the ** i th (i = 1,2, ..., n)? It is important to have the question **. Therefore, based on this question, ** the number of adjacent numbers cannot be selected **, so it can be seen that the number that can be selected from the 1st to the ith is (i + 1) // 2 or less. Furthermore, the number that can be selected from the i + 1 to nth is (n-i + 1) // 2 or less, and only n // 2 is selected from 1 to n, so the number that can be selected from the 1st to ith is Must also have the condition n // 2- (n-i + 1) // 2 = (i-1) // 2 or more. Therefore, the condition that ** the number of numbers to be selected up to the i-th must be (i-1) // 2 or more (i + 1) // 2 or less ** is obtained. Now that we know that there is a limit to the number of numbers that can be selected up to the i-th, ** the relationship between the number of numbers that can be selected up to the i-th and the number that can be selected up to the i-th ** and ** It seems natural to come up with the idea of thinking about the relationship between the number of numbers selected up to the i-th and the number of numbers selected up to the i + 1st **.
Figure 1
Figure 2
Figure 3
Figures 1 to 3 above are written based on this idea. First, in Fig. 1, the number of numbers that can be selected in the i-th is written in order from the first (Fig. 2 is in order from the second). I tried to prepare an array of DP that saves the two states as it is, but since it did not fit from the sample case, I looked closely and found that only these two states ** except when two numbers are consecutive * * I wasn't able to. That is, in Fig. 1, the red arrow advances from 0 to 1 to 1, but not from 0 to 1 to 2. Conversely, for the blue arrow, you can proceed in both 1 → 1 → 1 and 1 → 1 → 2. The same is true for Fig. 2. For the red arrow, both 1 → 1 → 1 and 1 → 1 → 2 can be advanced, but for the yellow arrow, only 0 → 1 → 1 can be advanced, but 0 → 1 → 2 I can't proceed. Therefore, in Fig. 1, for the second 0,1 ** increase the state by one ** to 0,1,1 and the first 1 is the second if the second number is not selected. 1 should be the case if you choose the second number. Also, in Fig. 2, the third 1,2 is 1,1,2, the first 1 is when the third number is not selected, and the second 1 is when the third number is selected. You can do it. Figure 3 summarizes the above. If you look carefully at Figure 3, you can see that the arrow points to different points depending on whether the index is even or odd. However, if you do not select the i-th number at this time, it is written as 1 if you select it with $ \ pm $ 0, and you need to check if → is closed according to this notation. By implementing up to this point obediently, it becomes as follows. Please note that the output differs depending on whether n is an even number or an odd number.
To restate what you need to think so far,
(1) Pay attention to what kind of constraint (upper limit) there is as the number of numbers up to the i-th.
(2) Derive that the number of numbers that can be selected up to the i-th is two.
(3) Experiment by paying attention to the relationship between before and after the i-th (i-1st and i + 1th)
(4) Notice that there are 2 different numbers up to the i-th, but 3 different states.
(5) The way of state transition differs depending on the evenness of the index.
It is considered that there are five. Personally, I thought that (1) was hard to notice, but ** considering that the limit on the number of pieces up to the nth is n // 2 or less, I think that it is not a barrier that cannot be exceeded. I would like to devote myself and grasp it sensuously.
answerF.py
n=int(input())
a=list(map(int,input().split()))
minf=-10000000000000
x=[[0,0,0] for i in range(n)]
x[0]=[0,0,a[0]]
for i in range(n-1):
if i%2==0:
x[i+1]=[max(x[i][0],x[i][1]),x[i][2],x[i][0]+a[i+1]]
else:
x[i+1]=[max(x[i][1],x[i][2]),x[i][0]+a[i+1],x[i][1]+a[i+1]]
print(max(x[-1][1],x[-1][2]) if n%2==0 else max(x[-1][0],x[-1][1]))
Recommended Posts