AtCoderBeginnerContest182 Review & Summary

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 A twiblr

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 B Almost GCD

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)

C problem To 3

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)

D problem Wandering

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

AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest161 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest168 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (first half)
samba summary
Django Summary
python-pptx summary
Linux Summary
Python summary
Django Summary
pyenv summary
String summary 1
pytest summary
matplotlib summary
Function review