Codeforces Round #696 (Div. 2)

문제 링크

codeforces.com/contest/1474

Dashboard - Codeforces Round #696 (Div. 2) - Codeforces

 

 

A. Puzzle From the Future

문제

이진수 두 개를 가능한 한 크게 만드는 또 다른 이진수를 구하는 문제이다.

단, 연속된 수가 있으면 압축이 된다.

 

풀이 1

이 문제는 그리디하게 해결할 수 있습니다.

우선, 연속된 수에 대한 "아주 강렬한" 조건이 있기 때문에 직감적으로 이진수를 연속되게 만들면 안 될 것 같네요.

이미 이진수 하나가 주어져있기 때문에, 우리는 나머지 정답이 될 이진수는 연속되지 않도록 만들 수 있습니다.

또한 "가장 크게 만드는" 조건이 있으므로 최대한 2를 만들도록 노력해야겠죠.

 

테스트 케이스 4번의 경우 주어진 이진수는 "111000" 입니다.

우선 첫 수는 반드시 2를 만들 수 있으니 "1"

그다음 수는 2를 만들면 연속되므로 "10"

그다음수는 다시 2를 만들 수 있으니 "101"

다음은 1이 최대이므로 "1011"

...

이런 식으로 그 이전에 만들어 준 수와 비교해서 가장 크도록 그리디 하게 만들어주면 됩니다.

소스 코드 1

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n; cin >> n;
		string b; cin >> b;
		string a = "";
		int pre = 0;
		a += '1';
		for (int i = 1; i < n; i++)
		{
			int pre = (b[i - 1] - '0') + (a[i - 1] - '0');
			if (b[i] == '0')
			{
				if (pre == 2) {
					a += '1'; pre = 1;
				}
				else if (pre == 1) {
					a += '0'; pre = 0;
				}
				else {
					a += '1'; pre = 1;
				}
			}
			else
			{
				if (pre == 2) {
					a += '0'; pre = 1;
				}
				else if (pre == 1) {
					a += '1'; pre = 2;
				}
				else {
					a += '1'; pre = 2;
				}
			}
		}
		cout << a << "\n";
	}
	return 0;
}

 

B. Different Divisors

문제

양의 정수 d가 주어졌을 때, 조건을 만족하는 양의 정수 a를 찾는 문제이다.

a는 최소 4개의 약수를 가질 것.

모든 약수들의 간격은 최소 d 이상은 되어야 함.

 

풀이 1

상당히 헤매었던.. 문제입니다.

우선 1을 제외한 모든 수는 약수를 최소 2개는 갖습니다. (1과 자기 자신)

나머지 두 개만 찾으면 되겠네요!

 

처음에 간단히 생각해볼 수 있는 방법은

1, 1 + d, 1+ 2d, (1 + d) * (1 + 2d)

이렇게 있으면 a = (1 + d) * (1 + 2d) 라면 위 조건을 모두 만족시킬 수 있다는 점입니다.

맞는 말입니다.

으앙! 쳐맞는 말이었군요 ㅠㅠ

무슨 일인고.. 하니 그 a값은 약수로 1, 1 + d, 1+ 2d, a 딱 4가지만 가진다는 보장이 없습니다 ㅠ

1과 1+d 사이 또는 1+d ~ 1+2d / 1+2d ~ a 사이에 또 a의 약수가 있다면 차이가 d이하가 되므로 틀리게 됩니다.

 

그리고 1+d, 1+2d 도 약수가 있으면 큰일이겠네요 ㅠ

 

따라서 1을 제외한 나머지 2가지 수는 소수이고, 마지막 수가 2가지 소수를 곱한 값이면 모든 조건을 만족시킬 수 있고, 이때 a값이 최소임은 자명합니다. 

 

문제에서 d값은 최대 1만이므로 한 20만까지 에라토스테네스의 체를 이용해 소수를 모두 구하고

2부터 시작해서 차이가 +d가 나도록 소수 2개를 골라주면 됩니다.

