Educational Codeforces Round 102 (Rated for Div. 2)

문제 링크

codeforces.com/contest/1473

Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces

 

A. Replacing Elements

문제

양의 정수로 이루어진 수열 a가 주어질 때, 다음과 같은 작업을 할 수 있다.

• 서로 다른 인덱스 i, j, k를 고른 후, ai = aj + ak 로 바꿀 수 있다.

이 작업을 무한정 할 수 있다고 할 때, 수열 a의 모든 수를 d보다 작거나 같게 만들 수 있는가?

 

풀이 1

이 문제의 경우 두 가지 case일 때, 문제 조건을 만족시킬 수 있습니다.

1. 모든 수가 d보다 작거나 같을 때, 작업을 하지 않고 그대로 정답이 됩니다.

2. 수열 a에 포함된 어떤 두 수의 합이 d보다 작거나 같을 때. 이때 이 두 수를 이용해 다른 원소들도 모두 d보다 작거나 같게 만들 수 있습니다.

 

따라서 우선 수열 a를 오름차순으로 정렬한 후, 맨 마지막 수가 d보다 작거나 같으면 바로 yes를 출력,

그렇지 않다면 맨 앞 두 수의 합이 d보다 작거나 같으면 yes, 그렇지 않다면 no를 출력하면 됩니다.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n, d;
		cin >> n >> d;
		vector<int>v(n);
		for (int i = 0; i < n; i++) cin >> v[i];
		sort(v.begin(), v.end());
		if (v[v.size() - 1] <= d) cout << "YES\n";
		else {
			if (v[0] + v[1] <= d) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}

 

B. String LCM

문제

문자열 a와 정수 x의 곱을 다음과 같이 정의하자.

예를 들어 a가 "abc", x가 2라면, a * x = "abcabc", "a" * 5 = "aaaaa"

 

그리고, 두 문자열 s, t의 최소공배수 LCM(s, t) = k 는 s * x = k, t * x = k 를 만족하여야 한다.

LCM(s, t)를 구하거나, 없다면 -1을 출력하라.

 

풀이 1

최소공배수란 두 수의 공배수 중 최소값이며, 모든 공배수의 약수가 되는 수입니다.

따라서 두 문자열 s, t 길이의 최소공배수를 구한 후, 그 길이만큼 문자열 s, t를 늘여준 후

둘을 비교했을 때 같지 않다면, 다음 공배수때도 같지 않을 것이기 때문에 -1을 출력하고

같다면 그대로 길어진 문자열을 출력하면 됩니다.

 

*참고 - 최소공배수 구하는 법

1. 우선 두 수의 최대공약수를 구한다. (유클리드 호제법으로, 생략)

2. 두 수의 곱에 1번에서 구한 최대공약수를 나누어주면 된다.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		string s, t;
		cin >> s >> t;
		int lc = lcm(s.size(), t.size());
		int s_cnt = lc / s.size();
		int t_cnt = lc / t.size();
		string tmp = "";
		for (int i = 0; i < s_cnt; i++) tmp += s;
		s = tmp;
		tmp = "";
		for (int i = 0; i < t_cnt; i++) tmp += t;
		t = tmp;
		if (s == t) {
			cout << s << "\n";
		}
		else cout << "-1\n";
	}
}

 

C. No More Inversions

 

문제

n개의 원소를 갖는 수열 a는 다음과 같은 모양을 갖습니다.

1, 2, 3, ..., k-1, k, k-1, k-2, ..., k - (n - k)

 

또한 "inversion"은 다음과 같은 상황을 말합니다.

인덱스 i, j가 i < j 이고, a[i] > a[j] 일 때

 

k개의 원소로 이루어진 수열 p가 있고, n개의 원소로 이루어진 수열 b는 다음을 만족하며 이루어집니다.

-> b[i] = p[a[i]]

 

수열 b의 "inversion"이 수열 a의 "inversion"을 넘지 않는 상황에서 수열 b의 사전 순이 최대가 되도록 하는 수열 p를 출력하시오.

 

풀이 1

개인적으로 상당히 어려웠던 문제였습니다.

결론부터 말하면 그리디 문제이고, 1... k로 구성된 수열 p에서 뒤에서 n-k 개를 거꾸로 뒤집으면 되는 문제입니다.

 

이러한 문제의 경우, 직접 만들어보는 것도 정말 큰 힌트가 될 수 있습니다.

직접 permutation을 돌려서 정답이 되는 수열 p, b를 만들어 볼게요.

다음과 같은 코드로 말이죠.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int>a;
	for (int i = 1; i <= k; i++) a.push_back(i);
	for (int i = k - 1; i >= k - (n - k); i--) a.push_back(i);
	int inv = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] > a[j]) inv++;
		}
	}
	vector<int>p;
	for (int i = k; i >= 1; i--) p.push_back(i);
	vector<int>b(n);
	do {
		int p_inv = 0;
		for (int i = 0; i < n; i++) {
			b[i] = p[a[i] - 1];
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (b[i] > b[j]) p_inv++;
			}
		}
		if (p_inv <= inv) break;
	} while (prev_permutation(p.begin(), p.end()));
	for (int i = 0; i < k; i++) cout << p[i] << " ";
	cout << "\n";
	for (int i = 0; i < n; i++) cout << b[i] << " ";
	cout << "\n";
}

 

이 코드를 이용해 몇 번 돌려보면 위 결론에 해당하는 규칙이 나오게 됩니다. 하지만 풀이라기엔 좀 아쉽네요.

그래서 좀 더 인간적인 설명을 하자면..

