[Codeforces] Round #706 (Div. 2) A ~ D 풀이

 

2021. 03. 10 21:05 ~ 23:05 참가 / performance = 1849

 

 

애드혹 범벅이었던 라운드....

D가 안터졌으면 2100 performance까지 나올 수 있었는데 아쉽다. (D 시스페일이 엄청 많았다)

다행히 C까지 빠르게 풀어서 레이팅이 하락하지는 않았다.

 

 

A. Split it!

 

문자열을 2k + 1 개로 쪼갤 때, 앞의 k개와 뒤의 k개는 각각 서로 reverse된 형태로 나타낼 수 있는지에 대한 문제이다. 

양끝에서부터 s[i]와 s[n-1-i]가 같은 최대 길이를 구하고, 이 길이가 k 이상이면 조건을 만족할 수 있다. 

k보다 크다면 남는 부분은 $a_{k+1}$에 모두 포함시켜주면 된다.   

주의해야할 점은, 2k + 1이 n보다 큰 경우에는 애초에 2k+1개로 쪼갤 수 없으므로 NO이다. 

 

[소스 코드]

#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, k; cin >> n >> k;
		string s; cin >> s;
		int cnt = 0;
		for (int i = 0; i < n / 2; i++) {
			if (s[i] == s[n - 1 - i]) cnt++;
			else break;
		}
		cout << (cnt >= k && 2 * k + 1 <= n ? "YES\n" : "NO\n");
	}
}

 

 

B. Max and Mex

 

매 연산마다 집합의 mex와 max값을 구한 뒤, (mex + max)/2를 올림한 값, 즉 (mex + max + 1)/2를 집합에 추가해준다. 중복되는 원소를 제외했을 때 K번 연산한 후의 집합의 크기를 구하는 문제이다.

 

먼저, K = 0인 경우에는 아무런 연산을 하지 않으므로 주어진 배열로 만든 집합의 크기를 그대로 출력하면 된다.

K ≠ 0인 경우에는 mex가 max값보다 큰지 작은지를 체크하면 된다. 그 이유는 다음과 같다.

mex < max인 경우를 생각해보자.

(mex + max + 1)/2는 항상 mex보다 큰 값을 가지게 되므로 무수히 많은 연산을 해도 mex값은 그대로 유지가 된다. 

그리고 (mex + max + 1)/2는 항상 max보다 작거나 같은 값이 된다. mex ≤ max-1 이므로, (mex + max + 1)/2 ≤ max를 만족하기 때문이다. 따라서 mex < max인 경우에는 mex와 max값이 계속 유지되므로 기존의 집합에 (mex + max +1)/2 값만 계속 추가된다. 

 

mex > max인 경우는 mex = max+1인 경우만 가능하다.

따라서 (mex + max + 1)/2 = max + 1이므로 원소를 추가할 때마다 mex와 max의 값이 1씩 계속 증가한다. 

그러므로 집합에 계속해서 최댓값 + 1인 값이 추가되므로 K개만큼 집합이 더 커지게 된다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
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, k; cin >> n >> k;
		set<int> s;
		for (int i = 1; i <= n; i++) {
			int a; cin >> a;
			s.insert(a);
		}
		if (k == 0) {
			cout << sz(s) << '\n';
			continue;
		}
		int mx = *s.rbegin();
		int mex = 0;
		for (auto a : s) {
			if (a == mex) mex++;
		}
		if (mex > mx) cout << sz(s) + k << '\n';
		else {
			s.insert((mex + mx + 1) / 2);
			cout << sz(s) << '\n';
		}
	}
}

 

 

C. Diamond Miner (*1200)

 

x축위에 n개의 점들이 있고, y축위에 n개의 점들이 있을 때, x축 위의 점과 y축 위의 점 각각 하나씩을 연결한 n개의 쌍이 만드는 선분의 길이의 합을 최소화하는 문제이다. 

 

x좌표의 절댓값들과 y좌표의 절댓값들을 각각 보관하여 정렬한 뒤, 앞에서부터 차례대로 매칭해주면 된다.

 

자세한 증명은 에디토리얼을 참고하면 되는데, 사실 proof by ac로 푼 사람이 대부분일 것 같다. 

나또한 대충 예시를 만들어보고 제곱근을 씌워줄 때는 최대한 큰 수를 씌워줄 때 수의 크기가 더 많이 줄어든다는 생각으로 코드를 구현했는데 예제 답이 나와서 제출을 했다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()

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<ll>X, Y;
		for (int i = 1; i <= 2*n; i++) {
			ll x, y; cin >> x >> y;
			if (x == 0) Y.push_back(abs(y));
			else X.push_back(abs(x));
		}
		sort(all(X)); sort(all(Y));
		double ans = 0;
		for (int i = 0; i < n; i++) {
			ans += sqrt(X[i] * X[i] + Y[i] * Y[i]);
		}
		cout << fixed;
		cout.precision(13);
		cout << ans << '\n';
	}
}

 

 

