pushback

맨날 백준만 풀다가 처음으로 도전해본 Codefroce 

A. Split it!

https://codeforces.com/contest/1496/problem/A

식으로 멋지게 포장되어있지만 핵심은 입력받은 string의 앞에서부터 palindrome을 만족하는 string의 길이를 확인하면 된다.

예를 들어 8 2 pushahsup 가 입력으로 들어왔다고 가정해보자.

pushahsup

앞뒤로 4개의 알파벳이 palindrome을 만족하고 있다. 이 때, 주어진 k는 2이므로 우리는

s = p + u + shahs + u + p

  = pu + s + hah + s + up

  = pus + h + a + h + sup

문제에서 제시한 조건에 만족하는 3개의 s를 만들 수 있다. 

결국, 입력받은 string에서 palindrome을 만족하는 string의 길이를 count라고 한다면, count가 k보다 크거나 같으면  조건에 만족하는 s를 찾을 수 있고, 그렇지 않다면 불가능하다.

여기서 한가지 예외가 있는데, n이 짝수이고 k == n / 2인 경우를 생각해보자.

우리는 분명히 앞에서부터 k개의 palindrome을 만들고 \(a_{k+1}\)에 남은 substring을 넣어주어야 한다. 

하지만 n이 짝수이고 k == n / 2이라면, 입력받은 string에 상관없이 \(a_{k+1}\)은 empty string이 된다. 따라서 이 경우 무조건 NO를 출력해준다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MOD = 998244353;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	while (T--) {
		int n, k;
		string str;
		cin >> n >> k >> str;
        
		if (n % 2 == 0 && n / 2 == k) {
			cout << "NO\n";
			continue;
		}

		bool ans = true;
		int cnt = 0;
		for (int i = 0; i < n / 2; i++) {
			if (str[i] == str[n - 1 - i]) {
				cnt++;
			}
			else break;
		}
		if (cnt >= k) cout << "YES\n";
		else cout << "NO\n";
			
	}
	return 0;
}

B. Max and Mex

https://codeforces.com/contest/1496/problemB

테스트 중에 set을 이용하여 제시된 operation을 k번 하는 코딩을 했으나, k가 최대 10의 9승이라 당연히 TIME LIMIT.

테스트 끝나고 생각해보니, distinct number가 계속해서 늘어나는 경우는 mex(S)가 max(S)보다 큰 경우 밖에 없다.

mex(S)가 max(S)보다 작은 경우 operation은 몇번 하든 추가되는 숫자는 항상 같다. 왜냐하면 항상 mex(S)와 max(S) 중간에 있는 숫자가 추가되기 때문에, mex(S)나 max(S)가 바뀔 일이 없다.

결국,

mex(S)가 max(S)보다 크면, n + k

mex(S)가 max(S)보다 작고 \(\left \lceil \frac{mex(S) + max(S)}{2} \right \rceil \) 의 값이 이미 S에 존재하면, n

그렇지 않다면, n + 1 을 출력하면 된다.

max(S) = set에 마지막 원소, O(1)

mex(S) = set의 find 함수 이용, 0부터 하나씩 찾아본다. O(n * log n)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MOD = 998244353;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int num[100001] = { 0 , };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	while (T--) {
		int n, k;
		set<int> s;
		cin >> n >> k;
		int MEX = -1, MAX = 0, ans = 0;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
			s.insert(num[i]);
		}
		if (k == 0) {
			cout << n << '\n';
			continue;
		}

		auto it = s.end();
		it--;
		MAX = *it;
		while (s.find(++MEX) != s.end());

		if (MEX > MAX) cout << n + k << '\n';
		else {
			int add = (MAX + MEX + 1) / 2;
			if (s.find(add) != s.end()) cout << n << '\n';
			else cout << n + 1 << '\n';
		}
	}
	return 0;
}

C. Diamond Miner

https://codeforces.com/contest/1496/problem/C

간단하다.

0에 가까운 순서대로 mine과 miner를 매칭시켜주면 된다.

이 부분은 자명해서 자세한 설명은 생략.

sorting 후, 계산만 해주면 되기 때문에 O(n*log n)에 해결 가능하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> mine;
vector<int> miner;
bool compare(const int& a, const int& b) {
	if (abs(a) == abs(b))
		return a < b;
	return abs(a) < abs(b);
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		int n, x, y;
		cin >> n;
		mine.resize(n);
		miner.resize(n);
		for (int i = 0, j = 0; i + j < 2 * n;) {
			cin >> x >> y;
			if (x == 0)
				miner[i++] = y;
			if (y == 0)
				mine[j++] = x;
		}
		sort(mine.begin(), mine.end(), compare);
		sort(miner.begin(), miner.end(), compare);
		double sum = 0;
		for (int i = 0; i < n; i++)
			sum += sqrt(pow(mine[i], 2) + pow(miner[i], 2));
		cout.precision(10);
		cout << fixed << sum << '\n';


	}


	
	return 0;
}