BOJ 16764 Cowpatibility

문제 링크입니다.

문제 요약

5개의 원소를 가진 집합들이 주어졌을 때, 그중 서로 공통된 원소가 없는 집합 쌍의 개수를 세어야 합니다.

원소가 하나뿐이라고 해 봅시다

각 집합에 원소가 하나뿐이라면, 답은 각 종류의 원소마다 (그 원소의 개수)C2 를 구해 더하는 것으로 구할 수 있습니다.

원소가 2개라면

일단 원소가 하나일 때처럼 (중복 원소 개수)C2를 구해 다 더해줍니다. 이 경우, 두 원소가 모두 같은 집합들은 각 원소마다 한 번씩 총 두 번 겹쳐 세집니다. 이걸 보정해 주기 위해, 두 원소를 쌍으로 묶은 걸 하나의 2-원소로 생각하고 (중복 2-원소 개수)C2를 구해 다 빼 주면 됩니다.

일반화

원소가 5개인 경우는, 1-원소의 조합을 다 더하고, 2-원소의 조합을 다 빼고 … 5-원소의 조합을 다 더해주면 됩니다. 5개의 원소의 전부 또는 일부를 사용해 만들 수 있는 공집합이 아닌 부분집합의 수는 31가지니까, 모든 집합에 대해 1-원소부터 5-원소까지를 만들어도 총 원소는 150만 개 정도로 그럭저럭 다룰 만합니다. 이제 그 원소들을 잘 정렬해 주면, 같은 원소끼리는 인접한 위치로 묶이기 때문에 개수를 빠르게 세 줄 수 있습니다. 또는 해시 셋을 쓰거나 해도 좋습니다.

저는 vector끼리의 비교가 가능함을 이용해 통째로 정렬해 주었습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>> v;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		vector<int> a(5);
		cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
		sort(a.begin(), a.end());
		for(int j = 0; j <= 31; j++){
			vector<int> in; in.push_back(0);
			for(int k = 0; k < 5; k++){
				if((j>>k)&1) in.push_back(a[k]);
			}
			v.push_back(in);
		}
	}
	sort(v.begin(), v.end());
	ll ans = 0, cnt = 1;
	for(int i = 1; i < v.size(); i++){
		if(v[i] == v[i-1]){
			cnt++; continue;
		}
		ans += (v[i-1].size()&1 ? 1 : -1)*cnt*(cnt-1)/2;
		cnt = 1;
	}
	ans += (v[v.size()-1].size()&1 ? 1 : -1)*cnt*(cnt-1)/2;
	cout << ans;
}