a = 1, 2, ..., k-1, k, k-1, k-2 가 있다고 해볼게요. 저는 1...k 이후에 나오는 수들은 밑줄을 치고 수를 셀 거예요.

수열 a에서 해당하는 부분은 2개가 있네요.

그렇다면 수열 a에서 k-2, k-1, k, k-1, k-2 이렇게 5개의 수는

수열 p = [..., k-2, k-1, k] 여기 마지막 3가지 수의 영향을 받아 수열 b가 만들어지겠죠!

그렇다면 수열 b는 1, 2, ..., k-2, k-1, k, k-1, k-2 가 되고 이는 수열 a와 같습니다.

그럼 이번엔 수열 p에서 밑줄 친 부분을 뒤집어 보겠습니다.

수열 b는 1, 2, ..., k, k-1, k-2, k-1, k 가 되고 여기서 "inversion"을 계산할 때 기존 수열 a와 다른 부분은
마지막 5가지 수에 대한 쌍 밖에 없습니다.

 

그럼 따로 떼어놓고 생각해볼게요.

k-2, k-1, k, k-1, k-2 -> [0, 1, 2, 1, 0]

k, k-1, k-2, k-1, k    -> [3, 1, 0, 0, 0]

 

차이가 보이시나요? 수열은 다르지만, 저 숫자들(inversion)에 영향을 미치는 숫자는 같습니다.

inversion은 어떤 수 x가 있을 때, 그 수 앞에 x보다 더 큰 수와 뒤에 x보다 더 작은 수의 합이 되기 때문이죠.

 

다른 수열도 볼게요.

 

k-1, k, k-2, k, k-1 -> [1, 2, 0, 1, 0]

 

이 수열도 결국 합은 똑같습니다. 따라서 가장 이득이 되려면 p는 밑줄 구간을 반대로 뒤집어야 하고

b는 그 값을 그대로 출력해주면 됩니다.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		int dist = n - k;
		int ptr = 1;
		for (int i = 1; i < k - dist; i++) {
			cout << i << " ";
			ptr++;
		}
		for (int i = k; i >= ptr; i--) {
			cout << i << " ";
		}
		cout << "\n";
	}
}

 

D. Program

 

문제

'+', '-' 로 이루어진 n개의 연산자가 주어집니다.

현재 수는 0부터 시작하며 +를 만나면 +1, -를 만나면 -1을 더해주면 됩니다.

이때 쿼리 l, r이 주어지면 n개의 연산자 중 [l, r] 구간 연산자는 무시한 채 결괏값을 출력하는 문제입니다. 

 

풀이 1

우선 이 문제는 n, m이 최대 20만이기 때문에 브루트 포스로 풀 순 없겠네요.

사실 대부분의 쿼리 문제는 무식하게 푸는 방법이 성립되기란 쉽지 않은 것 같습니다.

이 문제도 결론부터 말하자면 prefix, suffix (접두사, 접미사)를 사용해 푸는 문제입니다.

왜 그러느냐.. 하면 오랜만에 아이패드를 집으로 가져왔으니 직접 그려서 나타낼래요!

 

펜슬을 너무 안 쓰다 보니 글씨가 엉망이네요 ㅠㅠ

 

결과적으로 특정 쿼리 l, r이 주어진다면

미리 구해둔 prefix [l-1]에서 min, max, 현재 값을 뽑은 후,

suffix [r+1]에서 min, max값을 prefix에서 구한 현재 값에 비교해 min, max값을 뽑으면 됩니다.

그렇게 되면 구간 [l, r]을 바로 삭제할 수 있죠.

 

정답은 max - min + 1을 한 값이 됩니다.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n, m;
		cin >> n >> m;
		//접두사(max, min), 접미사(max, min)
		vector<pair<int, int> >pre(n), post(n);
		vector<int>pre_sum(n);
		string s; cin >> s;
 
		int mini = 0, maxi = 0;
		int ptr = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '-') ptr--;
			else ptr++;
			mini = min(mini, ptr);
			maxi = max(maxi, ptr);
			pre[i] = { maxi, mini };
			pre_sum[i] = ptr;
		}
		mini = 0, maxi = 0, ptr = 0;
		for (int i = n - 1; i >= 0; i--) {
			if (i == n - 1) {
				if (s[i] == '+') post[i] = { 1, 0 };
				else post[i] = { 0, -1 };
			}
			else {
				if (s[i] == '+') {
					if (post[i + 1].second == 0) post[i] = { post[i + 1].first + 1, 0 };
					else post[i] = { post[i + 1].first + 1, post[i + 1].second + 1 };
				}
				else
				{
					if (post[i + 1].first == 0) post[i] = { 0, post[i + 1].second - 1 };
					else post[i] = { post[i + 1].first - 1, post[i + 1].second - 1 };
				}
			}
		}
 
		for (int i = 0; i < m; i++)
		{
			int l, r; cin >> l >> r;
			if (l == 1 && r == n)
			{
				cout << 1 << "\n";
			}
			else if (l == 1)
			{
				cout << post[r ].first - post[r ].second + 1 << "\n";
			}
			else if (r == n)
			{
				cout << pre[l - 2].first - pre[l - 2].second + 1 << "\n";
			}
			else
			{
				ptr = pre_sum[l - 2]; //cout << ptr << "\n";
				maxi = pre[l - 2].first; //cout << maxi << "\n";
				mini = pre[l - 2].second; //cout << mini << "\n";
				maxi = max(maxi, ptr + post[r ].first); //cout << maxi << "\n";
				mini = min(mini, ptr + post[r].second);  //cout << mini << "\n";
				cout << maxi - mini + 1 << "\n";
			}
		}
	}
}