ABC206 D – KAIBUNsyo｜かえるのほんだな

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC206 D – KAIBUNsyoを解きました。

ある操作を繰り返して回文を作る。

難易度は緑色。

考察

2つの数を選び、数列内の片方の数をすべてもう片方に置き換える操作を繰り返して回文を作る。

この問題を解くために、なぜかUnion-findが思い浮かぶ人がいるらしい。

Union-findとは、2つの要素が同じグループに属するかを調べ、属する場合は、それらのグループを効率的に併合していくアルゴリズム。

今回回文を作るためには、数列のi番目とN-i番目の数が最終的に一致している必要がある。

つまり、数列のi番目とN-i番目の数が最終的に同じ値になるペアの関係になるので、ペアの数だけUnion-findアルゴリズムによって評価し、併合していけばよい、らしい…。

結局Union-findでの解法がいまいち理解できず、互いに連結しているペアのグループ数をBFSで求め、全体の数字の数から引く方法で解いた。

コード

from collections import deque
NULL = -1

N = int(input())
A = list(map(int,input().split()))


T = [[] for i in range(2 * pow(10, 5) + 1)]
for i in range(N//2):
    if A[i] != A[N-1-i]:
        T[A[i]].append(A[N-1-i])
        T[A[N-1-i]].append(A[i])

def bfs():
    que = deque([])
    dist = [NULL]*(2 * pow(10, 5) + 1)
    coutner = 0
    m = 0
    for i in range(2 * pow(10, 5) + 1):
        if len(T[i]) > 0:
            if dist[i] == NULL:
                m += 1
                dist[i] = coutner
                coutner += 1
                que.append(i)

            while que:
                pos = que.popleft()
                for v in T[pos]:
                    if dist[v] != NULL:
                        continue
                    dist[v] = coutner
                    coutner += 1
                    que.append(v)
                    # print(v)

    return m

ans = 0
m = bfs()
c = 0
for t in T:
    if len(t) > 0:
        c += 1
print(c - m)