Codeforces Round 934 (Div. 2)

대회 요약

스코어보드

 이번 라운드는 Div1과 Div2 두 라운드가 동시에 열리는 라운드였다. 문제가 굉장히 어려웠던 것 같고, Div2 400등 부터 6000등 까지 A, B, C를 푼 사람이 있을 만큼 A, B, C를 빨리 푸는 것이 중요한 라운드였다. C를 푼 사람과 D를 푼 사람의 차이를 보면 난이도 커브가 너무 가팔랐던 것 같다.

 B에서 원소들을 분리하는 부분을 잘못 짜서 2번 틀리고, 어찌어찌 40분정도에 C까지 푼 후에 1시간 50분 정도 거의 아무것도 못 한것 같다.

 

A. Destroying Bridges

https://codeforces.com/contest/1944/problem/A

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

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

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n, k;
		cin >> n >> k;

		if (k >= n - 1) {
			cout << 1 << '\n';
		}
		else {
			cout << n << '\n';
		}
	}
	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

 A는 그냥 A였다.

 주어지는 그래프가 완전그래프이기 때문에 하나의 정점당 n - 1개의 간선이 이어져있다. 그러므로 n - 1개 이상의 간선을 끊을 수 있다면 1번 섬의 모든 다리를 끊으면 되고, 그렇지 않을 경우 그래프의 연결이 유지되기 때문에 어떻게 끊어도 모든 정점이 연결되어있다.

 If문으로 k의 값에 따라 1 혹은 n을 출력하면 된다.

 

B. Equal XOR

https://codeforces.com/contest/1944/problem/B

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

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

	int T;
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		vector<int> l;
		vector<int> r;
		vector<int> b;
		set<int> lt;

		int n, k;
		cin >> n >> k;

		for (int i = 0; i < n; i++) {
			int v;
			cin >> v;
			if (lt.find(v) != lt.end()) {
				l.push_back(v);
				l.push_back(v);
			}
			else {
				lt.insert(v);
			}
		}
		for (int i = 0; i < n; i++) {
			int v;
			cin >> v;
			if (lt.find(v) == lt.end()) {
				r.push_back(v);
			}
			else {
				b.push_back(v);
			}
		}
		sort(r.begin(), r.end());

		for (int m : b) {
			l.push_back(m);
			r.push_back(m);
		}

		for (int i = 0; i < 2 * k; i++) {
			cout << l[i] << " ";
		}
		cout << '\n';
		for (int i = 0; i < 2 * k; i++) {
			cout << r[i] << " ";
		}
		cout << '\n';
	}
	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

 B는 길이 2n짜리 배열 a가 주어지고, a의 앞쪽 n개의 원소 중 2k개를 뽑아 l이라고 하고 a의 뒤쪽 n개의 원소 중 2k개를 뽑아 r이라고 할 때, l을 전부 xor한 값이 r을 전부 xor한 값과 같도록 l, r을 구성하는 문제였다.

 

 배열 a는 1 ~ n이 각각 2번씩 들어있는 배열이다.

l이 될 수 있는 a[1]~a[n]을 L, r이 될 수 있는 a[n + 1]~a[2n]을 R이라고 해보자.

a에 있는 어떤 수 p는 L에 두번 포함되거나, R에 두번 포함되거나, L에 한번 R에 한번 포함된다.

만약 모든 p에 대해 p가 L과 R에 한번씩 속했다면 l, r은 똑같게 만들 수 있으므로 쉽게 답을 찾을 수 있다.

 

어떤 수 p가 L에 두번 나타난다면, L과 R의 개수가 같기 때문에 R에만 두번 나타나는 q가 존재한다. 한쪽에만 나타나는 수는 모두 이렇게 쌍을 이루기 때문에, l, r에 두번씩 넣어주면 xor값이 0이 되어서 l, r을 같게 유지할 수 있다.

l과 r의 길이가 짝수이기 때문에 항상 이런 쌍을 넣을 수 있다.

 

a를 입력받으면서 set을 하나 가지고 스위핑을 하면 모든 원소를 L에만 나타나는 것 / 양쪽에 나타나는 것 / R에만 나타나는 것으로 분류하고, 적절하게 l, r에 넣어서 출력하면 된다.

 

C. MEX Game 1

https://codeforces.com/contest/1944/problem/C

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

int table[200000];

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

	int T;
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		int n;
		cin >> n;
		fill(&table[0], &table[n], 0);

		for (int i = 0; i < n; i++) {
			int v;
			cin >> v;
			table[v]++;
		}
		
		int c;
		bool used = false;
		for (c = 0; c < n; c++) {
			if (table[c] == 0) break;
			if (table[c] == 1) {
				if (used) {
					break;
				}
				used = true;
			}
		}
		cout << c << '\n';
	}
	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

 C는 게임 이론 문제였다.

 

 배열 a가 주어진다. Alice와 Bob이 Alice부터 시작해서 차례로 턴을 진행한다. Alice는 a의 값 중 하나를 골라서 삭제하고, 그 값을 c라는 배열에 넣는다. (이 배열은 게임이 시작할 때 빈 배열이다.) Bob은 a의 값 중 하나는 골라서 삭제한다.

 Alice는 MEX(c)값을 최대화하는 것이 목적이고, Bob은 MEX(c)값을 최소화 하는 것이 목적이다. 둘 다 최선으로 플레이한다면 마지막에 MEX(c)값은 몇이 될 것인가?

 

 MEX는 음이 아닌 정수 중 배열에 없는 최소값이다. 예를 들면 MEX([1, 2])는 0이고, MEX([3, 0, 1])은 2이다.

 

1) 가장 간단한 사실부터 접근해보면, a에 없는 값은 c에도 없으므로 MEX(a) >= MEX(c)가 성립한다.

 

2) 배열 a가 [0, 1, 2...]와 같이 원소 하나씩만 있다면 Alice가 첫 턴에 0을 고를 것이고, (그렇지 않으면 Bob이 0을 삭제해서 MEX(c) = 0이 된다.) Bob은 1을 골라서 이후에 어떻게 플레이 하더라도 MEX(c)는 1이 된다.

 

3) 배열 a가 [0, 0, 1, 1, 2, 2, ... ,k, k]과 같이 모든 원소가 두개씩 존재한다고 해보자. Bob이 어떤 값을 삭제하더라도 Alice가 남은 하나를 가져갈 수 있으므로 MEX값은 k + 1이된다.

 

 이 세가지 사실을 통해서, MEX(c)는 가장 먼저 등장하는 0개인 원소, 혹은 두번째로 등장하는 1개인 원소 중 더 작은 값이 됨을 알 수 있다.

 코드 구현은 n이 작으므로 그냥 n크기의 테이블을 만들고 원소 수를 세어준 후, table[0]부터 차례대로 탐색하면 된다.