Codeforces Round #580 (Div.2) 후기 / 풀이

Rating Change : +47 (1839 -> 1886)

화요일 라운드로 퍼플 갈 수도 있을 것 같아서 행복회로 빡세게 오버클럭 중....

---

A. Choose Two Numbers

자연수들로만 이루어진 두 배열 $A$와 $B$가 주어지는데, 여기서 각각 수를 하나씩 고른다. 이걸 $a$ 와 $b$라고 하자. 

이때, $a+b$ 가 $A$와 $B$ 모두에 들어가 있지 않도록 골라야 한다.

 

간단히 두 배열을 정렬한 다음, $A$에서 가장 큰 수와 $B$에서 가장 큰 수를 고르면 두 수의 합은 더 커질 것이기 때문에 두 배열에 들어갈 수가 없다.

#include <bits/stdc++.h>
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

vector <int> a, b;
int main()
{
	usecppio
	int n, m;
	cin >> n;
	a.resize(n);
	for (int i = 0; i<n; i++)
		cin >> a[i];
	cin >> m;
	b.resize(m);
	for (int i = 0; i<m; i++)
		cin >> b[i];
	sort(all(a));
	sort(all(b));
	cout << a[n-1] << " " << b[m-1] << '\n';
}

---

B. Make Product Equal One

+1 또는 -1을 할 수 있으므로, 우선 모든 양수들을 1로, 모든 음수들을 -1로 만들자. 여기까지 사용한 연산의 횟수가 $K$번이라면, 이제 부호만 잘 조절해서 곱을 1로 만들면 된다.

0이 몇 개인지 센 다음, 이걸 $Z$ 개라고 하자. 한 개라도 있으면, 즉 $Z > 0$ 이면 우리는 부호를 마음대로 바꿀 수 있다. 그러나 여전히 $Z$번의 연산으로 적당히 몇 개를 +1, 몇 개를 -1로 바꿔야 하므로 답은 $K+Z$.

0이 하나도 없으면, 두 가지 경우가 있는데

- $K$번 연산으로 상황이 끝난 경우 (즉, 이미 곱이 1인 경우)

- $K$번 연산으로 곱이 -1이 된 경우

첫 경우는 그냥 답이 $K$이고, 두 번째 경우는 아무거나 잡고 부호를 돌려주면 되니까 $K+2$ 번만에 할 수 있다.

#include <bits/stdc++.h>
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
int zeros;
int need;
vector <int> pos, neg;
int32_t main()
{
	usecppio
	int n;
	cin >> n;
	for (int i = 0; i<n; i++)
	{
		int x;
		cin >> x;
		if (x > 0)
			pos.push_back(x);
		else if (x < 0)
			neg.push_back(x);
		else zeros++;
	}
	for (auto it:pos)
		need += (it-1);
	for (auto it:neg)
		need += (-1-it);
	if (zeros)
		need += zeros;
	else
		if (neg.size() % 2 == 1)
			need += 2;
	cout << need;
}

---

C. Make Equal

1부터 $2n$ 까지의 숫자를 원형으로 배열해서, 임의의 위치에서 시작해서 연속한 $n$개를 더한 값들이 서로 1 이하의 차이를 가져야 한다.

이렇게 배치하면, 1 6 3의 합이 10, 6 3 2 의 합이 11, 3 2 5의 합이 10 ... 이라서, 모든 연속한 3개끼리의 합이 10 또는 11로 조건에 맞는 배치.

 

몇 개의 Casework를 통해, $n$이 짝수일 때는 불가능하다는 사실을 알 수 있다. 

 

돌려도 답이 바뀌지 않으므로, 일반성을 잃지 않고 1을 12시 방향에 고정하자. 그리고 답은 시계 방향으로 돌면서 출력하기로 정하자. 즉, $a_1 = 1$ 로 시작하는, $1$부터 $2n$ 까지의 순열 $a_1$ 부터 $a_{2n}$ 을 답으로 하겠다는 의미이다. 

일단 중요한 점은 $n$개의 합을 할 것이므로, $a_1$부터 $a_n$까지를 더한 값과 $a_2$부터 $a_{n+1}$ 까지의 합은 $a_{n+1} - a_1$ 차이가 나게 된다. 그런데 $a_1$에 1을 고정했으므로 $a_{n+1}$ 에는 2밖에 올 수 없다.

