[Codeforce] Educational Codeforces Round 114 (Rated for Div. 2) 풀이

A : Regular Bracket Sequences (0:20)

---

    n 을 입력 받았을 때, n 쌍의 괄호가 만들어지는 경우 중 n 개를 출력하는 문제이다. 백트래킹 개념으로 풀려고 접근을 했는데 흐름이 머리 속에서 바로 그려지지 않아서 여러 방법으로 시도하다가 시간이 오래 걸린 문제이다.

 

#include <iostream>
#include <vector>

using namespace std;

int ans;

void bracket(vector<char> &s, int l, int r)
{
	if (ans == 0)
		return;

	if (l == 0 && r == 0)
	{
		for (int i = 0; i < s.size(); ++i)
			cout << s[i];
		cout << '\n';

		--ans;
	}

	if (l < r)
	{
		s.push_back(')');
		bracket(s, l, r - 1);
		s.pop_back();
	}

	if (l > 0)
	{
		s.push_back('(');
		bracket(s, l-1, r);
		s.pop_back();
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<char> s;

	int t, n;

	cin >> t;

	while (t--)
	{
		cin >> n;
		ans = n;
		bracket(s, n, n);
	}
}

 

 

B : Combinatorics Homework (0:42)

---

    A와 B, 그리고 C 의 개수를 입력 받아 나열했을 때, 함께 입력받은 m 번만큼 연속되는 짝이 있을 수 있는지 구하는 문제이다. 처음에는 next_permutaion 으로 모든 경우를 고려하면 아슬아슬하게 될 것 같아서 구현해봤는데 TLE 가 나와서 다시 구현했다. 이것도 여러번 풀어서 시간이 오래 걸렸다. 아직 대회 문제를 많이 안 풀어봐서 정석적인 방법을 바로 떠올리지 못하여 해매는 것 같다.

 

   개념은 다음과 같다. 우선 m 이 가장 큰 경우는 3가지가 구분되어 정렬 되어있을 때이며, 그 크기는 (a - 1) + (b - 1) + (c - 1) 와 같다. 다음으로 m 이 가장 작은 경우는 a, b, c 를 가장 개수가 많은 것과 나머지로 구분하여 가장 개수가 많은 것을 나열한 뒤, 그 사이에 나머지 값들을 채워 넣는다고 생각했다. 따라서 m 이 가장 작은 경우는 (개수가 가장 많은 값의 개수 - 1) - (나머지 값의 개수의 합) - 1 이다. -1 을 하는 이유는 사이에 들어갈 수 있는 개수이기 때문이다. Ex) a 가 3 이고 가장 개수가 많다면, A( )A( )A 로 사이에 들어갈 수 있는 개수는 2개이다. 이렇게 해서 가능한 m 의 범위 안에 입력받은 m 이 있다면 "YES"를 출력하도록 했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	long long t, m, max_m, min_m;
	vector<long long> letter(3,0);

	cin >> t;

	while (t--)
	{
		cin >> letter[0] >> letter[1] >> letter[2] >> m;

		max_m = letter[0] + letter[1] + letter[2] - 3;
		
		sort(letter.begin(), letter.end());

		if (letter[2] - 1 < letter[0] + letter[1])
			min_m = 0;

		else
			min_m = letter[2] - letter[1] - letter[0] - 1;

		if (m <= max_m && m >= min_m)
			cout << "YES\n";

		else
			cout << "NO\n";
	}
}

 

 

C : Delete Two Elements (1:03)

---

    이건 그래도 lower_bound 와 upper_bound 를 이용해서 깔끔하게 풀었다! 히히~ 문제는 수열이 주어졌을때 수열의 수 중 2개를 제외해도 평균값이 변하지 않을 때, 제외할 수 있는 조합의 개수를 구하는 문제이다. 정렬한 뒤 하나씩 탐색하여 더했을 때 평균 * 2 가 되도록하는 수의 개수를 찾아서 ans 에 더해줬다. 다만 부동소수점 오류를 고려한다고 삽질을 하고, 형변환을 안해서 틀리고, 별 이상한 삽질 때문에 20분만에 푼 문제를 40분동안 고쳤다 ㅠㅠ 계속 하다보면 좋아지겠지..?

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<unsigned long long> arr;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	unsigned long long t, n, sum, ans;
	int address, next;
	double ave;
	
	cin >> t;

	while (t--)
	{
		cin >> n;

		sum = ans = 0;
		arr.assign(n, 0);

		for (int i = 0; i < n; ++i)
		{
			cin >> arr[i];
			sum += arr[i];
		}

		ave = (double)sum / n;

		sort(arr.begin(), arr.end());
	
		for (int i = 0; i < n; ++i)
		{
			address = lower_bound(arr.begin() + i + 1, arr.end(), ave * 2 - arr[i]) - arr.begin();
			next = upper_bound(arr.begin() + i + 1, arr.end(), ave * 2 - arr[i]) - arr.begin();
			
			ans += next - address;
		}

		cout << ans << '\n';
	}
}

 

 

D : Training Session (대회 이후 1:52 동안 풀어서 TLE 받고, 풀이 봄)

---

    사실 감이 잘 안 와서 TLE 나올 거 알았는데도 그냥 풀고, 풀이를 봤다. 유튜브에서 봤는데 정리한 내용을 이미지로 첨부하겠다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	int t, n;
	long long ans, topic_2, difficulty_2;

	vector<pair<int, int>> topic, difficulty;

	cin >> t;

	while (t--)
	{
		cin >> n;

		topic.resize(n);
		difficulty = topic;

		ans = 1LL * n * (n - 1) * (n - 2) / 6;

		for (int i = 0; i < n; ++i)
		{
			cin >> topic[i].first >> topic[i].second;

			difficulty[i].first = topic[i].second;
			difficulty[i].second = topic[i].first;
		}

		sort(topic.begin(), topic.end());
		sort(difficulty.begin(), difficulty.end());

		for (int i = 0; i < n; ++i)
		{
			topic_2 = upper_bound(topic.begin(), topic.end(), make_pair(topic[i].first + 1, 0)) - lower_bound(topic.begin(), topic.end(), make_pair(topic[i].first, 0)) - 1;
			difficulty_2 = upper_bound(difficulty.begin(), difficulty.end(), make_pair(topic[i].second + 1, 0)) - lower_bound(difficulty.begin(), difficulty.end(), make_pair(topic[i].second, 0)) - 1;

			ans -= (topic_2 * difficulty_2);
		}

		cout << ans << '\n';
	}
}

 

 

후기

---

    오랜만에 코드포스 VP 를 했는데, 바보가 된 것 같으면서도 성장한 게 느껴진다. 몇 달전에는 Div. 3 에서 A,B 밖에 못 풀었는데 조금 늦긴 해도 Div. 2 에서 C 까지는 자력으로 풀 수 있으니까 기분이 좋다. 단기적인 목표는 C 까지 안정적으로 푸는 것이다! 화이팅!

 

    이현수 그만 기만해~