AtCoder ARC111 個人的メモ

所感

0完

A - Simple Math 2

解説ac
https://atcoder.jp/contests/arc111/editorial/491
$10^N$の$mod$を取るって発想がでなかった

$\lfloor \frac{10^N}{M} \rfloor(mod\ M)$は整数)を求めればおｋ
この式は$0\equiv kM\ mod\ M\ (k\in \mathbb{Z})$($k$は整数)より，以下の様に変形できる

$$\lfloor \frac{10^N}{M} \rfloor \equiv\lfloor \frac{10^N}{M} \rfloor-kM \equiv\lfloor \frac{10^N-kM^2}{M} \rfloor \equiv\lfloor \frac{10^N\ mod\ M^2}{M} \rfloor \ (mod\ M)$$

計算式の$mod$の書き方間違ってるかも

N, M = map(int, input().split())

print(pow(10, N, M ** 2) // M % M)

B - Reversible Cards

解説ac
https://atcoder.jp/contests/arc111/editorial/519
大体解説の通り実装
$ans=(カードの色の種類)=(頂点数)$として，木一つにつき$ans$からデクリメントした

def dfs(n: int, parent: int):
    """木だったらtrue"""
    # 頂点nが探索済みかつ直前の頂点の親でもない→閉路
    if seen[n]:
        return False
    seen[n] = True
    res = True
    for i in G[n]:
        # 次の頂点が直前の頂点(親)と一緒なら探索不要
        if i == parent:
            continue
        res = res and dfs(i, n)
    return res


N = int(input())  # 2*10**5
color = 4 * 10 ** 5 + 1  # color<=4*10**5
G = [[] for _ in range(color)]
V = set()
for _ in range(N):
    a, b = map(int, input().split())
    V.add(a)
    V.add(b)
    G[a].append(b)
    G[b].append(a)

seen = [False] * color
ans = len(V)
for i in range(color):
    if dfs(i, 0) and G[i]:
        ans -= 1

print(ans)

他の人の提出見たらunion-find使ってたので，そっちでもacしといた

class UnionFind:
    """Union-Findアルゴリズム(素集合データ構造(disjoint-set data structure)に対しての操作)"""
    def __init__(self, n: int):
        self.root = [-1] * n
        self.edge = [0] * n

    def find(self, x: int) -> int:
        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int) -> bool:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            self.edge[x] += 1
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        self.edge[x] += self.edge[y] + 1
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> bool:
        return self.root[self.find(x)] * -1

    def num_edge(self, x: int) -> int:
        return self.edge[x]


N = int(input())  # 2*10**5
color = 4 * 10 ** 5 + 1  # color<=4*10**5
union = UnionFind(color)
for _ in range(N):
    a, b = map(int, input().split())
    union.unite(a, b)

ans = 0
for i in range(color):
    if union.root[i] < 0:
        ans += min(union.size(i), union.num_edge(i))

print(ans)