AtCoder ABC399 振り返り

前回のABC398は用事により未チャレンジだったので、今回は2回ぶりのRating参加です。

結果は3問解答でした。あまりレーティングは気にしていないとはいえ、そろそろ緑陥落が見えてきてしまいました。

2週間間隔が空いたこと、水曜日あたりひどい胃腸炎になってしまい、体調が戻っていないことが敗因です（言い訳）。398は受けなかったなら受けなかったで、復習しておけばよかったなあ...。

C問題で解法をすぐに思いつかず、時間がかかってしまった & 1ペナしてしまったのも良くなかった。D問題は解けそうなんですけど、頭が働かずだめでした。

A - Hamming Distance

全探索して、文字が異なるものをカウントしました。

N = int(input())
S = input()
T = input()

count = 0
for i in range(N):
    if S[i] == T[i]:
        continue
    else:
        # 異なる文字をカウント
        count += 1
print(count)

B - Ranking with Ties

解き方を悩んだんですが、入力数列を逆順でソートしまして...

[3 12 9 9]
↓
[12 9 9 3]

「その数値が最初に現れる位置」が順位になります。
上の例なら 12 → 1番、9 → 2番、3 → 4番

N = int(input())
P = list(map(int, input().split()))
sorted_p = sorted(P, reverse=True) # 逆順にソート

answers = []
for i in range(N):
    r = sorted_p.index(P[i]) # 逆順ソートの配列の中で、indexを求める
    print(r + 1)

C - Make it Forest

1ペナでした。最初は幅優先探索で解くのかなと思ってやってたんですが、それだは答えが出ません...(これで1ペナ)。

「よくわかんないなー」と思って、鉄則本を見ていたら「最小全域木問題」のところで、解き方を思い出しました。この問題は、すべての辺の重みが1の最小全域木問題ですね...。

というわけで、Union-Find を使用して解きました。


# UnionFindは https://qiita.com/sano192/items/027d672129ac4cb42aa2#e---graph-destruction より
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
    def size(self,a):
        return abs(self.parent_size[self.leader(a)])
    def groups(self):
        result=[[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

# 読み込み
N, M = map(int, input().split())
paths = defaultdict(list)
uv = []
for i in range(M):
    u, v = map(int, input().split())
    paths[u].append(v)
    paths[v].append(u)
    uv.append((u, v))

unionfind = UnionFind(N + 1)

count = 0 # 使用した辺の数をカウント
for path in uv:
    u, v = path

    # 既に連結されている場合はスキップ
    if unionfind.same(u, v):
        continue
    
    # 未連結の場合は、その辺を使用し連結する
    unionfind.merge(u, v)
    count += 1

print(M - count) # すべての辺の数 - 使用した辺の数