AtCoder Beginner Contest 120をPythonで解く

A - Favorite Sound（100点）

満足する回数Cを無視すると、答えは(B//A)
この数よりCが小さければ、答えはC

A, B, C = list(map(int, input().split()))

ans = min((B//A), C)
print(ans)

B - K-th Common Divisor（200点）

K番目に「大きい」ことに注意

A, B, K = list(map(int, input().split()))

ans = []
for i in range(1, min(A, B) + 1):
    if (A%i==0) and (B%i==0):
        ans.append(i)

print(ans[-K])

C - Unification（300点）

少し考えると0と1が可能な限り打ち消し合うと分かる

S = input()

num_0 = S.count('0')
num_1 = S.count('1')

print(min(num_0, num_1)*2)

D - Decayed Bridges（400点）

Union Find Treeの拡張

class UnionFindTree():
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
        self.hubensa = N*(N-1)//2
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.hubensa -= self.size[px] * self.size[py]
            self.size[px] += self.size[py]

N, M = list(map(int, input().split()))
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]

for i in range(M):
    A[i], B[i] = list(map(int, input().split()))

ans = []
UFT = UnionFindTree(N)

# 後ろから処理
for i in range(M-1, -1, -1):
    ans.append(UFT.hubensa)
    UFT.unite(A[i], B[i])

print(*ans[::-1], sep="\n")