[PYTHON] AtCoder Beginner Contest 165 Review
This time's results
Impressions of this time
The C problem seemed to be severe and it wasn't that difficult, so I should have considered it properly. I've been trying to build an E problem, but I couldn't think enough about it and couldn't finish solving it during the contest. I am very disappointed.
Problem A
When I thought that I changed the policy because the for statement appeared in problem A, I simply lacked my own consideration. All you have to do is make sure that a to b are multiples of k, so the code looks like this: It's also easier to write with the any function.
A.py
k=int(input())
a,b=map(int,input().split())
for i in range(a,b+1):
if i%k==0:
print("OK")
break
else:
print("NG")
B problem
Repeat the operation of multiplying by 1.01 and devaluing until it becomes X yen or more, and count the total of the operations.
B.py
import math
ans=0
x=int(input())
y=100
while y<x:
ans+=1
y=math.floor(1.01*y)
print(ans)
C problem
This time it will be a rough C problem.
First, the moment you see it, is it a weighted Union Find? However, this consideration is ** algorithm-based **, so it should never be done. In this issue, I was able to reaffirm the basics (I want to be sloppy ...).
Also, at first glance, this problem requires you to search the entire $ M ^ {10} $ street, but the constraint of $ 1 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M $ can be quite tight. Obviously (you can tell by experimenting with small N, M. ** I neglected this experiment during the contest. **), $ A_1, A_2,…, A_N $ is less than $ M ^ {10} $ streets You can suspect that. Therefore, for the time being, I will try to solve it with the policy of full search. You can find out how many ways there are by looking at Explanation, but I think it's a little difficult to consider so far during the contest.
Here, ** if you can select the policy of full search **, the rest is not so difficult. You can set $ A_1, A_2,…, A_N $ in order from the front, so you can use DFS here (you can nest N for statements, but ** many fors like this. If it looks like a nested statement **, you can easily write a similar process in DFS **).
In the case of DFS, prepare an array with up to $ A_1, A_2,…, A_d $ (or a character string ← described later), and a function that takes the above three arguments, d and $ A_d $, and d arrives at N. If so, the score of the sequence is calculated, and if N is not reached, the value above $ A_d $ and below M can be the next $ A_ {d + 1} $, so all of them are recursive functions. Just call the case. At this time, it may be easier to understand if you save up to $ A_1, A_2,…, A_d $ as a character string. In other words, the same result can be obtained by changing $ 1 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M \ leqq 10 $ to $ 0 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M-1 \ leqq 9 $. Therefore, each number can be unified with a single digit, and the code for recursion becomes easier to see when viewed as a character string.
Also, after the contest, I found out by looking at maspy's tweet, but in Python ** about the iterable data structure x There seems to be a function ** combinations_with_replacement that allows duplicate elements and returns a subsequence of elements of length r (first argument is x and second argument is r). In addition, the combinations are generated in lexicographic order, so if the original iterable data structure is sorted, the combinations are available as sorted tuples. Therefore, in this problem, if you specify `range (1, m + 1) ``` for x and `n``` for r, the tuple that agrees with the array (or string) generated by DFS will be obtained. Can be generated. I would like to check the functions around itertools like this once.
C.py
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
R=[range(i,m) for i in range(m)]
def dfs(s,d,l):
global n,m,Q,ans
if d==n:
ans_=0
for k in Q:
a,b,c,e=k
if int(s[b-1])-int(s[a-1])==c:
ans_+=e
ans=max(ans,ans_)
else:
for i in R[l]:
dfs(s+str(i),d+1,i)
dfs("",0,0)
print(ans)
C.py
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
for s in combinations_with_replacement(range(1,m+1),n):
ans_=0
for k in Q:
a,b,c,d=k
if s[b-1]-s[a-1]==c:
ans_+=d
ans=max(ans_,ans)
print(ans)
D problem
Personally, it was easy, but many people seemed to find it difficult. After all, ** the first policy is important **, so I want to improve my understanding.
First, considering the case where x is a multiple of B, it becomes 0, and I thought that if the remainder of ** B is small, the calculation result will be small **. Under this, if $ x = k \ times B + l \ (0 \ leqq l \ leqq B-1)
Also, the assumption of $ 0 \ leqq l \ leqq B-1 $ and $ [\ frac {Al} {B}] $ increase monotonically with respect to $ l $, so $ l = B-1 $ is the maximum Will be. Also, in the case of $ n \ leqq B-1 $, n is the maximum, so the answer you want is $ [\ frac {A \ times min (B-1, n)} {B}] $.
answerD.py
a,b,n=map(int,input().split())
print(a*min(b-1,n)//b)
I played a little code golf. It was a shortest.
answerD_shortest.py
a,b,n=map(int,input().split());print(a*min(b-1,n)//b)
E problem
After thinking about the C problem during the contest, I couldn't classify when n was an even number because I was doing it with an appropriate policy **. I found yuma's tweet on Twitter and was able to AC by my own method, so I started writing a commentary, but I haven't been able to explain the pattern with even n. </ font> I think I will write the continuation of the explanation soon, but please forgive me. In addition, the ones listed in the official commentary are briefly explained.
For construction problems like this, you should ** first move your hand ** (experimentally) to find the assignment of numbers to the battlefield. Then, as a result of the experiment, I thought that the following combinations would be convenient and that any combination of M and N could exist.
This combination looks good at first glance. Because, at the beginning, the participants with the number 1 move to the place with the number M in order (** you will not hit the same participant during this time ), and when the number increases to NM, go back in the reverse order ( ** You won't hit the same participant during this time **) That's fine. So, once I submitted it, all the test cases in the latter half became WA.
Personally, I feel that the policy from here was wrong. ** If you clarify the case where the previous combination does not hold **, then ** you can transform the above combination so that it still holds **. Now, let's consider the case where the above combination does not hold. Then, the following considerations can be made.
First, when the person with number 1 is A and the person with number N-M is B, When M is an even number, you must not fight B when A is number N-M or higher, as you will be fighting B by the time A becomes number M (shown in red in the figure). Also, when B is number M, A is number N, so when A is number N-M, B is number 2N-M. Therefore, when A becomes number N-M or later, it does not fight B when A is odd, and ** N is odd **. Conversely, when M is odd, you will not fight B by the time A becomes number M, so you will have to fight B when A becomes number N-M or later. Also, when A is number NM, B is number 2N-M, and when A is number NM or later, B is fighting when A is even, and ** N is odd *. It becomes *.
Therefore, the same thing can be done for any person (∵ ** only use odd numbers to determine the pattern to fight or not fight **), so when N is odd, any person can use the previous combination. It can be said that you will not play against the same participant. Therefore, I would like to consider the time when the remaining N is an even number, but from here it is the demon gate.
Too much demon gate! </ Font>
→ I'm sorry, but the explanation from here is not enough for me. It would be greatly appreciated if you could supplement it with comments or edit requests.
From here, I tried to explain the method described in Official Explanation, but I don't have time to write it, so a light explanation. End with.
As you can see from the above two patterns (the figure in Official Explanation), ** the distance of the combination of numbers ** (In the first figure, the distance is 4 for 1 and 5, 2 for 2 and 4, and so on.) You can see that they are all different. Therefore, you can arrange n numbers and take them so that they all have different distances ** ($ \ thererefore $ If this distance is different, the same participant will not play multiple times). As shown in the above figure, if you divide it in the middle and fetch it so that the distance on the left side is even and the distance on the right side is odd, you can see that you can fetch a set of numbers with different distances without waste. Also note that the maximum distance is $ [\ frac {n} {2}] $ ($ \ because $ maximum is greater than $ [\ frac {n} {2}] $ There is a possibility that the same distance will come out, and the set of numbers does not meet the subject.)
… That's a light explanation. For more information, please ask in the comments.
✳︎ It took a couple of hours to capture both Python and PyPy's shortest and fastest (as of May 03, 2020). Especially for the shortest, I think I put in some excellent code. I didn't explain the code because I was playing with it, but I think I was able to use bit operations effectively.
answerE_bymyself.py
#Code of policy that I came up with during the contest
n,m=map(int,input().split())
if n%2==1:
for i in range(m):
print(i+1,n-i)
else:
for i in range(m):
if i<m/2:
print(i+1,n-i)
else:
print(i+1,n-i-1)
answerE_editorial.py
n,m=map(int,input().split())
if n%2==1:
l=n//2
for i in range(m):
if i%2==1:
print(i//2+1,l-i//2)
else:
print(l+i//2+1,n-i//2)
else:
l=n//2
for i in range(m):
if i%2==0:
print(i//2+1,l-i//2)
else:
print(l+i//2+2,n-i//2)
answerE_shortest.py
n,m=map(int,input().split())
for i in range(m):print(i+1,n-i-((i>=m/2)&~n))
answerE_fastest.py
def main():
n,m=map(int,input().split())
if n%2==1:
x=[f"{i+1} {n-i}" for i in range(m)]
print(" ".join(x))
else:
x=[f"{i+1} {n-i}" if i<m/2 else f"{i+1} {n-i-1}" for i in range(m)]
print(" ".join(x))
if __name__ == "__main__":
main()
F problem
I have spent too much time on other issues and there is a contest today, so I will not review it once. I will review it at another time.
Recommended Posts