이번 라운드는 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]부터 차례대로 탐색하면 된다.
'알고리즘 > 코드포스' 카테고리의 다른 글
Codeforces Global Round 25 (0) | 2024.05.05 |
---|---|
CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) (0) | 2024.05.03 |
think-cell Round 1 (0) | 2024.04.23 |
Codeforces Round 924 (Div. 2) (1) | 2024.04.12 |
Codeforces Round 923 (Div. 3) - 블루 달성 (0) | 2024.04.08 |