이런 식으로 생각하면, 1과 2, 3과 4, 5와 6 ... 이 서로 마주 보는 위치에 서야 한다는 것을 알 수 있다.

또한, 3이 온 쪽에 6이, 4가 온 쪽에 5가 와야 합이 일정해질 것이다. 따라서, 1과 2를 잇는 12시 - 6시 방향 직선을 기준으로 "왼쪽" 과 "오른쪽"을 나누면, 오른쪽에 작은 수가 오는 경우와 왼쪽에 작은 수가 오는 경우가 한번씩 번갈아서 와야 한다.

 

이런 점들을 고려해서 배열을 짜 주면 OK.

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
vector <int> order;
int32_t main()
{
	usecppio
	int n;
	cin >> n;
	if (n % 2 == 0)
	{
		cout << "NO";
		return 0;
	}
	cout << "YES\n";
	order.resize(2*n);
	int curpt = 0;
	for (int i = 1; i<2*n; i+=2)
	{
		order[curpt] = i;
		order[(curpt+n)%(2*n)] = i+1;
		curpt = curpt + (n-1);
		curpt %= (2*n);
	}
	for (auto it:order)
		cout << it << ' ';
}

---

D. Shortest Cycle

문제 Description이 굉장히 짧다. 

어떤 숫자가 쓰여 있는 노드가 $n$개 주어지는데, 이 노드들 간에는 $a_i \texttt{ and } a_j$, 즉 bitwise and의 값이 0이 아니면 간선이 있고, 0이면 간선이 없다. 이때 그래프에서 가장 길이가 짧은 Cycle을 찾는 문제.

 

노드가 최대 10만 개니까, 그 사이에 간선이 최대 $10^{10}$ 개 있을 수 있다. 따라서 그래프를 만들어보지 않고 답을 찾아야 한다.

 

먼저, 숫자 전체가 대략 64비트 안에 다 들어가며, 각 비트에 0번부터 63번까지 번호를 붙여 주면, 어떤 노드 $a_i$에 대해서 몇 번 비트가 켜져 있는지를 모두 마킹할 수 있다. 이렇게 마킹을 하면, 각 비트에 대해서 "이 비트가 마킹된 노드" 들 끼리만 모으면 그 노드들 간에는 모두 간선이 있어야 하므로 완전 그래프를 이룬다.

 

완전 그래프는 노드가 2개가 아닌 이상, 노드가 3개 이상일 때 반드시 크기 3짜리 사이클이 있으므로, 이 경우 항상 답이 3이 된다.

 

만약 모든 비트에 노드가 2개 이하만 마킹되어 있다면, 각 비트에 대해서는 많아야 1개의 간선이 존재한다는 뜻이다. 따라서, 전체 비트가 64개 이하이므로 이제는 간선 최대 64개, 정점 최대 128개인 그래프에서 minimum length cycle을 찾는 문제가 된다.

 

DFS로 짜다가 엄청 오래 걸렸고, 결국 MLE를 받았다. 아마도 재귀 종료 조건을 잘못 줘서 메모리가 터진거 같은데...

그래서 한 30분 정도, 그걸 비재귀로 고쳐 짜려고 하다가 망했다. 그런데 종료 한 25분 전에 코포는 e-maxx나 Geeksforgeeks 같은거 볼 수 있다는게 생각 나서, undirected graph minimum length cycle 이라고 검색했더니 minimum weight cycle을 찾는 코드가 나와서, 그냥 weight = 1 넣고 쓰기로 하고 (어차피 간선 수도 정점 수도 매우 작으므로, 대충 적당히 찾아만 지면 된다) 긁어다 써서 맞았다. :uwek: 

덕분에 평소에 잘 안쓰는 list <pii> graph 같은것도 써 봤다 :(

코드 : 링크

---

그래프 구현 너무 어려워요...:cry:

그래도 C랑 D에서 필요한 관찰들이 빠르게 생각나서 코딩에서 뇌절할 시간을 조금 벌었다.

다음라운드에 퍼플 갈 수 있을라나;;;