AtCoder ABC161 This is a summary of the AtCoder Beginner Contest 161 questions that were held on 2020-04-04 (Sat), starting with question A and taking into consideration the considerations. The first half deals with problems up to ABC. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF
Problem statement There are three boxes $ A $, $ B $, $ C $. Each box contains one integer. Currently, the integers in the boxes $ A $, $ B $, $ C $ are $ X $, $ Y $, $ Z $, respectively. Find the integers in each of these boxes after performing the following operations in order. ・ Swap the contents of box $ A $ and box $ B $ ・ Swap the contents of box $ A $ and box $ C $
Originally, the contents of box $ A $ go into box $ B $, the contents of box C go into box $ A $, and the contents of box $ B $ go into box $ C $. Therefore, the box $ A $ contains $ Z $, the box $ B $ contains $ X $, and the box $ C $ contains $ Y $, so it is okay to output in that order.
abc161a.py
x, y, z = map(int, input().split())
print(z, x, y)
Problem statement We voted for the $ N $ type of products. Goods $ i $ are getting $ A_i $ votes. Select the popular $ M $ item from this list. However, you cannot select products that have less than $ \ frac {1} {4M} $ in total votes. Output "Yes" if you can select the popular $ M $ item, or "No" if you cannot select it.
In the explanation, the method of sorting was described first, but I thought that the second solution was simpler. It is okay if you count the products for which the number of votes obtained is $ \ frac {1} {4M} $ or more of the total number of votes, and judge whether there are more than $ M $. If it becomes WA, I think that "less than ** **" may be mistaken for the following, or whether or not "=" should be included in the conditional expression. sum (a_list) is a function that sums all the numbers in the list.
abc161b.py
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
sum_a = sum(a_list)
count = 0
for a in a_list:
if a >= sum_a / (4 * m):
count += 1
if count >= m:
print("Yes")
else:
print("No")
Problem statement Aoki can perform the following operations on any integer $ x $. Operation: Replace $ x $ with the absolute value of the difference between $ x $ and $ K $. An initial value of the integer $ N $ is given. Find the minimum value of $ N $ that can be taken when the above operation is performed $ 0 $ or more as many times as you like for this integer.
It took me some time to solve this problem. For the time being, I thought that the minimum $ N $ would be obtained if I looped according to the rules, but when I wrote the program, I couldn't solve 1000000000000000000 1 in input example 3 in 2 seconds, and I stopped a little. If you think about it carefully, if the input $ N $ is large and $ K $ is small, you will subtract many times, but for the time being, it is decided that you will do $ N $ / $ K $ times, so you can subtract that amount at once. With that in mind, the following code was completed. (Since I didn't have time to write the code in detail for the one where the subtraction result is negative, if (n --k) is negative for the time being, if the absolute value of the difference is larger than the original number, there is no need to do more, and if it is smaller, for the time being It worked if I updated the absolute value of the difference to n)
abc161c.py
n, k = map(int, input().split())
while(True):
if n - k > 0:
if n // k > 0:
n = n - k * (n // k)
else:
if n - k < n:
n = n - k
else:
break
else:
if abs(n - k) < n:
n = abs(n - k)
else:
break
print(n)
If it's a real contest, you can write the above code, but I rewrote the summary article a little more simply with reference to the explanation. The explanation is as follows.
Commentary When $ x $ is $ K $ or more, it becomes $ x-K $ by performing the operation. That is, by performing $ N / K $ operations from $ N $, the integer is the remainder of $ N $ divided by $ K $. Let $ t $ be the remainder of $ N $ divided by $ K $. If you operate on $ t $, it will be $ K−t $. If you operate on $ K−t $, it just returns to $ t $. That is, only $ t $ or $ K−t $ can be taken as a value less than $ K $. So the answer is the smaller of $ t $ and $ K-t $, that is, the remainder of $ N $ divided by $ K $ and the remainder of $ K- $ (the remainder of $ N $ divided by $ K $). The smaller one.
It's a long story in the middle, but the conclusion is simple and you can use too much to answer. If you write the code with reference to this, it will be as follows.
abc161c.py
n, k = map(int, input().split())
t = n % k
print(min(t, k - t))
I was able to write in 3 lines (laughs) It's obvious when compared to what I originally submitted. I regret not realizing that the formula for n = n --k * (n // k) that I originally wrote is n = n% k. If the explanation is only letters and difficult to understand, you can easily understand it by considering a concrete numerical example. Listing all the various patterns makes the article difficult to read, so let's take a typical example when n = 1003 and k = 5. In this case, you will first subtract 5 from 1003 200 times, and the result will be 3. This 3 is too much of 1003/5, so the program can get 3 by 1003% 5. That is, t = 3. Finally, which is smaller, t or k-t, is k --t = abs (t --k) = abs (3-5) = 2. Therefore, in 3 and 2, 2 is smaller, so the answer is 2.
This is the end of the first half. The second half will explain the DEF problem. Thank you for reading to the end of the first half for the time being. Continued in the second half.
Recommended Posts