#742 (Div.2) B - MEX or Mixup

문제 링크 => Problem - B - Codeforces

Problem - B - Codeforces

---

이 문제를 해결하려면 먼저 MEX의 성질을 알아야 한다.

 

MEX([0, 1, 2, ..., x]) = x + 1 

 

MEX([0, 2, 4, 6, 8]) = 1

 

MEX([1, 2, 3, ... , x]) = 0

 

이런식으로 리스트 안에 0부터 시작해서 1씩 증가하다가 비어있는 숫자에 대해서 해당 값이 MEX 값임을 알 수 있다.

 

문제는 MEX 값 a와 XOR 값 b가 주어졌을 때과 리스트 안의 모든 XOR값이 b를 만족하면서 리스트의 MEX 값이 a를 만족하도록 하는 리스트의 최소 길이를 구해야 한다.

 

이때 리스트 안에 숫자는 겹쳐도 상관없다. (이부분 때문에 많은 뻘짓을 했다)

 

먼저 최소 길이여야 하므로 MEX 값 a에 대하여 다음과 같이 세팅할 수 있다.

 

a = MEX([0, 1, 2, ..., a - 1])

 

근데 테스트 케이스 50,000 그리고 a, b값은 최대 300,000 임을 고려하면 for문을 돌려서 xor 값을 구하면 시간 초과가 일어난다.

 

따라서 배열 dp[x] 를 이용하여 미리 모든 xor값에 대하여 미리 세팅할 수 있다.

 

for (int i = 1; i <= 300000; i++) {
	dp[i] = dp[i - 1] ^ i;
}

 

그렇다면 두가지 case를 나눠서 생각할 수 있다. (MEX : a, XOR : b)

 

1. dp[a - 1] == b 인 경우 => [0, 1, ..., a - 1] 의 원소들의 갯수이므로 a 개를 출력하면 된다.

 

2. dp[a - 1] != b 인 경우 => 임의의 원소를 x라고 설정하자.

 

일단 단순하게 dp[a - 1] ^ x = b 인 x 를 찾는것이 목표다.

 

일단 xor 연산의 성질을 이용한다면

dp[a - 1] ^ dp[a - 1] ^ x = dp[a - 1] ^ b => x = dp[a - 1] ^ b 

 

즉, x = dp[a - 1] ^ b 로 바로 구할 수 있다.

 

여기서 핵심은 리스트 안에 원소가 겹칠 수 있으나, MEX 값 a 가 유지되도록 하는 것이 중요하다.

 

(1) x 값이 a가 아닌 경우 => [0, 1, 2, ... , x, x, ... , a - 1] ( x < a )이 되거나 [0, 1, 2, ... , a - 1, x] ( x > a)이 될 수 있다.

즉, x != a 인 경우 a + 1 개를 출력해야 한다.

 

(2) x 값이 a 인 경우 => 위 방법을 적용하면 MEX 값이 a + 1이 되므로 [0, 1, 2, ..., a - 1, s, t] 가 되도록 임의의 s, t 2 개를 설정해야 한다. (s, t > a)

즉, x == a 인 경우 a + 2 개를 출력해야 한다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#define endl '\n'

using namespace std;

int dp[300001];

void test() {

	int a, b;
	cin >> a >> b;

	if (dp[a - 1] == b) cout << a << endl;
	else {
		int x = dp[a - 1] ^ b;
		if (a == x) cout << a + 2 << endl;
		else cout << a + 1 << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	for (int i = 1; i <= 300000; i++) {
		dp[i] = dp[i - 1] ^ i;
	}

	int t;
	cin >> t;
	while (t--) {
		test();
	}

	return 0;
}