ABC350をPythonで（A～E）

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）の解答等のまとめ

A問題

$ABC001$から$ABC349$までのいずれかで一致するか調べる

A

s = input()
for i in range(1, 350):
    if i == 316: continue
    a = "ABC"
    b = "00" + str(i)
    if s == a + b[-3:]:
        exit(print("Yes"))

print("No")

B問題

それぞれの歯にflagを与えて生えているか切り替えていけばいい

B

n, q = map(int, input().split())
t = list(map(lambda x: int(x) - 1, input().split()))

lst = [True] * n
for t_i in t:
    lst[t_i] ^= True

print(sum(lst))

C問題

$1$から$n-1$まで順に正しい位置に戻したら、$n$を操作せずとも正しい位置にもどる
よって、$1$から$n-1$まで正しい位置に来るように入れ替えていけば$n-1$回までに昇順になる

C

n = int(input())
a = [0] + list(map(int, input().split()))

b = [0] * (n + 1)
for i, a_i in enumerate(a):
    b[a_i] = i

ans = []
x = [i for i in range(n + 1)]
for i in range(1, n + 1):
    if a[i] == x[i]:
        continue
    a_i, b_i = a[i], b[i]
    ans.append([i, b_i])
    a[i], a[b_i] = a[b_i], a[i]
    b[a[b_i]] = b_i
    # print(a)
    # print(b)

print(len(ans))
for a_i in ans:
    print(*a_i)

D問題

問題文に最大の回数とあるが、この答えはできるものから順に行えばどの順番だろうと同じ回数できる
なぜなら自身と無関係の辺が増えてもつながっていない頂点との距離は１になることはないから

よって、同じグループかつ隣接していない組み合わせの和がこの問題の答えになる

D

from collections import defaultdict


class UnionFind:
    """
    URL : https://note.nkmk.me/python-union-find/
    """

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())


n, m = map(int, input().split())
data = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
data.sort()
UF = UnionFind(n)
edge = [set() for _ in range(n)]
for a, b in data:
    edge[a].add(b)
    edge[b].add(a)
    UF.union(a, b)

ans = 0
for group in UF.all_group_members().values():
    ans_i = 0
    group_count = len(group)
    for g_i in group:
        ans_i += group_count - len(edge[g_i]) - 1
    ans += ans_i // 2

print(ans)

E問題

dfsで求める$O(\sqrt{n})$

yの時の期待値はなんとなくの調整でうまくいった。理論的に正しいかはわかってない

E

from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n, a, x, y = map(int, input().split())
d = {0: 0}


def dfs(N):
    if N not in d:
        x_n = dfs(N // a)
        y_n = (dfs(N // 2) + dfs(N // 3) + dfs(N // 4) + dfs(N // 5) + dfs(N // 6) + y) / 5
        d[N] = min(x + x_n, y + y_n)
    return d[N]


print(dfs(n))