Round #686 (Div. 3) 후기 및 풀이

 

처음으로 '언레가 되어버린 라운드'가 아닌 '언레로 적용되는' 라운드에 참여했다. 

사실 부계도 1600을 이미 넘겨서 그냥 잘까 하다가 코포 중독증에 걸려버린 나로서는 그냥 자기는 아쉬워서 참가했는데 그냥 잤어야 했다... 다음날이 너무 힘들었다.

 

가볍게 참가해서 제출도 대충대충 하다 보니 WA가 많이 나왔다. rated 라운드였어도 신중하게 제출하지 않았을 것 같아서 조금 주의할 필요가 있을 것 같다. 

 

 

---

 

 

A. Special Permutation 

 

p[i] != i 를 만족하는 순열을 만드는 것이다. 

1, 2, ... n 순서대로 구성된 순열을 한 칸씩 밀기만 하면 만족한다. 

 

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

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 2; i <= n; i++) cout << i << ' ';
		cout << 1 << '\n';
	}
}

 

 

B. Unique Bid Auction

 

하나만 있는 원소 중에서 가장 작은 값의 index를 출력하는 문제이다.

원소 1개만 있는 것 중에서 가장 작은 값을 구한 후, 그 값이 있는 index를 찾으면 된다.

 

이 문제에서 굉장히 많은 사람이 시스텟에서 터졌는데, 배열의 크기가 20만이고, testcase가 최대 2만이기 때문에

매 testcase마다 20만 크기의 배열을 초기화를 시켜주게 되면 TLE가 나게 된다. 

 

거의 대부분의 문제는 testcase의 개수와 상관없이 각 testcase 내에서만 생각해도 되지만,

이러한 문제는 하나의 큰 채점 케이스 안에 많은 테스트 케이스를 넣어두었기 때문에 반드시 배열 초기화 등을 할 때에는 주의를 해주어야 한다. 

종종 이런 경우가 나오는데, 공교롭게도 pretest에서 잘 걸리지 않는 것 같다. 

예전에 한번 이런 경우를 본 적이 있어서 이번에는 코드를 짤 때부터 주의하면서 짰고, 뭔가 예상대로(?) 사람들이 많이 터진 것 같다.

 

#include<bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<int> cnt(n + 1, 0);
		vector<int> A(n + 1);
		for (int i = 1; i <= n; i++) {
			int a; cin >> a;
			cnt[a]++;
			A[i] = a;
		}
		int ans = -1;
		for (int i = 1; i <= n; i++) {
			if (cnt[i] == 1) {
				ans = i;
				break;
			}
		}
		if (ans == -1) cout << -1 << '\n';
		else {
			for (int i = 1; i <= n; i++) {
				if (A[i] == ans) {
					cout << i << '\n';
					break;
				}
			}
		}

	}
}

 

 

C. Sequence Transformation

 

원소 중에서 하나를 선택해서 해당 원소와 같은 값을 제외한 모든 원소를 지울 때 필요한 최소의 경우의 수를 고르는 문제이다. 

i = 1 ~ n인 각각의 A[i]에 대해 A[i] 사이에 있는 구간들의 개수를 구하고, 그 구간의 최소 개수를 구하면 된다.

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 2e9;

int A[200001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<vector<int>> v(n + 1, vector<int>());
		for (int i = 1; i <= n; i++) {
			cin >> A[i];
			v[A[i]].push_back(i);
		}
		int ans = MAX;
		for (int i = 1; i <= n; i++) {
			if (sz(v[i]) == 0) continue;
			int cnt = 0;
			for (int j = 0; j < sz(v[i]); j++) {
				if (j == 0) {
					if (v[i][j] > 1) cnt++;
				}
				else {
					if (v[i][j] > v[i][j - 1] + 1) cnt++;
				}
				if (j == sz(v[i]) - 1 && v[i][j] < n) cnt++;
			}
			ans = min(ans, cnt);
		}
		cout << ans << '\n';
	}
}

 

 

