Atcoder解いてみた AtCoder Beginner Contest D - KAIBUNsyo

AtCoder Beginner Contest D - KAIBUNsyo

問題はこちら

回答

A[i]の同じ値は運命共同体で連結しているとみなせる
事前に同じ値どうしでグルーピングしておき、その後、A[i], A[N-1-i]を比べた時に、異なるグループだったら同じグループにまとめ、その回数をカウントすればいい

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>


int N;
std::vector<int> A;

class UnionFind {
private:
	std::vector<int> parent;
	std::vector<int> rank;

public:
	UnionFind(const int n) {
		parent.resize(n);
		rank.resize(n);

		for (int i = 0; i < N; i++) {
			parent[i] = i;
			rank[i] = 1;
		}
	}

	int GetRoot(int val) {
		if (val == parent[val]) {
			return val;
		}
		else {
			parent[val] = GetRoot(parent[val]);
			return parent[val];
		}
	}

	bool IsSame(int val1, int val2) {
		return GetRoot(val1) == GetRoot(val2);
	}

	void Merge(int val1, int val2) {
		int root1 = GetRoot(val1);
		int root2 = GetRoot(val2);

		if (root1 == root2) {
			return;
		}

		if (rank[root1] > rank[root2]) {
			parent[root2] = root1;
		}
		else {
			parent[root1] = root2;
			if (rank[root1] == rank[root2]) {
				rank[root2]++;
			}
		}
	}
};

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;
	A.resize(N);

	UnionFind uf(N);
	std::unordered_map<int, std::vector<int>> ump;

	for (int i = 0; i < N; i++) {
		std::cin >> A[i];
		ump[A[i]].push_back(i);
	}

	// A[i]が同じな場合、グループを作る
	for (const auto& [val, vec] : ump) {
		int s = vec[0];
		
		for (int i = 1; i < vec.size(); i++) {
			uf.Merge(s, vec[i]);
		}
	}

	int pNum = N / 2;
	int ans = 0;
	for (int i = 0; i < pNum; i++) {
		int revI = N - 1 - i;

		// 根が違う場合、グルーピングしていく
		if (uf.IsSame(i, revI)) {
			continue;
		}

		uf.Merge(i, revI);
		ans++;
	}

	std::cout << ans << std::endl;

	return 0;
}