Review of AtCoder Beginner Contest 163, up to question E (Python)
This is a review article for beginners of competition professionals.
The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
A - Circle Pond It is a problem to output the circumference of radius R.
Circumference c with respect to radius r
It can be found by.
import math
R = int(input())
print(2 * math.pi * R)
Since the error tolerance is large, it seems that it is not necessary to read the pi in such a manner.
$ \ boldsymbol {A} $ days It is a question of how many days of summer vacation will remain if you do the necessary summer vacation homework.
(Number of days of summer vacation)-If (total array) is negative-1, output as it is otherwise. If you use max (), you don't need to use an if statement.
N, M = map(int, input().split())
A = list(map(int, input().split()))
print(max(N - sum(A), -1))
You will be given the information "Employee with employee number $ i $, who has employee number $ A_i $ as his boss". It is a question of how many subordinates each staff member has.
It took the most time to understand the problem statement. In short, you are asked about the distribution of numbers.
I counted the distribution of numbers using collections.Counter.
import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)
for n in range(N):
print(count[n+1])
It is a question to answer the number of possible sums among all combinations that take $ K $ or more out of $ N + 1 $ numbers. However, since each number is in the form of $ 10 ^ {100} + i $, the sum of $ M $ and the sum of $ M + 1 $ will never match.
I do not have a clue. Isn't it possible to formulate the number of sums? I tried to calculate what kind of distribution the "combination of sums when $ M $ is taken from the numbers from 1 to 9" would be. It shows the distribution of the sum when the output on the $ m $ line takes $ m $.
Actually I gave up here. However, if you look at this now, you will get an important hint.
Looking at this output, it is speculated that there is no missing number between the minimum and maximum values of the sum of combinations. Then, if you calculate the "minimum value of the sum" and the "maximum value of the sum" respectively, you can find the number of combination sums when $ M $ is taken.
The minimum value when taking $ M $ is "total of the numbers up to the $ M $", and the maximum is "total of the numbers from $ N-M + 1 $". The rest is the number of combinations that can have a difference of +1.
N, K = map(int, input().split())
mod = 10**9 + 7
count = 0
for n in range(K, N+2):
maxSum = (n*(N + N-n+1))//2
minSum = (n*(n-1))//2
count += maxSum - minSum + 1
count %= mod
print(count)
I passed by this. I knew this without looking at the commentary, so I wanted to solve it during the contest. E - Active Infants
Given the coefficient $ A_i $ for each infant that exists at position $ i $, the problem is to find the maximum value of the distance that the infant moves around x the coefficient.
I don't understand at all. I submitted a brute force answer (TLE) and gave up.
TLE guy.py
import itertools
N = int(input())
A = list(map(int, input().split()))
ureshisa = [
[A[i] * abs(i-j) for j in range(N)] for i in range(N)
]
maxV = 0
for P in itertools.permutations(list(range(N))):
maxV = max(maxV, sum([ureshisa[P[i]][i] for i in range(N)]))
print(maxV)
I didn't understand even if I looked at the explanation, so I will refer to other answers. The following code is taken from this answer as it is.
Quote.py
# E - Active Infants
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n
#List of subscripts
p = list(range(n))
p.sort(key=lambda i: a[i])
# dp[j] =Maximum happiness when i are placed in the section from position j to width i from the smallest
dp = [0] * (n + 1)
for i in range(n):
for j in range(n - i):
dp[j] = max(dp[j] + a[p[i]] * abs(p[i] - (j + i)),
dp[j + 1] + a[p[i]] * abs(p[i] - j))
print(dp[0])
I don't know, so I'll follow the process
Let's follow in order what happens when the array [1, 3, 4, 2] is given.
First, consider the placement of an infant with $ i = 0 $ (hereinafter referred to as $ a_0 $) whose minimum value is $ A_i $.
The joy of placing $ a_0 $ at each of the 0, 1, 2, and 3 positions is calculated to be 0, 1, 2, 3.
Save this value as an array dp. The array dp when one infant $ a_0 $ is placed from the bottom is as follows.
Next, place the infant $ a_3 $ with $ i = 3 $, where $ A_i $ is the second smallest value. However, consider only the state of "place one behind $ a_0 $" and "push $ a_0 $ one behind".
First, when $ a_0 $ is placed at $ i = 0 $, "Leave $ a_0 $ and place $ a_3 $ at $ i = 1 $" "Set $ a_0 $ to $ i = 1 $" Push it away and place $ a_3 $ at $ i = 0 $ ". The joy was calculated to be 4 and 7, respectively. Leave only the larger value and set dp [0] = 7.
If this is calculated in the same way, when the placement of $ a_0 $ is $ i = 1, 2 $, 6 and 5 are the maximum, respectively. (The value of dp [3] was absorbed here)
So, the two infants with the lowest coefficient ($ a_) When arranging {03} $) side by side
Is the maximum value corresponding to each position.
Next, consider the placement of the infant $ a_1 $ with the third coefficient from the bottom, $ i = 1 $.
Calculate "place two toddlers in a row behind $ a_ {03} $" and "place two toddlers in a row behind $ a_ {03} $" respectively.
It was calculated in the same way as before, and when the three infants (called $ a_ {031} $) from the bottom were placed side by side, it was obtained as follows.
Finally, do the same for the infant $ a_2 $ with the largest coefficient $ A_i $.
When $ a_ {031} $ is placed at $ i = 0 $ and $ a_2 $ is placed at $ i = 3 $, $ 14 $ is placed, and $ a_ {031} $ is placed at $ i = 1 $. $ 20 $ when a_2 $ is placed at $ i = 0 $. Take the larger one.
Now you have the answer.
I'm not catching up with my understanding ... In order to go with this idea, do we need to come to the idea that "the infant with the Mth coefficient from the bottom is always adjacent to the" row of infants from 1st to M-1st "? Intuitively, I don't feel like that, but I'm not sure if I can prove it.
According to the way of thinking of the commentator, the left or right wall is filled in order from the infant with the highest coefficient. In short, it seems that you are doing the same thing in reverse order.
That's all for this article.
reference
https://atcoder.jp/contests/abc163/submissions/12150591 Question E quoted this.
Recommended Posts