ABC473のPython解答（Ａ～Ｅ）

AtCoder Beginner Contest 473の解答等の速報的まとめ

A問題

そのまま

A

n = int(input())
a = list(map(int, input().split()))

print(sum(a[n // 2:]))

B問題

ソートしてババ抜き

B

n = int(input())
a = list(map(int, input().split()))

a.sort()
lst = list()
for a_i in a:
    if lst and lst[-1] == a_i:
        lst.pop()
    else:
        lst.append(a_i)

print(sum(lst))

C問題

個数を数えて、最大値$-1$以上となるものの数が答え

C

n, k = map(int, input().split())
a = map(lambda x:int(x) - 1, input().split())

lst = [0] * k

for a_i in a:
    lst[a_i] += 1

maxi = max(lst)
print(len([l_i for l_i in lst if maxi - l_i <= 1]))

D問題

再起で導出
PyPyだと遅いのでCodonで出す

D(Codon)

n, k = list(map(int, input().split()))

def dfs(lst, sums):
    ind = len(lst)
    if ind == n:
        if (k - sums) % ind == 0:
            for l_i in lst[1:]:
                print(l_i, end=" ")
            print((k - sums) // ind)

    else:
        i = 0
        while i * ind + sums <= k:
            new_lst = lst.copy()
            new_lst.append(i)
            dfs(new_lst, sums + i * ind)
            i += 1

dfs([0], 0)

E問題

$dp[i] = i$番目までのスコアの最大値

• $dp[i-1]$
• 端からの合計$modK$が一致するマスの$dp$値の中で最大値

端からの合計$modK$ごとの$dp$の最大値をメモするとうまくいく

E

n, k = map(int, input().split())
a = list(map(int, input().split()))

d = {0:0}
dp = [0]
sums = [0]
for a_i in a:
    target = (sums[-1] + a_i) % k
    sums.append(target)
    dp.append(dp[-1])
    if target in d:
        dp[-1] = max(dp[-1], d[target] + 1)
    d[target] = dp[-1]

print(max(dp))