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 - Beginner On a certain competition pro site, it seems that the rating of people with a small number of times is displayed higher than the internal rating. The actual internal rating is a question that answers some.
If the number of times N is 10 or more, output as it is. If it is less than 10, the value obtained by adding the correction value $ 100 \ times (10-N) $ will be the internal rating.
N, R = map(int, input().split())
if N < 10:
print(R + 100 * (10-N))
else:
print(R)
B - Digits It is a question to answer how many digits will be when the numerical value N is expressed in K notation.
Think about where the largest digit will be. For example, if $ N = 9, K = 2 $, $ 1000 $, which is $ 2 ^ 3 $, will be the largest digit, and $ r = 4 $ will be obtained. To put this in a mathematical formula, we can find the multiplier r that satisfies the following.
I simply implemented this.
N, K = map(int, input().split())
r = 1
while not(K**(r-1) <= N and N < K ** r):
r += 1
print(r)
This passed without any problems, but when I looked at the explanation, the method was different.
The number of digits to be calculated is $ D $, and the value of each digit is $ a_ {D-1}, \ cdots, a_1, a_0
It is expressed by the formula.
If you repeat the operation of dividing $ N $ by $ K $ and taking the quotient, the quotient will be $ 0 $ when $ D $ is divided by $ K $.
Let's implement this.
N, K = map(int, input().split())
D = 0
while N:
N //= K
D += 1
print(D)
There was no problem with the calculation time.
C - Rally
The question is where to find the point (integer value) where the square error is the smallest for those placed on the number line.
The least squares method is associated with the problem statement, but both N and X have a narrow range of 1 to 100. I decided that I didn't need any mathematical skills because $ O (N ^ 2) $ passed without any problem, so I simply searched all over.
N = int(input())
X = list(map(int, input().split()))
minLoss = 1e6
for i in range(1, 101):
minLoss = min(minLoss, sum([(x - i)**2 for x in X]))
print(minLoss)
I passed by this.
I think it would be a little more efficient if the left and right ranges were set to the minimum and maximum values of X instead of 1 to 100.
D - Bouquet How many combinations can be taken from N different flowers? However, a and b cannot be taken out. Is the problem.
TLE because I tried to find a combination with $ _nC_r $ for each number n from 1 to N. I gave up.
I saw the commentary. "All combinations for all numbers" is much easier to calculate.
There are only two options for each flower, "use" and "not use". So all combinations are $ 2 ^ N $. However, the combination that uses 0 is excluded, so it is exactly $ 2 ^ N-1 $.
It can be obtained by subtracting the combinations that should be excluded from $ _nC_r $ for a and b.
from scipy.misc import comb
m = 1000000007
n, a, b = map(int, input().split())
out = 2**n - comb(n, a) - comb(n, b)
print(out%m)
This was no good. The problem is that 2 ** n, $ _nC_a, and _nC_b $ are ridiculous numbers.
To get rid of this It is necessary to reduce the calculation by a mathematical method using the condition "remainder divided by $ 10 ^ 9 + 7 $".
First, consider the multiplier of 2. In python, you can use pow () instead of ** to specify the number to divide by the third argument, and you can perform modulo calculation at high speed.
print(pow(2, 4, 3)) # 1
Next, consider speeding up the combination calculation.
There is Fermat's Little Theorem. When $ p $ is prime and $ a $ and $ p $ are relatively prime
Is established. In other words, dividing a by p-1 to the power of p gives 1. It seems. I did not know.
I didn't really feel it, so I'll give it a try.
p = 29
for a in range(3, 29, 5):
print("a: {}, p: {}, a^(p-1)%p: {}".format(a, p, pow(a, p-1, p)))
'''
a: 3, p: 29, a^(p-1)%p: 1
a: 8, p: 29, a^(p-1)%p: 1
a: 13, p: 29, a^(p-1)%p: 1
a: 18, p: 29, a^(p-1)%p: 1
a: 23, p: 29, a^(p-1)%p: 1
a: 28, p: 29, a^(p-1)%p: 1
'''
It's true. Hmm. The proof is not mentioned here.
Return the story. Under this condition, $ 10 ^ 9 + 7 $ and Y are always relatively prime, so the following equation holds.
Divide both sides by Y
pow () as before. The term that appears in the combination calculation is separated into the denominator X and the numerator Y, and Y is subjected to this process.
m = 1000000007
n, a, b = map(int, input().split())
def comb(n, r, m):
X, Y = 1, 1
for i in range(r):
X *= n-i
Y *= i+1
X %= m
Y %= m
return int(X * pow(Y, m-2, m))
out = pow(2, n, m) - 1 - comb(n, a, m) - comb(n, b, m)
print(out%m)
I passed by this.
E - Roaming If a person in each of n rooms moves k times, how many room conditions can be? Is the problem.
I couldn't imagine how to solve it, so I gave up.
I saw the commentary.
First, consider a combination of rooms with 0 people. Suppose $ m $ of rooms are empty. Then, the combination of selecting m rooms from all n rooms
It can be found by.
From there, consider the combination of rooms that the original m-room resident has moved to. There are many ways of thinking, but the simplest way is to divide the $ m $ inhabitants by $ n-m-1 $ walls. If the resident is 〇 and the wall is |, it can be changed to the problem of thinking about the combination of patterns for arranging character strings.
〇〇|〇|〇〇 You can make a combination like this.
This arrangement is
Can be calculated with.
Applying this calculation to this situation gives the following formula.
Therefore, the combination of $ _nC_m \ times _ {n-1} C _ {m} $ when there are no $ m $ rooms can be obtained. You can add up by changing this $ m $ from 0 to $ k $ (or $ n-1 $).
In addition, the calculation result of the combination can be used for the next combination calculation.
So it is an implementation example. I write while looking at the code of almost other people.
n, k = map(int, input().split())
c1 = 1
c2 = 1
mod = 10**9+7
ans = 0
for i in range(min(n, k+1)):
ans += c1 * c2
c1 *= (n-i) * pow(i+1, mod-2, mod)
c1 %= mod
c2 *= (n-i-1) * pow(i+1, mod-2, mod)
c2 %= mod
print(ans%mod)
This is the end of this article.
Recommended Posts