D. Number into Sequence

 

모든 원소가 1보다 크고, 모든 원소의 곱이 n이고, A[i] 가 A[i-1]으로 나누어 떨어지는 최대 길이의 배열을 구하는 문제이다.

n을 소인수 분해해서, 가장 개수가 많은 소수를 a라고 하면, a, a, ..., a, a*d로 구하면 된다.

(d는 n을 더 이상 a로 나누어 떨어지지 않을 때까지 나눈 값) 

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
using ll = long long;

ll prime[100001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	vector<ll> P;
	for (int i = 2; i <= 100000; i++) {
		if (prime[i] == 0) {
			P.push_back(i);
			for (int j = 2; j*i <= 100000; j++) {
				prime[i*j] = 1;
			}
		}
	}
	int psz = sz(P);
	while (T--) {
		ll n; cin >> n;
		ll k = n;
		int idx = 0;
		int cnt = 0;
		ll ans = 1;
		ll val = 0;
		while (k > 1 && idx < sz(P)) {
			if (k%P[idx] == 0) {
				cnt++;
				k /= P[idx];
			}
			else {
				if (cnt > ans) {
					ans = cnt;
					val = P[idx];
				}
				cnt = 0;
				idx++;
			}
		}
		if (cnt > ans) {
			ans = cnt;
			val = P[idx];
		}
		if (ans == 1) {
			cout << 1 << '\n' << n << '\n';
		}
		else {
			cout << ans << '\n';
			for (int i = 1; i < ans; i++) {
				cout << val << ' ';
				n /= val;
			}
			cout << n << '\n';
		}
	}
}

 

 

E. Number of Simple Paths

 

(Editorial을 참고)

 

한 연결 그래프의 정점의 개수가 n개이고 간선의 개수가 n-1개이면 트리를 만족한다. 

그러므로 간선의 개수가 n개이면 트리에 간선이 하나가 더 추가된 그래프이며, 이는 하나의 사이클을 만들게 된다.

이 그래프를 사이클 하나와, 사이클을 이루는 정점들에 트리들이 붙어있는 형태로 생각할 수 있다. 

그러면, 각 트리 별로 내부에서 생기는 path와 트리와 트리 사이를 연결하는 path로 구분할 수 있다.

트리의 내부인 경우에는 정점의 개수가 a개이면, 1 + 2 +... + a-1 = a*(a-1)/2 개의 path가 존재한다.

한 트리에서 다른 트리로 연결되는 path는 트리의 정점 a개중 한 정점과, 다른 트리의 정점 n-a개 중 한 정점을 연결하는 경우의 수와 같다. (두 정점을 연결하는 path는 유일하기 때문) 

따라서 각 트리의 정점을 cnt[i]라고 한다면 cnt[i]*(cnt[i]-1)/2 + cnt[i]*(n-cnt[i]) 를 모두 더해주면 된다.

 

라운드 도중에는 풀지 못했는데, 이런 아이디어로 문제를 해결하는 것에 감명을 많이 받았다. 

얻어갈게 많은 문제인 것 같다.

 

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

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<int>in(n + 1, 0), visited(n+1, 0);
		vector<vector<int>>adj(n + 1, vector<int>());
		for (int i = 1; i <= n; i++) {
			int a, b; cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
			in[a]++;
			in[b]++;
		}
		vector<int> cnt(n+1, 1);
		queue<int> leaf;
		for (int i = 1; i <= n; i++) {
			if (in[i] == 1) leaf.push(i);
		}
		while (!leaf.empty()){
			int v = leaf.front(); leaf.pop();
			visited[v] = true;
			for (int u : adj[v]) {
				if (visited[u]) continue;
				cnt[u] += cnt[v];
				cnt[v] = 0;
				in[u]--;
				if (in[u] == 1) leaf.push(u);
			}
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += 1LL * cnt[i] * (cnt[i] - 1) / 2;
			ans += 1LL * cnt[i] * (n - cnt[i]);
		}
		cout << ans << '\n';
	}
}

 

 

