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.
It is a question to answer whether the given 3-digit number is a number with 7.
I think it will pass no matter how you write it. Is it the cleanest to treat it as a character string and check its existence with ʻin`?
S = input()
if '7' in S:
print('Yes')
else:
print('No')
It is a question to count only the numbers that are not Fizz or Buzz up to the given number K and answer how many numbers will be added up.
I wrote it as it was and it passed. If $ O (n) $ at $ N = 10 ^ 6 $, there is no need to improve efficiency.
count = 0
n = int(input())
for i in range(1, n+1):
if i%3 and i%5:
count += i
print(count)
C - Sum of gcd of Tuples (Easy)
The question is how to add up the greatest common divisors for all three numbers below K.
Create all combinations with ʻitertools.combinations_with_replacement` to find the greatest common divisor, and add 6 times that for $ a \ neq b \ neq c $ and 3 times that for $ a \ neq b = c $. .. I tried to save the common divisor once calculated and speed it up. It doesn't look very pretty, but it's gone.
import itertools
import math
K = int(input())
g = [[0] * (K+1) for _ in range(K+1)]
out = 0
for a, b, c in itertools.combinations_with_replacement(range(1, K+1), 3):
if g[a][b] == 0:
g[a][b] = math.gcd(a, b)
d = g[a][b]
if g[d][c] == 0:
g[d][c] = math.gcd(d, c)
if a == b and b == c:
out += g[d][c]
elif a != b and b != c:
out += g[d][c] * 6
else:
out += g[d][c] * 3
print(out)
It is a question of how many combinations of three types of RGB can be made. However, the combination will be played under certain conditions.
All RGB combinations have $ R number \ times G number \ times B number $. From here, subtract the number of combinations that will catch the condition.
The exclusion condition "combination separated by a certain distance" can be obtained by turning the distance and the starting point with for for $ O (n ^ 2) $. If this index fills R, G, and B, it will be included as an exclusion target.
So I wrote the following code. I passed by this.
import itertools
N = int(input())
S = input()
out = S.count('R') * S.count('G') * S.count('B')
RGBs = list(itertools.permutations(['R', 'G', 'B'], 3))
for i in range(1, N):
for j in range(N-i*2):
if (S[j], S[j+i], S[j+i*2]) in RGBs:
out -= 1
print(out)
E - Sum of gcd of Tuples (Hard)
Again, the problem is the greatest common divisor, but the value has increased so much that the previous solution will never make it in time.
I gave up. See the commentary.
Since we do not have time to find all combinations of $ a, b, c, ... $ in finding $ \ gcd (a, b, c, ...) = X $, we satisfy a specific $ X $. Count the number of combinations of $ a, b, c, ... $.
The greatest common divisor of $ a, b, c, ... $ is $ X $, which means that "all of $ a, b, c, ... $ are divided by $ X
First, consider the condition that "all $ a, b, c, ... $ are divisible by $ X $". Of the numbers from K to 1, there are $ K \ over X $ that are multiples of X. Since only N of them are lined up, there are $ ({K \ over X}) ^ N $ combinations of $ a, b, c, ... $.
Furthermore, the condition that "all of $ a, b, c, ... $ are not broken by $ n \ times X $ (but $ n> 1 $)" is that the search for X is performed in descending order, and $ 2X, 3X , ... You can subtract the number of combinations of things that are multiples of $ in order.
Since the number of combinations that become X is obtained in this way, it can be obtained by summing the number of each combination x the value of X.
So, the implementation is as follows.
N, K = map(int, input().split())
li = [0]*(K+1)
out = 0
mod = 10**9+7
for i in range(K, 0, -1):
li[i] = pow(K//i, N, mod)
for j in range(i*2, K+1, i):
li[i] -= li[j]
out += li[i] * i
print(out%mod)
That's all for this article.
Recommended Posts