Codeforces Round #631 (Div. 2) virutal

금요일에 div.2 코포가 열리게 되었다. 그때 약속이 있어서 실제로 참가는 하지 않고 오늘 virutal을 돌렸다.

A번은 무난하게 풀고 B번은 예외처리를 안 해줘서 한 번 틀리고 acept 됐다. 하지만 정리를 해보니 쉬웠던 부분을 어렵게 돌아서 푼 것이 있어서 다시 풀어보았다.

C번은 영어 해석만 열심히 하다가 친구에게 물어봤는데 알려준 거를 잘 못 이해하였다. 그래서 오히려 그냥 해석한 것보다 더 이해가 안 가서 1시간 동안 문제 이해만 하다 끝나게 되었다. 나중에 다시 시간을 내서 업 솔빙을 해보아야겠다.

 

 

A. Dreamoon and Ranking Collection

문제 설명

해석이 바로 됐으면 1~2분 안에 풀었을 거 같았던 문제였다. 경진대회를 참가한 지역이 배열로 주어지고 x개만큼 대회를 더 참가할 수 있을 때 첫 번째 지역부터 연속되는 최대 지역을 구하는 문제이다. 

풀이

결국 bool 배열을 만들어 놓고 입력받은 지역을 다 true로 체크해준다. 그다음 1~최대 나올 수 있는 값인 200까지 반복문을 돌리면서 true이면 그냥 넘어가면 되고 false일 때 아직 참가할 수 있는 대회의 수가 남아있으면(k) k--를 한다. 이제 k==0이면 더 이상 연속되는 지역의 최댓값을 구할 수 없으므로 i-1을 출력하고 break 해주면 된다.

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 1001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

bool s[202];
int main() {
	SYNC;
	cin >> t;
	while (t--) {
		cin >> n >> k;
		memset(s, 0, sizeof s);
		fu(i, 0, n) {
			int a;
			cin >> a;
			s[a] = 1;
		}
		int ans = 0;
		fu(i, 1, 202) {
			if (!s[i]) {
				if (k > 0)
					k--;
				else {
					ans = i - 1;
					break;
				}
			}
		}
		cout << ans << '\n';
	}
}

 

B. Dreamoon Likes Permutations

문제 설명

여기서 m의 길이를 갖는 수열은 모든 원소들이 정확히 한 번씩만 1~m까지 나와야 한다. 그리고 0이 아닌 l1과 l2를 길이로 갖는 수열 p1, p2가 있다.  입력으로 주어지는 것은 l1+l2의 길이를 가진 배열 a이다.

배열 a는 p1의 원소가 먼저 나오고 다음으로 p2의 원소가 나온다. 이때 가능한 l1, l2의 모든 경우의 수를 구하는 문제이다.

풀이

처음 문제를 이해를 하는데 조금 시간을 쓰고 구현을 해보려 했다. 근데 단순히 구현을 해보려 하니까 안 되었다. 그래서 모든 경우의 수를 어떻게 N^2를 쓰지 않고 구할 수 있을까 생각을 하다가 중요한 특징을 찾아냈다.

 

이 문제에서는 수열은 1~m까지 모두 한 번씩 나와야한다. 그러므로 각 수열마다 중복된 값이 존재하면 안 된다.  조건이 모두 만족하려면 앞, 뒤로 수열이 2개 존재하고 주어진 배열을 모두 사용해야한다.

따라서 앞에서부터 중복이 나올 때까지 수열을 찾게 되면 그 지점 전까지가 p1이 될 수 있는 위치이다. 만일 수열의 조건은 만족하지만 더 짧은 길이를 선택하게 되면 p2가 중복이 되었던 지점을 지나 짧아진 곳까지 오면서 수가 중복이 되므로 더 짧은 길이는 무시해도 된다.

그래서 중복이 나왔을 때 p1, p2 수열의 조건을 확인해주고 이제는 뒤에서부터 중복되지 않는 가장 긴 길이를 구해서 조건을 확인해주면 된다. 그래서 어떠한 배열이 나오든 p1이 가장 긴 중복되지 않는 지점, p2가 가장 긴 중복되지 않는 지점으로 최대 2개의 경우의 수를 가진다.

 

예를 들어서 설명해보겠다.

(1 2 3 1 2)의 경우 p1이 길이가 1, 2, 3을 모두 가질 수 있다. 그리고 길이 4에서 중복이 된다. 만약 길이 1을 선택하면 p2의 수열이 2 3 1 2가 되어 중복이 되므로 될 수 없다. 길이 2를 선택하면 뒤에서부터 판단한 경우와 중복되므로 지금 구할 필요가 없다.

 

