BOJ 33079 흑백 설곽

문제 링크입니다.

문제 요약

$N$명의 학생이 $0$ 또는 $1$이 적힌 모자를 쓰고 빙 둘러앉습니다. 다른 학생의 모자는 볼 수 있지만 자신의 모자는 확인할 수 없습니다. 각 학생은 나머지 $N-1$명의 모자를 보고 쪽지에 ${ 0, 1, 2 }$ 중 하나의 수를 적습니다.

이제 이 과정에 참여하지 않은 $N+1$번째 학생을 데려옵니다. 이 학생에게 $N$명의 학생이 적은 수 중 하나를 제외한 나머지 $N-1$개 중 $0,1,2$가 각각 몇 개인지 알려줍니다. 이 학생은 $0,1,2$의 개수만을 바탕으로 자신이 적은 수가 포함되지 않은 나머지 한 명의 학생이 쓴 모자에 적힌 수가 $0$인지 $1$인지 알아맞혀야 합니다.

즉, 두 개의 결정론적 알고리즘의 가능한 모든 입력에 대한 출력의 리스트를 만들어야 합니다.

1. 길이가 $N-1$의 비트열을 입력받아 ${ 0, 1, 2 }$ 중 하나를 반환
2. 합이 $N-1$인 세 수를 입력받아 ${0, 1}$ 중 하나를 반환

관찰

$N+1$번째 학생이 알 수 있는 것은 각 수의 개수 뿐입니다. 순서에 관한 정보는 전달하는 과정에서 소실됩니다. 쪽지의 순서를 알 수 없으니 학생들이 쪽지에 순서와 관련된 정보를 담더라도 그것이 온전히 전달되기를 기대하기는 어렵습니다.

학생들이 앉은 순서에 관한 정보를 배제하면 남는 정보는 $N-1$명 중 $1$이 적힌 모자를 쓰고 있는 학생의 수 뿐입니다.

서브태스크 $N \equiv 0 \mod 2$, $N \equiv 2 \mod 3$ (49점)

$N$이 짝수인 경우를 살펴 봅시다. 각 학생의 쪽지가 자신을 제외한 나머지 $N-1$명의 정보를 1개씩 포함한다고 생각합시다. 편의 상 $1$번 학생의 쪽지가 배제되었다고 하면, 남은 쪽지들은 $1$번 학생에 대한 정보를 총 $N-1$개, 나머지 학생에 대한 정보를 총 $N-2$개 포함합니다.

$N-2$가 짝수이므로, 각 학생에 대한 정보를 합할 수 있다면 $1$번 학생을 제외한 모든 학생의 정보가 $\mod 2$에서 제거됩니다. 이는 단순히 각 학생이 보이는 $1$이 적힌 모자의 수 $\mod 2$를 적는 것으로 실현할 수 있습니다.

$N \equiv 2 \mod 3$인 경우도 단순히 모듈러를 2에서 3으로 바꾸면 같은 전략을 이용할 수 있습니다.

나머지 (51점)

단순히 $1$이 적힌 모자 수의 합을 적는 전략이 통하지 않습니다. 대신, 각 학생이 볼 수 있는 $1$이 적힌 모자의 수가 $i$개(자신이 $1$이 적힌 모자를 쓰고 있을 때) 또는 $i+1$개(자신이 $0$이 적힌 모자를 쓰고 있을 때) 뿐이라, 실제로 $N+1$번째 학생이 받을 수 있는 입력은 고작 $2N$개임에 주목합니다.

$1$이 적힌 모자의 수를 ${ 0,1,2 }$ 중 하나로 변환하는 $3^N$가지 방법 중 어느 하나라도 내 모자에 적힌 수에 따라 가능한 $N+1$번째 학생에게의 입력의 집합이 서로소이면, 해당 변환을 이용해 모자에 적힌 수를 알아맞힐 수 있습니다. 각 집합의 원소 개수가 적으니 하나쯤은 되는 게 있지 않을까 싶고, $N$이 작기 때문에 직접 시뮬레이션을 해볼 수 있습니다. 그리고 이 방법으로 실제로 주어진 제한 내에서 실례를 찾을 수 있습니다!

코드

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

const int seven[] = {0,1,2,0,1,0,1};
const int nine[] = {0,1,0,2,1,0,1,0,1};
const int thirteen[] = {0,1,0,1,0,2,1,0,1,0,1,0,1};

bool seven_mask[8][8];
bool nine_mask[10][10];
bool thirteen_mask[14][14];
bool mask[14][14];
int modular[14];

void mask_init(){
	seven_mask[0][6]=seven_mask[0][1]=seven_mask[4][0]=seven_mask[3][3]=seven_mask[2][4]=seven_mask[5][1]=1;
	nine_mask[0][8]=nine_mask[7][1]=nine_mask[2][0]=nine_mask[0][5]=nine_mask[4][4]=nine_mask[5][3]=nine_mask[2][6]=1;
	thirteen_mask[0][12]=thirteen_mask[11][1]=thirteen_mask[2][10]=thirteen_mask[9][3]=thirteen_mask[4][0]=thirteen_mask[0][7]=thirteen_mask[6][6]=thirteen_mask[7][5]=thirteen_mask[4][8]=1;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	mask_init();
	int n; cin >> n;
	if(n == 7) for(int i = 0; i <= 7; i++) for(int j = 0; j <= 7; j++) mask[i][j] = seven_mask[i][j];
	if(n == 9) for(int i = 0; i <= 9; i++) for(int j = 0; j <= 9; j++) mask[i][j] = nine_mask[i][j];
	if(n == 13) for(int i = 0; i <= 13; i++) for(int j = 0; j <= 13; j++) mask[i][j] = thirteen_mask[i][j];
	
	if(n == 7) for(int i = 0; i < 7; i++) modular[i] = seven[i];
	if(n == 9) for(int i = 0; i < 9; i++) modular[i] = nine[i];
	if(n == 13) for(int i = 0; i < 13; i++) modular[i] = thirteen[i];
	if(~n&1){
		cout << "2\n";
		for(int i = 0; i < (1<<n-1); i++){
			int cnt = 0;
			for(int bit = 0; bit < n-1; bit++) if(i&(1<<bit)) cnt++;
			cout << cnt%2 << ' ';
		} cout << '\n';
		for(int i = 0; i <= n-1; i++) cout << i%2 << ' ';
		return 0;
	}
	cout << "3\n";
	if(n%3 == 2){
		for(int i = 0; i < (1<<n-1); i++){
			int cnt = 0;
			for(int bit = 0; bit < n-1; bit++) if(i&(1<<bit)) cnt++;
			cout << cnt%3 << ' ';
		} cout << '\n';
		for(int i = n-1; i >= 0; i--) for(int j = n-1-i; j >= 0; j--){
			cout << !!((j+2*(n-1-i-j))%3) << ' ';
		}
		 return 0;
	}
	for(int i = 0; i < (1<<n-1); i++){
		int cnt = 0;
		for(int bit = 0; bit < n-1; bit++) if(i&(1<<bit)) cnt++;
		cout << modular[cnt] << ' ';
	} cout << '\n';
	for(int i = n-1; i >= 0; i--) for(int j = n-1-i; j >= 0; j--){
		cout << mask[i][j] << ' ';
	}
	 return 0;
}