ABC368をPythonで（A～D,F）

日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）の解答等の速報的まとめ

A問題

後ろから$K$枚を前にする

A

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

b = a[n - k:] + a[:n - k]
print(*b)

B問題

実際にシミュレーションをする。
操作回数は$N=100,A$全部100の時の5000回が最大のため間に合う

B

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

cnt = 0
while a.count(0) < n - 1:
    a.sort(reverse=True)
    a[0] -= 1
    a[1] -= 1
    cnt += 1

print(cnt)

C問題

基本３回で５減らすループなのでその計算をして$H$を大きく減らす
端数部分は実際にシミュレーションをする

C

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

t = 0
for h_i in h:
    while t % 3 != 0 and h_i > 0:
        t += 1
        if t % 3 == 0:
            h_i -= 3
        else:
            h_i -= 1

    if h_i > 0:
        x = h_i // 5
        t += x * 3
        h_i %= 5

    while h_i > 0:
        t += 1
        if t % 3 == 0:
            h_i -= 3
        else:
            h_i -= 1

print(t)

D問題

葉から$V$の対象外かを確認していく

D

n, k = map(int, input().split())
edge = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(lambda x:int(x) - 1, input().split())
    edge[a].add(b)
    edge[b].add(a)

v = set(map(lambda x:int(x) - 1, input().split()))

mono = list()
for i in range(n):
    if len(edge[i]) == 1:
        mono.append(i)

ans = n
for now in mono:
    if now not in v:
        to = edge[now].pop()
        edge[to].discard(now)
        if len(edge[to]) == 1:
            mono.append(to)
        ans -= 1

print(ans)

F問題

Grundy数
約数関係はエラトステネスの篩の要領で値を渡して、そのあとmexを求めた

F

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

p = [0, 0]
s = [{0} for _ in range(10 ** 5 + 10)]
for i in range(2, 10 ** 5 + 1):
    t = 1
    while t in s[i]:
        t += 1
    p.append(t)
    for j in range(i + i, len(s), i):
        s[j].add(t)

grundy = 0
for a_i in a:
    grundy ^= p[a_i]

print("Anna" if grundy else "Bruno")