ABC396をPythonで（A～E）

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

A問題

問題文通りに調べる

A

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

ans = "No"
for i in range(n - 2):
    if a[i] == a[i + 1] == a[i + 2]:
        ans = "Yes"

print(ans)

B問題

スタックを利用してシミュレーションをする

B

card = [0] * 100

for _ in range(int(input())):
    query = list(map(int, input().split()))
    if query[0] == 1:
        card.append(query[1])
    else:
        c = card.pop()
        print(c)

C問題

1. 黒で価値が正のものをすべて取る
2. 白で価値が正のものを黒の個数以下で取れるだけ取る
3. 残り物のうち白と黒を同時にとって正となる組み合わせをとれるだけ取る

C

n, m = map(int, input().split())
b = sorted(map(int, input().split()))
w = sorted(map(int, input().split()))

count_diff = 0
total = 0
ans = 0
while b and b[-1] >= 0:
    b_i = b.pop()
    total += b_i
    count_diff += 1

while count_diff > 0 and w and w[-1] >= 0:
    w_i = w.pop()
    total += w_i
    count_diff -= 1

ans = total

while b and w and b[-1] + w[-1] >= 0:
    b_i = b.pop()
    w_i = w.pop()
    total += b_i + w_i
    ans = max(ans, total)

print(ans)

D問題

すべての順番を調べる

D

from itertools import permutations

n, m = map(int, input().split())
edge = [[-1] * n for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edge[u][v] = w
    edge[v][u] = w

ans = float("inf")

for p in permutations(range(1, n)):
    now = 0
    ans_i = 0
    flag = True
    for p_i in p:
        if edge[now][p_i] == -1:
            flag = False
            break
        else:
            ans_i ^= edge[now][p_i]
            now = p_i
            if now == n - 1:
                break
    if flag:
        ans = min(ans, ans_i)

print(ans)

E問題

各bit桁ごとにうまくいく組み合わせがあるか調べる

E

from collections import deque


def calc(bit, start, b, edge):
    res = dict()
    res[start] = b
    q = deque()
    q.append([start, -1, b])
    while q:
        now, old, b_i = q.popleft()
        for to, z_i in edge[now]:
            if to == old:
                continue
            if z_i >> bit & 1:
                b_j = b_i ^ 1
            else:
                b_j = b_i
            if to in res:
                if res[to] != b_j:
                    return False, res
            else:
                res[to] = b_j
                q.append([to, now, b_j])
    return True, res


n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append((y, z))
    edge[y].append((x, z))

ans = [0] * n
for i in range(31):
    ans_i = [-1] * n
    for s in range(n):
        if ans_i[s] == -1:
            flag_0, d_0 = calc(i, s, 0, edge)
            # flag_1, d_1 = calc(i, s, 1, edge)
            if flag_0:
                if sum(d_0.values()) * 2 <= len(d_0.values()):
                    for key, val in d_0.items():
                        ans_i[key] = val
                else:
                    for key, val in d_0.items():
                        ans_i[key] = val ^ 1
            else:
                exit(print(-1))

    for ind in range(n):
        ans[ind] += 2 ** i * ans_i[ind]

print(*ans)