ABC448をPythonで

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

A問題

問題文通りシミュレーション

A

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

for a_i in a:
    if a_i < x:
        print(1)
        x = a_i
    else:
        print(0)

B問題

順番に使えるだけ使う

B

n, m = map(int, input().split())
c = list(map(int, input().split()))
ans = 0
for _ in range(n):
    a, b = map(int, input().split())
    use = min(c[a - 1], b)
    ans += use
    c[a - 1] -= use

print(ans)

C問題

SortedListを使って問題文通りのシミュレーションをする

C

from sortedcontainers import SortedList


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

s = SortedList(a)
for _ in range(q):
    k = int(input())
    b = list(map(lambda x:int(x) - 1, input().split()))
    for b_i in b:
        s.discard(a[b_i])
    print(s[0])
    for b_i in b:
        s.add(a[b_i])

D問題

dfsで上から確認

D

import sys;sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
edge = [list() for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)
    edge[v - 1].append(u - 1)

check = [False] * n
d = dict()
ans = [False] * n

def dfs(now, flg):
    global check, d, ans
    if a[now] not in d:
        d[a[now]] = 0
    if flg or d[a[now]] > 0:
        ans[now] = True
        flg = True
    d[a[now]] += 1
    check[now] = True
    for to in edge[now]:
        if check[to]:
            continue
        dfs(to, flg)
    d[a[now]] -= 1

dfs(0, False)

for ans_i in ans:
    print("Yes" if ans_i else "No")