소스 코드 1

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
bool check[1000010];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	check[1] = true;
	for (int i = 2; i * i <= 200000; i++) {
		if (!check[i]) {
			for (int j = i + i; j <= 200000; j += i) {
				check[j] = true;
			}
		}
	}
	vector<int>pr;
	for (int i = 1; i <= 200000; i++) if (!check[i]) pr.push_back(i);
	while (t--)
	{
		int d; cin >> d;
		int pre = 1;
		int cnt = 0;
		int ans = 1;
		for (int i = 0; i < pr.size(); i++) {
			if (pr[i] - pre >= d) {
				ans *= pr[i];
				pre = pr[i];
				cnt++;
				if (cnt == 2) break;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

 

C. Array Destruction

 

문제

쓸모없는 2n 개의 양의 정수가 담긴 배열이 주어진다.

다음과 같은 작업을 통해 배열에 있는 원소를 다 비워버리자.

 

1. 우선 아무 양의 정수 x를 고른다. (배열에 없어도 된다.)

2. 합이 x가 되는 두 원소를 고르고, x를 두 원소 중 큰 수로 바꾼 후, 두 원소를 삭제한다. 이 과정을 n번 반복한다.

 

만약 합이 x가 되는 두 원소가 없다면 이 작업은 중단되며 그때 "NO"를 출력한다.

그렇지 않다면 그 과정을 모두 출력하면 된다.

 

풀이 1

우선, 합이 x가 되는 두 원소를 a, b라 하면 (x = a + b) a, b가 x보다 작음은 자명하다. (모든 원소는 양의 정수)

그렇다면 맨 처음 x를 정할 때, 그 x는 배열에 있는 수들 중 가장 큰 수보다 반드시 커야 한다.

 

왜 그런가 하면..

배열 a를 오름차순으로 정렬했을 때 a1, a2,..., a(2n-1), a(2n)로 원소가 정렬되었다고 해보자.

맨 처음 x가 a(2n) 보다 작다면 처음에 두 수 a,b를 고를 때 a(2n)을 선택할 수 없게 되고

a(2n)을 선택하지 못한다면 영영 x는 a(2n)보다 작으므로 결국 고르지 못하게 되기 때문이다.

 

이는 a(2n)을 고른 이후에도 마찬가지로, 배열에 있는 수들 중 가장 큰 수를 계속 골라야만

그다음 큰 수를 고를 수 있게 된다.

 

따라서 x는 큰 수부터 시작해서 점점 작아지는 느낌으로 가야 한다.

 

여기까지 이해했다면 이다음은 브루트 포스의 영역이다.

 

 

맨 처음 x는 우리가 아무거나 선택할 수 있기 때문에

가장 큰 수를 제외하고 하나씩 선택해서 시뮬레이션을 돌려보면 된다. (x = (가장 큰 수) + (아무거나 수))

이렇게 수를 골랐다면 이제 다음 수는 (가장 큰 수) = (그다음 큰 수) + (가장 큰 수와 다음 큰 수의 차이)...로 계속 이루어지므로 두 번째 수가 있으면 계속하고, 없으면 멈추면 된다.

단, 수를 찾는데 시간을 줄이기 위해 map을 사용하자.

 

n이 최대 1000밖에 안되므로 시뮬레이션해도 500번이고 모든 경우를 다 따져보아도

1000 x 500으로 50만 번 계산하고 끝나게 된다.

소스 코드 1

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	
	while (t--)
	{
		int n; cin >> n;
		map<int, int>mp;
		vector<int>v(2 * n);
		for (int i = 0; i < 2 * n; i++) {
			cin >> v[i];
			mp[v[i]]++;
		}
		map<int, int> tmp = mp;
		sort(v.begin(), v.end());
		vector<pair<int, int> > ans;
		int pre = v[2 * n - 1];
		
		bool flag = false;
		for (int k = 2 * n - 2; k >= 0; k--) {
			mp = tmp;
			pre = v[2 * n - 1];
			vector<pair<int, int> >tans;
			tans.push_back({ v[k], pre });
			mp[v[k]]--; mp[pre]--;
			int ptr = 2 * n - 2;
			for (int i = 0; i < n - 1; i++) {
				while (mp[v[ptr]] == 0) ptr--;
				mp[v[ptr]]--;
				if (mp[pre - v[ptr]] == 0) {
					break;
				}
				else {
					tans.push_back({ v[ptr], pre - v[ptr] });
					mp[pre - v[ptr]]--;
					pre = v[ptr];
					ptr--;
					if (i == n-2) {
						flag = true;
						ans = tans;
					}
				}
			}
			if (flag) break;
		}
		if (n == 1) {
			cout << "YES\n";
			cout << v[0] + v[1] << "\n";
			cout << v[0] << " " << v[1] << "\n";
		}
		else if (ans.size() == n) {
			cout << "YES\n";
			cout << ans[0].first + ans[0].second << "\n";
			for (int i = 0; i < ans.size(); i++) {
				cout << ans[i].first << " " << ans[i].second << "\n";
			}
		}
		else {
			cout << "NO\n";
		}
	}
	return 0;
}

 

 

D. Cleaning

문제

n개의 돌무더기를 제거하려고 한다.

제거 방식은 다음 작업을 따르는데

두 개의 돌이 있는 이웃 돌 무더기를 고른 후 각각 -1씩 하는 작업이다.

이것만 하면 너무 쉬우니 한 가지 능력이 있는데

바로 제거하기 전, 이웃되는 두 돌무더기를 바꿀 수 있다는 점이다. 이 능력은 너무 사기라 최대 1번만 사용 가능하다.

모든 돌무더기를 제거할 수 있겠는가?

 

풀이

머리에 털나고 처음 풀어보는 무려 2200점 레이팅의 문제이다.. ㄷ

원래 웬만하면 쳐다보지도 않는 문제인데.. 요즘 어려운걸 많이 풀어봐야 한다는 생각과.. 이 문제는 좀 할 만한 것 같아서 풀이에 올려놓는다.

 

우선 에디토리얼에 나온 문제 설명은 이렇다.

 

능력을 사용하지 않고, 돌 무더기를 모두 치울 수 있는 조건이 어떻게 되는가?

 

1. 우선 첫 번째 돌무더기는 두 번째 돌 무더기 밖에 같이 치울 친구가 없다. 

따라서 a[1] > a[2] 가 되버리면 a[2]를 다 쓰더라도 첫 번째 돌 무더기에 있는 돌들을 모두 제거할 수 없다.

2. 만약 첫 번째를 모두 제거하였더라면, 두 번째는 a[2] - a[1]이 된다. 따라서 세 번째 돌무더기만 이용해 두 번째를 치워야 한다. 원리는 1번과 동일하다.

3. 이렇게 1 ~ n 번째 인덱스를 순회하다가 a[i] > a[i+1] 가 되어버리면, 이는 능력없이 절대 치울 수 없고

a[i] <= a[i+1] 라면, a[i+1] = a[i+1] - a[i] 로 초기화해야 한다.

 

그럼 이 작업을 모든 i에 대해서 다 해야 하는가? 그렇지 않다.

만약 i와 i+1 번째 돌무더기를 바꾸었더라도, 1, 2,... i-2 번째 돌무더기는 그 어떤 영향을 받지 않는다.

또한 i+2,..., n 도 마찬가지이다.

 

따라서 미리 prefix, suffix 전처리를 해준다면 (1,... i-1을 청소했을 때 i번째 돌무더기 돌 개수)

i, i+1을 바꾸고, prefix(i-1), suffix(i + 2)를 바로 알 수 있으므로 총 O(n) 시간 복잡도로 계산이 가능하다.

소스 코드

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int t, n;
 
bool check(vector<ll> v)
{
	for (int i = 0; i < v.size() - 1; i++)
	{
		if (v[i] > v[i + 1]) return false;
		else {
			v[i + 1] -= v[i];
		}
	}
	if (v.back() != 0) return false;
	else return true;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n;
		vector<ll>a(n);
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
 
		if (check(a)) {
			cout << "YES\n";
			continue;
		}
		if (n == 1)
		{
			cout << "NO\n";
			continue;
		}
 
		vector<ll>p(n), s(n);
		vector<ll>b = a;
		p[0] = b[0];
 
		for (int i = 1; i < n; i++)
		{
			if (p[i - 1] == -1 || b[i - 1] > b[i]) {
				p[i] = -1;
			}
			else {
				b[i] -= b[i - 1];
				b[i - 1] = 0;
				p[i] = b[i];
			}
		}
		b = a;
		s[n - 1] = b[n - 1];
		for (int i = n - 2; i >= 0; i--)
		{
			if (s[i + 1] == -1 || b[i + 1] > b[i]) {
				s[i] = -1;
			}
			else {
				b[i] -= b[i + 1];
				b[i + 1] = 0;
				s[i] = b[i];
			}
		}
		bool flag = false;
		for (int i = 0; i < n - 1; i++)
		{
			if (i == 0 || i == n-2) {
				swap(a[i], a[i + 1]);
				if (check(a)) {
					cout << "YES\n";
					flag = true;
					break;
				}
				swap(a[i], a[i + 1]);
				continue;
			}
			vector<ll> c = { p[i - 1], a[i], a[i + 1], s[i + 2] };
			if (p[i - 1] == -1 || s[i + 2] == -1) continue;
			swap(c[1], c[2]);
			if (check(c))
			{
				cout << "YES\n";
				flag = true;
				break;
			}
		}
		if (flag) continue;
		cout << "NO\n";
	}
	return 0;
}