AtCoder ABC 120の反省 - もうカツ丼はいいよな

やったので回答とメモを残しておく。

A - Faborite Sound

特に注意すべき点はない。

# coding: utf-8
 
a, b, c = [int(i) for i in input().split()]
 
print(min(b // a, c))

B - K-th Common Divisor

$B$の範囲がそれほど広くなかったので、bruteforceで解いてしまった。最初「大きい方から」というのを忘れていて一回ミスってしまった。

提出時は内包表記使ってなかった。慣れておきたい。

# coding: utf-8
 
a, b, k = [int(i) for i in input().split()]
 
divs = [i for i in range(1, a+1) if a % i ==0 and b % i == 0]
 
print(divs[-k])

C - Unification

列の中に異なる色がある限り必ず消滅するので、最後には0の数と1の数の差だけブロックが残る、という点に気づけば簡単。

# coding: utf-8
 
S = list(input())
 
n1 = sum(s == "1" for s in S)
n0 = sum(s == "0" for s in S)
 
print(len(S) - abs(n1 - n0))

D - Decayed Bridges

（ひっくり返せば行けそう…）とまでは気付いたものの時間内には手も足も出なかった。

Union-Find木というものを使う基本的な問題らしく、アリ本（プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?）ではp81に説明がある（もう少しちゃんと読んでおけばよかった）。

Union-Findの実装はPython:Union-Find木について - あっとのTECH LOGを参考に、グループ数をメモるように少し手を加えた。

# coding: utf-8
 
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1) # 木の高さ
        self.n = [1] * (n+1)    # グループメンバー数
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def find_n(self, x):
        return self.n[self.find(x)]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.n[y] = self.n[x] + self.n[y]
        else:
            self.par[y] = x
            self.n[x] = self.n[x] + self.n[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
# -------------------------------------------------------------------

N, M = [int(i) for i in input().split()]

bridges = [tuple(int(i) for i in input().split()) for j in range(M)]

bridges = bridges[::-1]

result = []

now = int(N * (N-1) / 2) #最終不便さ

uf = UnionFind(N)

for i in range(M):
    result.append(now)
    a = bridges[i][0]
    b = bridges[i][1]
    if uf.is_same(a, b): # 既に同じグループ
        pass
    else:
        now -= uf.find_n(a) * uf.find_n(b)
        uf.union(uf.find(a), uf.find(b))

result = result[::-1]

for i in result:
    print(i)