ABC404をPythonで（A～E）

AtCoder Beginner Contest 404（Promotion for Engineer Guild）の解答等の速報的まとめ

A問題

入っていない文字を１つずつ調べて、そのうち１つを出力する

A

s = input()
lst = [chr(i + ord("a")) for i in range(26) if chr(i + ord("a")) not in s]
print(lst[0])

B問題

最初に回転する回数を決めてから、違うマスが何マスあるか数える

B

def check(list_a, list_b):
    res = 0
    for a_i, b_i in zip(list_a, list_b):
        for a_ij, b_ij in zip(a_i, b_i):
            if a_ij != b_ij:
                res += 1
    return res

def turn(s):
    return list(zip(*s[::-1]))

n = int(input())
s = [list(input()) for _ in range(n)]
t = [list(input()) for _ in range(n)]

ans = check(s, t)
s = turn(s)
ans = min(ans, check(s, t) + 1)

s = turn(s)
ans = min(ans, check(s, t) + 2)

s = turn(s)
ans = min(ans, check(s, t) + 3)
print(ans)

C問題

すべての頂点に接続している辺の数が 2 かつ、1回のDFSですべての頂点に到達できれば良い

C

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

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

if n != m:
    exit(print("No"))

check = [False] * n
def dfs(now, old = -1):
    if check[now]:
        return
    check[now] = True
    for to in edge[now]:
        if to == old:
            continue
        dfs(to, now)

dfs(0)
print("Yes" if all(check) and all(len(e_i) == 2 for e_i in edge) else "No")

D問題

bit全探索を3進数で行う

D

n, m = map(int, input().split())
zoo = list(map(int, input().split()))
zoo_list = [set() for _ in range(n)]
for i in range(m):
    k, *a = map(lambda x:int(x) - 1, input().split())
    for a_i in a:
        zoo_list[a_i].add(i)

ans = float("inf")
for bit in range(3 ** n):
    lst = []
    for _ in range(n):
        lst.append(bit % 3)
        bit //= 3
    count = [0] * m
    ans_i = 0
    for i, cnt in enumerate(lst):
        if cnt:
            ans_i += zoo[i] * cnt
            for animal_i in zoo_list[i]:
                count[animal_i] += cnt
    if min(count) >= 2:
        ans = min(ans, ans_i)

print(ans)

E問題

$N-1$から降順に操作する
運べる茶碗の中にすでに豆があるときはその茶碗に入れる
豆が入っている茶碗がないときは一番遠くにおける茶碗に入れればよい

E

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

ans = 0
for i in range(n - 2, -1, -1):
    if a[i] == 0:
        continue
    ans += 1

    nxt = 0
    dist = n + 10
    flag = False
    for c_i in range(c[i]):
        if a[i - 1 - c_i] > 0:
            flag = True
        elif dist > i - 1 - c_i - c[i - 1 - c_i]:
            nxt = i - 1 - c_i
            dist = i - 1 - c_i - c[i - 1 - c_i]
    if not flag:
        a[nxt] += 1

print(ans)