따라서 1~m까지 한 번씩 앞 뒤로 나오려면 중복되지 않을 때까지 가장 긴 길이의 수열을 찾아낸 다음 중복이 된 지점에서 조건을 판정해주면 된다.

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 1001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

int main() {
	SYNC;
	cin >> t;
	while (t--) {
		cin >> n;
		vi a(n);
		fu(i, 0, n) {
			cin >> a[i];
		}
		k = 0;
		set<int> s;
		vpii v;
		int idx = 0;
		fu(i, 0, n) {
			if (s.count(a[i])) {
				bool ok = 0;
				idx = i;
				fu(j, 1, idx + 1) {
					if (!s.count(j)) {
						ok = 1;
						break;
					}
				}
				if (ok) break;
				s.clear();
				fu(j, idx, n) {
					if (s.count(a[j])) {
						ok = 1;
						break;
					}
					else
						s.insert(a[j]);
				}
				if (ok) break;
				fu(j, 1, n - idx + 1) {
					if (!s.count(j)) {
						ok = 1;
						break;
					}
				}
				if (ok) break;
				v.push_back({ idx,n - idx });
				k++;
				break;
			}
			else
				s.insert(a[i]);
		}
		reverse(all(a));
		s.clear();
		fu(i, 0, n) {
			if (s.count(a[i])) {
				bool ok = 0;
				idx = i;
				fu(j, 1, idx + 1) {
					if (!s.count(j)) {
						ok = 1;
						break;
					}
				}
				if (ok) break;
				s.clear();
				fu(j, idx, n) {
					if (s.count(a[j])) {
						ok = 1;
						break;
					}
					else
						s.insert(a[j]);
				}
				if (ok) break;
				fu(j, 1, n - idx + 1) {
					if (!s.count(j)) {
						ok = 1;
						break;
					}
				}
				if (ok) break;
				if (k>0 && v[0] != pii(n - idx, idx)) {
					k++;
					v.push_back({ n - idx, idx });
				}
				else if(k==0) {
					k++;
					v.push_back({ n - idx, idx });
				}
				break;
			}
			else
				s.insert(a[i]);
		}
		cout << k << '\n';
		fu(i, 0, k) {
			cout << v[i].first << ' ' << v[i].second << '\n';
		}
	}
}

 

하지만 정리하면서 문제를 다시 정확히 파악하게 되었는데 위의 방법으로도 논리상 틀린 건 없지만 비효율적이었다. 결국 이 문제의 수열 2개는 각각 모든 배열의 원소를 써야 하고 1~m이 한 번씩 나타나야 하므로 가장 큰 크기의 값에서부터 나누어져서 존재하는 경우가 생긴다.

또한, 그렇게 되면 수열은 각각 한 번씩 수가 나타나므로 대칭인 경우도 생길 수 있다. (대칭이 아닌 경우는 중복이 되거나 수열의 조건이 맞지 않는다.)

대칭이더라도 안 되는 경우가 있을 수도 있기에 한 번 더 조건을 체크하면 모든 정답을 구하게 된다.

따라서 위의 예시의 (1 2 3 1 2)는 결국 (1 2 3), (1 2)와 (1 2), (3 1 2)로 나누어진다.

 

다른 예시로 (1 4 2 3 1)은 (1 4 2 3), (1)과 (1), (4 2 3 1)로 나누어진다.

 

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 1001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

bool s[200001];
int a[200001];

bool ch(int idx, int n) {
	fu(i, 0, n + 1)
		s[i] = 0;
	fu(i, 0, n) {
		s[a[i + idx]] = 1;
	}
	fu(i, 1, n + 1) {
		if (!s[i])
			return 0;
	}
	return 1;
}
int main() {
	SYNC;
	cin >> t;
	while (t--) {
		k = 0;
		pii v[2];
		cin >> n;
		int mx = 0;
		fu(i, 0, n) {
			cin >> a[i];
			if (mx < a[i]) {
				mx = a[i];
			}
		}
		if (ch(0, mx) && ch(mx, n - mx)) {
			v[k++] = { mx, n - mx };
		}
		reverse(a, a + n);
		if (ch(0, mx) && ch(mx, n - mx) && mx * 2 != n) {
			v[k++] = { n - mx, mx };
		}
		cout << k << '\n';
		fu(i, 0, k) {
			cout << v[i].first << ' ' << v[i].second << '\n';
		}
	}
}

 

단순히 A, B 풀고 끝냈으면 몰랐던 것을 이렇게 정리를 해보면서 비효율적이고 몰랐던 부분을 알게 되어서 좋았던 작업이었다.