D. Let's Go Hiking (*1900)

 

입력으로 permutation이 주어진다.

그리고 A와 B 두 사람이 있고, A는 항상 이웃한 원소 중 현재보다 더 작은 값으로만 이동가능하고, B는 더 큰 값으로만 이동이 가능하다. 또한 A가 먼저 위치를 정하고 B가 그 다음 위치를 정한 다음 A부터 작한다. 

상대방이 현재 있는 위치로는 겹치게 이동할 수 없고, 더이상 움직이지 못하는 경우 상대방이 승리한다.

이때 A가 항상 이길 수 있는 위치가 몇가지인지 구하는 문제이다.

 

한가지 생각해야하는 부분은 원소가 permutation이기 때문에 A, B 모두 한쪽방향으로만 이동이 가능하다는 것이다.  

 

먼저, 각 위치별로 A가 왼쪽 또는 오른쪽으로 최대 몇칸 이동할 수 있는지 구한다. 

A가 a[i]에서 왼쪽으로 2칸 이동가능하다면, B는 a[i-2]에서 오른쪽으로 2칸 이동가능하다. 

a[i] > a[i-1] > a[i-2] 를 만족하기 때문이다. 

 

L[i] = i에서 시작해서 왼쪽으로 갈 수 있는 최대 거리

R[i] = i에서 시작해서 오른쪽으로 갈 수 있는 최대 거리라고 하자. 

 

L[i]가 홀수인 경우, B가 a[i - L[i]]에서 시작한다면 A는 왼쪽으로 이동해서는 승리할 수 없다. R[i]가 홀수인 경우도 마찬가지이다. 

따라서 L[i]와 R[i]가 모두 홀수인 경우에, B가 a[i - L[i]]와 a[i+R[i]] 둘 중 a[i]로 부터 더 멀리 있는 위치에서 시작하면 항상 B가 승리하기 때문에 적어도 하나는 짝수이어야 한다. 

 

하지만 둘 중 하나만 짝수인 경우 또한 A가 승리할 수 없다. 

일반성을 잃지 않고 L[i]가 짝수, R[i]가 홀수라고 해보자. 이 경우도 L[i] > R[i] or L[i] < R[i] 둘로 나뉘게 된다. 

L[i] > R[i]인 경우에는 B가 a[i - L[i] + 1]에서 시작하면 된다.

L[i] - 1 >= R[i]이고 L[i] - 1이 홀수이므로 A는 왼쪽으로 이동할 수 없고, 오른쪽으로 이동한다고 해도 B는 L[i] - 1만큼 이동가능하기 때문에 더 많이 이동할 수 있다. 

L[i] < R[i]인 경우에는 B가 a[i + R[i]]에서 시작하면 된다. 

 

결국 L[i]와 R[i] 모두 짝수이어야 한다. 미리 말하면 정확히 L[i] == R[i]인 경우여야 한다. 

L[i] > R[i]라고 가정해보면, 마찬가지로 B가 a[i - L[i] + 1]에서 시작하면 A가 이길 수 없다. 반대도 마찬가지이다.

 

그렇다면 항상 L[i] == R[i]인 경우이기만 하면 될까? 

A가 이동가능한 범위 밖에서 B가 시작했을 때 B가 더 많이 이동가능한 경우가 있는지도 고려를 해주어야 한다. 

 

(본대회때에는 ar[i] >= br[1] && al[i] >= bl[n] 조건을 빼먹어서 sys fail이 났다)

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
int p[100001];
int al[100001];
int bl[100001];
int ar[100001];
int br[100001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> p[i];
	for (int i = 2; i <= n; i++) {
		if (p[i] > p[i - 1]) al[i] = max(al[i], al[i - 1] + 1);
		if (p[i] < p[i - 1]) bl[i] = max(bl[i], bl[i - 1] + 1);
	}
	for (int i = n - 1; i >= 1; i--) {
		if (p[i] > p[i + 1]) ar[i] = max(ar[i], ar[i + 1] + 1);
		if (p[i] < p[i + 1]) br[i] = max(br[i], br[i + 1] + 1);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) bl[i] = max(bl[i - 1], bl[i]);
	for (int i = n - 1; i >= 1; i--) br[i] = max(br[i], br[i + 1]);

	for (int i = 2; i < n; i++) {
		if (al[i] % 2 == 0 && al[i] == ar[i]) {
			if (min(al[i], ar[i]) > max(bl[i], br[i]) && (ar[i] >= br[1] && al[i] >= bl[n])) cnt++;
		}
	}
	cout << cnt;

}