AtCoder ABC 182 Python (A ~ D)

Summary

A, B, C solved. D is one step further. E just read the problem sentence in no time, but it was a surprisingly simple problem, so it may have been okay to solve E first.

problem

https://atcoder.jp/contests/abc182

A. twiblr

Answer

A, B = map(int, input().split())

max_follow = 2 * A + 100
answer = max_follow - B
print(answer)

Just write this.

B. Almost GCD

Answer

N = int(input())
A = list(map(int, input().split()))

max_gcd = 0
answer = 0
for i in range(2, 1000+1):
    count = 0
    for a in A:
        if a % i == 0 and a >= i:
            count += 1
    if count >= max_gcd:
        answer = i
        max_gcd = count

print(answer)

This is also basically just writing, but the implementation is a little complicated for the B problem.

C. To 3

Answer

from itertools import combinations

N = list(map(int, str(int(input()))))
k = len(N)

for i in reversed(range(1, k+1)):
    for C in combinations(N, i):
        if sum(C) % 3 == 0:
            print(k - i)
            exit()

print(-1)

For numbers that are multiples of 3, you can test whether the sum of each digit is a multiple of 3. Since you can try all the ways constrainedly, select an arbitrary number from each digit in the combination and try whether the sum can be divided by 3.

D. Wandering

Answer (2 WA)

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
cumA = np.cumsum(A)
cumA = np.append(cumA, 0)

now = 0
max_list = []
max_point = 0
max_index = 0
for i, cum_a in enumerate(cumA):
    now += cum_a
    if now >= max_point:
        max_point = now
        max_index = i
        max_list.append((max_point, max_index))

use_max_index = []
for point, index in max_list:
    if point == max_point:
        use_max_index.append(index)


answer = 0
for max_index in use_max_index:
    # max_index and max_index+Consider 1 and adopt the larger one
    # max_When using index
    answer_1 = max_point - cumA[max_index-1]
    count = 0
    add_amount = 0
    for i in range(max_index):
        count += A[i]
        add_amount = max(add_amount, count)

    answer_1 += add_amount

    # max?index+When using 1
    answer_2 = max_point
    count_2 = 0
    add_amount_2 = 0
    if max_index <= N-1:
        for i in range(max_index+1):
            count_2 += A[i]
            add_amount_2 = max(add_amount_2, count_2)

        answer_2 += add_amount_2

    answer = max(answer, answer_1, answer_2)

print(answer)

I thought too hard, the code became long, and I couldn't get two WAs.

Answer (AC at a later date)

N = int(input())
A = list(map(int, input().split()))

cumA = A[:]
for i in range(1, N):
    cumA[i] += cumA[i-1]

max_cumA = cumA[:]
for i in range(1, N):
    max_cumA[i] = max(max_cumA[i], max_cumA[i-1])

now_point = 0
max_point = 0
for i in range(N):
    max_point = max(max_point, now_point + max_cumA[i])
    now_point += cumA[i]

print(max_point)

This problem is easy without considering the constraints, but it was difficult in terms of reducing the amount of calculation. I quickly realized that the policy of reducing the amount of calculation was the cumulative sum, but I couldn't solve it because I was confused on the way.

If you think calmly,

1. Take the cumulative sum (cumA)
2. Take a list of max up to each index of the cumulative sum (max_cumA)
3. Use max_cumA to update the maximum reach (max_point)

I finally solved it cleanly. I thought that the point of this problem was to "take another idea after taking the cumulative sum".