BOJ 24592 XOR Island

문제 링크입니다.

문제 요약

$N \le 25$명의 사람이 각각 모자를 쓰고 있습니다. 모자에는 양의 정수가 하나씩 적혀 있습니다. 각 사람은 자신을 제외한 다른 사람의 모자에 적힌 수를 볼 수 있습니다.

세 명의 모자에 적힌 수의 XOR이 0이 되는 경우 그 세 명을 좋은 집합으로 간주합니다. 모든 사람들이 사람들 중 좋은 집합이 존재한다는 사실과, 이 사실을 모든 사람이 알고 있음을 알고 있습니다.

사람들은 매일 자신이 좋은 집합에 속한다고 확신할 수 있으면 손을 듭니다. 다른 사람이 손을 들었는지 여부 또한 알 수 있습니다.

며칠 째에 처음으로 손을 드는 사람이 나오는지 알아내세요.

풀이

모든 사람이 [모든 사람이 좋은 집합의 존재성을 아는 상태로 전략을 세울 것]을 아는 상태로 전략을 세웁니다.

만약에 내가 보고 있는 $N-1$명의 사람 중 좋은 집합이 안 나왔다고 합시다. 좋은 집합이 있긴 해야 되니까 적어도 나는 좋은 집합에 포함되어 있을 것이라 추론할 수 있습니다. 이 경우 나는 첫날에 손을 듭니다.

첫날에 아무도 손을 들지 않았다고 해봅시다. 이제 어떤 크기 $N-1$짜리 부분집합을 골라도 좋은 집합이 적어도 하나 존재한다는 것을 모든 사람이 아는 상태가 되었습니다. 이제 크기 $N-2$짜리 부분집합을 봅니다. 좋은 집합이 없는 $N-2$짜리 부분집합을 찾았다고 합시다. 그러면 그 집합을 같이 보는 다른 사람이 본 $N-1$짜리 부분집합은 그 $N-2$짜리 부분집합 $\cup$ 나에 해당하고, 이 집합에는 좋은 집합이 있어야 합니다. 내가 어떤 좋은 집합에 포함되어 있을 거라 추론할 수 있으니 나는 둘째 날에 손을 듭니다.

논의를 반복하면 답은 $N-$(좋은 집합이 없는 최대 부분 집합의 크기)임을 알 수 있습니다. 이는 SOS DP로 ${\cal O}(N 2^N)$에 구할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int a[25];
bool vis[1<<25];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) for(int k = j+1; k < n; k++) vis[(1<<i)|(1<<j)|(1<<k)] = !(a[i]^a[j]^a[k]);
	int ans = n; for(int i = 0; i < (1<<n); i++){
		if(vis[i]) for(int b = 0; b < n; b++) vis[i|(1<<b)] = 1;
		else ans = min(ans, n-__builtin_popcount(i));
	}
	cout << ans;
}