F. Array Partition

 

우선, 문제를 풀기 전에 생각해야 할 기본 아이디어? 상식? 같은 것이 있다.

배열의 원소들의 최댓값은, 원소가 더 추가되는 경우에는 최댓값이 감소하는 경우는 없다.

그러므로 누적 합의 형태처럼 premax[i] = max(premax[i-1] , A[i])로 premax 배열을 만들면 항상 비 내림차순으로 만들어진다. 

마찬가지로 최솟값인 경우에는 원소가 더 추가되는 경우에는 최솟값이 감소할 수 있고, 원소가 제거되는 경우에는 최솟값이 증가할 수 있다. 이를 이용하여 문제를 해결할 수 있다.

 

x = 1 ~ n-2까지 반복문을 돌면서 최댓값을 갱신해나가면 max(1, x)는 바로 알 수 있다. 

그리고 x는 고정되어 있고 max(x+y+1, n)은 미리 구해둔 premax의 값으로 O(1)만에 구할 수 있기 때문에 결국 적절한 y를 찾는 것이 목표이다.

만약 특정한 y에 대해서 max(1, x) = max(x+y+1, n) = K일 때,

min(x+1, x+y) < K이면, [x+1, x+y] 구간이 더 작아져야 한다. 따라서 y를 감소시켜 주어야 한다.

만약 min(x+1, x+y) > K이면 원소를 더 추가시켜서 최솟값을 작게 해야 하므로 y를 증가시켜주어야 한다.

이 과정을 이분 탐색을 이용해서 찾아준다. 

min을 구할 때에는 세그 트리를 이용하면 O(logn)만에 구할 수 있게 된다. 

 

라운드 중에는 풀이는 다 생각했는데, 이분 탐색을 생각하지 못해서 시간을 줄이지 못했다.

정해는 Div3이기 때문에 물론 세그 트리를 이용하지 않겠지만, 구간의 최솟값을 보면 세그 트리가 생각나는 건 나뿐만이 아닐 것이다...

 

#include<bits/stdc++.h>

using namespace std;
int A[200001];
int tr[800001];
int mx[200001];
int init(int x, int s, int e) {
	if (s == e)return tr[x] = A[s];
	else {
		return tr[x] = min(init(x * 2, s, (s + e) / 2), init(x * 2 + 1, (s + e) / 2 + 1, e));
	}
}
int min_(int x, int s, int e, int l, int r) {
	if (s > r || e < l) return MAX;
	else if (s >= l && e <= r) return tr[x];
	else return min(min_(x * 2, s, (s + e) / 2, l, r), min_(x * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> A[i];
		init(1, 1, n);
		mx[0] = 0;
		for (int i = n; i >= 1; i--) {
			mx[n - i + 1] = max(mx[n - i], A[i]);
		}
		int M = 0;
		int a, b, c;
		bool chk = false;
		for (int i = 1; i <= n - 2; i++) {
			M = max(M, A[i]);
			int s = i + 1;
			int e = n - 1;
			while (s <= e) {
				int mid = (s + e) / 2;
				int k = min_(1, 1, n, i+1, mid);
				if (M == k && k == mx[n - mid]) {
					chk = true;
					a = i;
					b = mid - i;
					c = n - mid;
					break;
				}
				else if (M < mx[n - mid]) s = mid+1;
				else if (M > mx[n - mid]) e = mid-1;
				else {
					if (k > M) s = mid+1;
					else e = mid-1;
				}
			}
			if (chk) break;
		}
		if (chk) {
			cout << "YES\n";
			cout << a << ' ' << b << ' ' << c << '\n';
		}
		else cout << "NO\n";
	}
}

 

 

 

 

실수를 많이 하는 스타일이라 별로 안 좋아하는 형태의 난이도 배치이다 ㅠ

앞의 문제는 매우 쉽다가 갑자기 난이도가 확 올라가서 같은 솔브라도 페널티에 따라 등수가 수천 등 차이나는...