AtCoder ABC169 This is a summary of the AtCoder Beginner Contest 169 problems that took place on 2020-05-31 (Sun), starting with problem A and taking into account the considerations. 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 A positive integer $ N $ is given. Consider repeating the following operation for $ N $. ・ First, select a positive integer $ z $ that satisfies all of the following conditions. ◦ Can be expressed as $ z = p ^ e $ using a prime number $ p $ and a positive integer $ e $ ◦ $ N $ is divisible by $ z $ ◦ Different from any integer selected in the previous operation ・ Replace $ N $ with $ N / z $ Find out how many times you can perform the operation.
I realized that this problem could be easily solved by factoring the prime factors for the time being, so I searched for articles that I have always been indebted to and copied the code for the factorization part.
High-speed prime factorization with Python-for competition professionals-
The problem this time is that if you have $ k $ of a certain prime factor $ p_1 $, you have to think about how many operations you can perform, but the number of operations → the number of required prime factors $ p_1 $ Is
abc169d.py
def factorization(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
n = int(input())
if n == 1:
print(0)
else:
x_list = factorization(n)
ans = 0
for x in x_list:
n = 2
while True:
if x[1] < (n * n + n) // 2:
ans += n - 1
break
n += 1
print(ans)
You have to be careful only when the input is $ 1 $.
Problem statement There are $ N $ integers $ X_1, X_2, ⋯, X_N $, which we know are $ A_i \ leq X_i \ leq B_i $. Find out how many possible median values for $ X_1, X_2, ⋯, X_N $.
I was too busy with the B and C problems, but I quickly realized that I could sort $ A $ and $ B $ separately and use their median to solve them. Write the code until the number of data is odd and time up.
Regarding the problem, first sort $ A_1, A_2, ..., A_N $, and the resulting sequence is $ C_1, C_2, ..., C_N $, and $ B_1, B_2, ..., B_N $ are sorted. As a result, the obtained sequence is $ D_1, D_2, ..., D_N $.
The answer is $ D_ {(N + 1) / 2} --C_ {(N + 1) / 2} + 1 $.
The answer is $ D_ {N / 2} --C_ {N / 2} + D_ {N / 2 + 1} --C_ {N / 2 + 1} + 1 $. For example, if $ C_ {N / 2} = 5, C_ {N / 2 + 1} = 7, D_ {N / 2} = 7, D_ {N / 2 + 1} = 9 $, the possible combinations are ，
| 5 | 6 | 7 | |
|---|---|---|---|
| 7 | 6 | 13/2 | 7 |
| 8 | 13/2 | 7 | 15/2 |
| 9 | 7 | 15/2 | 8 |
The answer is $ 6,13 / 2,7,15 / 2,8 $, which is $ 5 $. Since this answer is the number of rows + the number of columns of the table -1, the same answer can be obtained by the above formula.
abc169e.py
n = int(input())
a_list = []
b_list = []
for i in range(0, n):
a, b = map(int, input().split())
a_list.append(a)
b_list.append(b)
a_list.sort()
b_list.sort()
if n % 2 == 0:
x1 = n // 2 - 1
x2 = n // 2
print(b_list[x2] - a_list[x2] + b_list[x1] - a_list[x1] + 1)
else:
x = n // 2
print(b_list[x] - a_list[x] + 1)
If the question set from A to C is the usual difficulty level, I think I could have completed 5, but I feel lack of study. By the time I got a job, I started thinking that I should improve my programming skills as much as possible, so I feel that it suits my purpose, so I would like to continue participating (I can not pass the B and C problems, If the rate dropped, I would have to keep a distance). I am busy this week with the F problem, so I hope I can add it even when I have time.
Thank you for reading the second half to the end.
Recommended Posts