AtCoder ABC173 This is a summary of the problems of AtCoder Beginner Contest 173, which was held on 2020-07-05 (Sun), in order from problem A, taking into consideration the consideration. The second half deals with the DE problem. Click here for the first half. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF
Problem statement You have finished the tutorial of the online game "AT Chat" and decided to visit a certain place with $ N $ players who were there. This $ N $ person is numbered from $ 1 $ to $ N $, and the friendliness of person $ i (1 \ leq i \ leq N) $ is $ A_i $. When visiting, $ N $ people arrive in any order, $ 1 $ each. To avoid getting lost, we have decided on a rule that people who have already arrived will line up in a circle, and new arrivals will interrupt and join in any position they like. Each person, except the first person to arrive, feels as comfortable as the smaller of the "clockwise closest person" and "counterclockwise closest person" friendliness when arriving from the interrupted position. I feel it. The comfort of the first person to arrive is $ 0 $. What is the maximum total comfort of $ N $ people when the order in which they arrive and the position of interruption are properly determined?
To be honest, I thought I should have thought about it properly. Somehow I found it difficult to see the problem, and I skipped it to solve the E problem to make a difference.
abc173d.py
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
ans = 0
for i in range(0, n - 1):
ans += a_list[(i + 1) // 2]
print(ans)
Problem statement $ N $ integers $ A_1,…, A_N $ are given. When selecting just $ K $ elements from this, find the maximum possible product of the selected elements. Then, divide the answer by $ (10 ^ 9 + 7) $ and output the remainder as an integer between $ 0 $ and $ 10 ^ 9 + 6 $.
I was thinking about the problem by dividing it into positive numbers, negative numbers, and 0 numbers, but for some reason I desperately wrote the cases when the result of $ K = N $ was negative and when it was positive. , It was time over. If you think about it carefully, when you use all of them, you can calculate it greedily (reflection). However, looking at the code submitted for study,
4 3
-1 -2 3 4
I wondered what was going on with "AC" that couldn't correspond to the input example like. People who are thinking about what to do in such cases end up running out of time, not thinking too much about the input, and luckily passing through the limited input in the test. If there are people who have scored, I would like you to adjust the rate later, but there is no point in asking too much for the free contest (sweat). Currently, after_contest_01.txt has been added to the check, and such code will be "WA".
abc173e.py
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
for i in range(k):
ans *= a_list[n - 1 - i]
ans %= mod
else:
l = 0
r = -1
mlt1 = a_list[0] * a_list[1]
mlt2 = a_list[-2] * a_list[-1]
count = 0
while True:
if count == k:
break
elif count == k - 1:
ans *= a_list[r] % mod
ans %= mod
break
if mlt1 >= mlt2:
ans *= mlt1 % mod
l += 2
count += 2
if l <= n - 2:
mlt1 = a_list[l + 1] * a_list[l]
else:
ans *= a_list[r] % mod
r -= 1
count += 1
if r >= - n + 1:
mlt2 = a_list[r - 1] * a_list[r]
ans %= mod
print(ans)
Thank you for reading the second half to the end.
Recommended Posts