[CF] Round #692 (Div. 2, based on Technocup 2021) _ 201220

(2020년 12월 21일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #692 (Div. 2, based on Technocup 2021 Elimination Round 3) - Codeforces

 

A.

그냥 구현.

string 입력받고 뒤에서부터 세주면 된다

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	string s;
	int i;
	int cnt;

	cin >> T;
	while (T--) {
		cin >> N;
		cin >> s;
		cnt = 0;
		for (i = N - 1; i >= 0; i--) {
			if (s[i] == ')') {
				cnt++;
			}
			else {
				break;
			}
		}
		if (cnt > N - cnt) {
			cout << "Yes" << '\n';
		}
		else {
			cout << "No" << '\n';
		}
	}

	return 0;
}

​

B.

와 진짜 멘붕 왔다.

근데 효규가 이걸 7분만에 풀어서 당황했는데

​

그냥 N부터 1씩 증가해나가면서 확인하는 게 답이다..

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	string s;
	int i;
	int cnt;

	cin >> T;
	while (T--) {
		cin >> N;
		cin >> s;
		cnt = 0;
		for (i = N - 1; i >= 0; i--) {
			if (s[i] == ')') {
				cnt++;
			}
			else {
				break;
			}
		}
		if (cnt > N - cnt) {
			cout << "Yes" << '\n';
		}
		else {
			cout << "No" << '\n';
		}
	}

	return 0;
}

​

C.

그리고 또 멘붕.

처음에는, 빈 공간이 있는지 찾고

빈 공간으로 가면 되는 걸 보내고

그걸 계속 반복하는 방법으로 풀었는데

TLE가 났다.

​

결국 이 문제는

X를 Y로 보낼 때 몇 번 이동시켜야 하는지 보는거니까

방향그래프로 나타낼 수 있고,

그렇게 나타낸 그래프는 특이하게도 모든 노드가 들어오는 간선, 나가는 간선이 최대 하나만 존재한다.

​

만약 사이클이 없으면 그냥 차례대로 다 옮겨주면 되기 때문에

옮기는 횟수는 (노드 수) - 1로 하면 되고

사이클이 있으면 그 중 하나를 다른 곳으로 일단 보내고, 차례대로 이동시켜야 한다.

그래서 옮기는 횟수는 (노드 수) + 1.

이 문제의 그래프에서는 사이클에서 노드 수 == 간선 수니까

정확하게 말하면 옮기는 횟수가 (간선 수) + 1인데

(노드 수) + 1로 구하면 된다.

​

그럼 이걸 어떻게 하느냐!!

Union-Find로 하면 된다

​

merge할 때, 둘 중 번호가 작은 것을 대표 노드로 업데이트 하고

cnt도 처리해줬다.

​

그리고 유의할 점은

input으로 X, Y 받을 때

X == Y 이면 continue 하는거 놓치면 안 된다.

여기서 처리 안 하면, 그 뒤에서 복잡해진다...ㅎ

vector<int> par;
vector<int> cnt;
int getPar(int);
void merge(int, int);

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N, M;
	int X, Y;
	int ans;
	int i;

	cin >> T;
	while (T--) {
		cin >> N >> M;
		par.clear();
		par.resize(N + 5, -1);
		cnt.clear();
		cnt.resize(N + 5, 1);

		set<int> nums;
		ans = 0;
		while (M--) {
			cin >> X >> Y;
			if (X == Y) {
				continue;
			}
			nums.insert(X);
			nums.insert(Y);
			if (getPar(X) == getPar(Y)) {
				ans += cnt[getPar(X)] + 1;
				cnt[getPar(X)] = 0;
			}
			else {
				merge(X, Y);
			}
		}

		for (auto iter = nums.begin(); iter != nums.end(); iter++) {
			i = *iter;
			int temp = getPar(i);
			if (cnt[temp]) {
				ans += cnt[temp] - 1;
				cnt[temp] = 0;
			}
		}

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

	return 0;
}

int getPar(int x)
{
	if (par[x] == -1) {
		return x;
	}
	return par[x] = getPar(par[x]);
}

void merge(int a, int b)
{
	a = getPar(a);
	b = getPar(b);
	if (a > b) {
		swap(a, b);
	}

	if (a != b) {
		cnt[a] += cnt[b];
		cnt[b] = 0;
		par[b] = a;
	}
}