AtCoder ABC 182 Python (A~D)

総括

A,B,C解けました。
Dはあと一歩。
Eは時間なく問題文読んだだけですが、意外と簡単な問題だったので、先にEを解いてもよかったかもしれません。

問題

A. twiblr

回答

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

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

これは書くだけ。

B. Almost GCD

回答

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)

これも基本的に書くだけですが、B問題にしては実装がやや複雑。

C. To 3

回答

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)

3の倍数の数字は各桁の和が3の倍数であるか否かを試せばよいです。
制約的に全通り試せるので、コンビネーションで各桁から任意の数を選んでその和が3で割れるかを試します。

D. Wandering

回答（WA 2つ）

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 と max_index+1 を検討して大きいほうを採用する
    # max_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+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)

難しく考えすぎ、コードが長くなり、WA２つ取り切れず。

回答（後日AC）

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)

この問題は制約を考えなければ簡単ですが、計算量を落とす点で難しかったです。
計算量をおとす方針は累積和ということはすぐにわかったのですが、途中でこんがらがって解けず・・・。

落ち着いて考えてみると、
1. 累積和をとる(cumA)
2. 累積和の各indexまでのmaxのリストをとる(max_cumA)
3. max_cumAを使って最大到達地点(max_point)を更新していく

とう方針できれいに解けました。
「累積和をとったあとに、もう一工夫する」というところがこの問題のポイントだったと思いました。