AtCoder-ABC206 D - KAIBUNsyo【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210620230625p:plain

AtCoder Beginner Contest206のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 206（Sponsored by Panasonic） - AtCoder

AtCoder Beginner Contest206 D - KAIBUNsyo

問題文

N 項からなる正整数列 A=(A1,A2,…AN) が与えられます。
以下の操作を 0 回以上何度でも行える時、操作を最小何回行えば、A を回文にすることができますか？

ある正整数の組 (x,y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える。
なお、この問題では、全ての整数 i (1≤i≤N) について、Ai=AN+1−i が成り立つとき、またその時に限って、A が回文であると言います。

制約

・入力は全て整数
・1≤N≤2×10^5
・1≤Ai≤2×10^5

解答例

max_num = 200010
# ノードiの親がpar[i]
par = [0 for _ in range(max_num)]
# 集合の要素数
size = [1 for _ in range(max_num)]

# 初期化
def init(n):
    for i in range(max_num):
        # 初期化では自身を親とする
        par[i] = i
        # sizeは1
        size[i]= 1

# 木の根を求める
def find(x):
    # 自身が親なら自身の番号を返す
    if par[x] == x:
        return x
    else:
        # 根を張り替える
        par[x] = find(par[x])
        return par[x]

# xとyの属する集合を併合
def unite(x,y):
    root_x = find(x)
    root_y = find(y)
    # 同じグループの場合
    if root_x == root_y:
        return
    # sizeの大きいほうの根に小さいほうの根をつなぐ
    if size[root_x] < size[root_y]:
        par[root_x] = root_y
        size[root_y] += size[root_x]
    else:
        par[root_y] = root_x
        size[root_x] += size[root_y]

# xとyが同じ集団か
def same(x,y):
    return find(x) == find(y)

# 集団の要素数
def treesize(x):
    return size[find(x)]


n = int(input())

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

init(n)

# 回文のペアを併合
for i in range(-(-n//2)):
    unite(A[i], A[n-1-i])

ans = 0
# 連結成分の個数-1を足し合わせる
for i in range(max_num):
    if i == find(i):
        ans += treesize(i) - 1

print(ans)