Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

AtCoder ABC 182 Python (A~D)

総括

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

問題

https://atcoder.jp/contests/abc182

A. twiblr

image.png

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

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

これは書くだけ。

B. Almost GCD

image.png

回答
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

image.png

回答
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

image.png

回答(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)

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

回答(後日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)を更新していく

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

K_SIO
プログラミング初心者Pythonを学ぶ(2020/4~) コロナで在宅勤務が増えたことから(!)プログラミングを始めました。 学習記録として記事を残します。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away