AtCoder ABC182 This is a summary of the problems of AtCoder Beginner Contest 182, which was held on 2020-11-08 (Sun), in order from problem A, taking into consideration the consideration. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary
Problem statement You have an SNS called twiblr. With twiblr, you can increase the number of followers as long as the number of followers does not exceed $ 2 × ($ followers $) + 100 $. Your current number of followers is $ A $ and your current number of followers is $ B $. How many more followers can I have?
abc182a.py
a, b = map(int, input().split())
print(2*a+100-b)
Problem statement The sequence $ A (A_1, A_2, A_3,…, A_N) $ is given. Define the GCD degree of the positive integer $ k $ as the number of $ A_1, A_2, A_3,…, A_N $ that is divisible by $ k $. Find one of the integers greater than or equal to $ 2 $ that has the greatest common divisor. If there are multiple GCD degrees, it does not matter which one is output.
GCD degree of $ p $ $ \ geq p × k $ GCD degree ($ p $ is a prime number, $ k $ is a natural number) Therefore, I implemented it with the intention of examining only prime numbers, but it was unnecessary because $ N $ was small. In addition, I wrote various conditions for exiting the loop, but this was not necessary in the contest to solve quickly.
abc182b.py
n = int(input())
a_list = list(map(int, input().split()))
sosuu_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
max_a = max(a_list)
max_count = 0
ans = 0
for i in sosuu_list:
if max_a < i:
break
count = 0
for a in a_list:
if a % i == 0:
count += 1
if count > max_count:
max_count = count
ans = i
if max_count == len(a_list):
break
print(ans)
Problem statement Each digit is given a positive integer $ N $ such that $ 0 $ does not appear. Let $ k $ be the number of digits in $ N $. I want to make a multiple of $ 3 $ by erasing $ 0 $ or more and less than $ k $ in digits of $ N $ and combining the remaining digits in the same order. Determine if you can make a multiple of $ 3 $, and if so, find the minimum number of digits to erase.
It's not a very good code, but it's just what I submitted. Carefully classify cases.
abc182c.py
n = input()
n_list = []
for i in range(len(n)):
k = int(n[i])
k = k % 3
if k == 2:
n_list.append(-1)
else:
n_list.append(k)
if sum(n_list) % 3 == 0:
print(0)
else:
t = sum(n_list) % 3
if t == 2:
p_one = n_list.count(1)
n_one = n_list.count(-1)
if n_one > 0 and len(n_list) - 1 > 0:
print(1)
elif p_one > 1 and len(n_list) - 2 > 0:
print(2)
else:
print(-1)
else:
p_one = n_list.count(1)
n_one = n_list.count(-1)
if p_one > 0 and len(n_list) - 1 > 0:
print(1)
elif n_one > 1 and len(n_list) - 2 > 0:
print(2)
else:
print(-1)
Problem statement Given the sequence $ A_1, A_2, A_3,…, A_N $. This sequence may contain negative elements. The robot located at the coordinate $ 0 $ on the number line performs the following operations in order. ・ Go forward $ A_1 $ in the positive direction. ・ Advance $ A_1 $ in the positive direction and $ A_2 $ in the positive direction. ・ Advance $ A_1 $ in the positive direction, advance $ A_2 $ in the positive direction, and advance $ A_3 $ in the positive direction. ⋮ ・ Advance $ A_1 $ in the positive direction, advance $ A_2 $ in the positive direction, advance $ A_3 $ in the positive direction, ..., advance $ A_N $ in the positive direction. Find the maximum value of the robot coordinates from the start to the end of the operation.
I feel that it was solved well. TLE was avoided by making it possible to find the time when the most positive direction can be reached in each step with a single calculation.
abc182d.py
n = int(input())
a_list = list(map(int, input().split()))
b_list = [0] * n
b_list[0] = a_list[0]
c_list = [0] * (n + 1)
c_list[1] = b_list[0]
for i in range(1, n):
b_list[i] = b_list[i - 1] + a_list[i]
c_list[i + 1] = c_list[i] + b_list[i]
max_x = 0
max_b = b_list[0]
x = 0
for i in range(n):
x = c_list[i]
if max_b < b_list[i]:
max_b = b_list[i]
x += max_b
if x > max_x:
max_x = x
print(max_x)
I was able to solve the D problem at a good pace this time as well, but I was stuck with the E problem. It's time to solve the past problems so that I can complete 5 of them.
Thank you for reading until the end.
Recommended Posts