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

 

2021.01.03. 15:00 virtual 참가 / performance = 1563 

 

 

[풀이]

 

1153A. Serval and Bus  (*1000)

 

버스별로 정류장에 처음 도착하는 시간과 배차간격이 주어질 때, 버스정류장에 t초에 도착했을 때 제일 먼저 탈 수 있는 버스를 구하는 문제이다. 

처음에 A번치고 생각보다 까다로웠으나, n이 100이고 t가 10만이기 때문에 각 버스별로 정류장에 도착하는 시간을 모두 구해줘도 무방하다.

 

나는 priority_queue를 이용하여 현재 pq에 담겨있는 버스들의 도착 시간 중에 제일 빠른 것을 확인해서,

t보다 작다면 배차간격만큼 더해줘서 다시 넣어주고, 처음으로 t보다 큰 값이 나온 경우에 출력을 해주었다. 

 

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, t; cin >> n >> t;
	priority_queue<pair<pii, int>> pq;
	for (int i = 1; i <= n; i++) {
		int s, d; cin >> s >> d;
		pq.push({ { -s, d }, i });
	}
	while (1) {
		int now = -pq.top().first.first;
		int plus = pq.top().first.second;
		int ans = pq.top().second;
		pq.pop();
		if (now >= t) {
			cout << ans;
			break;
		}
		else {
			pq.push({ {-(now + plus), plus}, ans });
		}
	}
}

 

1153B. Serval and Toy Bricks  (*1200)

 

옆면과 앞면, 윗면에서 본 입체 도형이 주어질 때, 실제로 가능한 입체 도형을 구하는 문제이다. 

옆면과 앞면에서 각각 봤을 때 각 열 별로 최대 높이인 블록의 높이가 저장되므로,

ans[i][j]에는 옆면의 i번째 값과 앞면의 j번째 값 중 작은 값을 골라주면 된다. 

 

#include<bits/stdc++.h>
using namespace std;
int a[101], b[101], A[101][101], ans[101][101];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, m, h; cin >> n >> m >> h;
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> A[i][j];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (A[i][j] == 1) ans[i][j] = min(a[j], b[i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cout << ans[i][j] << ' ';
		cout << '\n';
	}
}

 

1153C. Serval and Paranthesis Sequence  (*1700)

 

'(', ')', '?'로 이루어진 문자열이 주어지고, '?'자리에는 '('와 ')'가 올 수 있다.

전체 문자열이 'correct parenthesis sequence'가 되어야 하고, prefix들은 되면 안 된다. 

따라서 먼저, 문자열의 길이가 홀수이면 correct할 수 없고, 주어지는 문자열에서 '('의 개수가 절반을 넘거나 ')'의 개수가 절반을 넘어도 correct할 수 없다.

이 경우들을 모두 제거해주고, prefix들이 correct할 수 없도록 '?'를 앞에서부터 최대한 '('로 바꿔준다. 

최종적으로 바꾼 후에 만들어진 문자열이 문제 조건을 만족하는지 다시 체크해준다.

 

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	string s; cin >> s;
	if (n % 2) return cout << ":(", 0;
	int l = 0, r = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(') l++;
		else if (s[i] == ')') r++;
	}
	if (l > n / 2 || r > n / 2) return cout << ":(", 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '?') {
			if (l < n / 2) {
				s[i] = '(';
				l++;
			}
			else s[i] = ')';
		}
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(') cnt++;
		else {
			cnt--;
			if (i != n - 1 && cnt <= 0) return cout << ":(", 0;
		}
	}
	cout << s;
} 

 

1153D. Serval and Rooted Tree (*1900)

 

이 문제의 풀이를 이해하는데만 1시간 넘게 걸린 것 같다. 좋은 문제임에 틀림없지만 너무 어렵다...

문제를 요약하자면, k개의 리프노드에 1부터 k까지 하나씩 부여를 할 수 있다. 

그리고 각 노드별로 min인지 max인지 주어져있고, min인 경우에는 자신의 자식들 중 최솟값을 가져오고 max인 경우에는 최댓값을 가져온다. 

최종적으로 루트노드인 1번 노드가 가질 수 있는 최댓값을 구하는 것이다. 

핵심적인 아이디어는, min과 max에 관계없이 자신이 최대가 되기 위해서는, 자식들의 값이 최대가 될수록 좋다는 것이다.

그러기 위해서 min을 취했을 때와 max를 취했을 때 자손들에서 지워지게 되는 노드의 수를 구한다.

 

문제의 예시를 확인해보자. 

먼저, 리프노드에 적혀있는 max와 min은 아무 의미 없으므로 고려하지 않는다. 

 

3번 노드만 따로 보면, min이기 때문에 자식 노드의 값 중에서 최솟값을 가져온다. 

이때, 자식노드인 6, 7, 8번 노드에 배정되는 값을 각각 a, b, c라고 해보자.

일반성을 잃지 않고 a < b < c라고 가정하면, 3번 노드에는 a가 배정되게 된다.

따라서 b와 c는 절대 1번 노드의 값이 될 수 없다.

 

즉, 어떤 숫자가 배정되는지와 상관없이 3번 노드로 올라올 땐 2개의 수는 제외되고,

1번 노드가 최대가 되기 위해서는 3번 노드가 클수록 좋으며,

3번 노드가 최대가 되기 위해서는 제외되는 수인 b와 c가 최대한 작아질수록 좋기 때문에 a+1, a+2가 되는 게 최적이다. 

그러므로 3번노드의 최댓값은

리프 노드의 수 - 지워지는 노드의 수 = 리프 노드의 수 - (자식의 수 -1) = 3 - 2 = 1을 만족한다. 

 

이를 임의의 노드에 대해서 정리하면 min이 배정된 노드에서는

(자식 노드를 루트로 하는 서브 트리에서의 지워지는 노드의 수) + (자식 노드 수 - 1) 만큼 지워지게 된다. 

 

max가 배정된 노드에서는 어떨까? 

자식들 중 최댓값을 가져와야 하는데, 이 최댓값이 제일 크기 위해서는

자식들을 루트로 하는 서브트리들 중에서 지워지는 노드의 수가 가장 적은 자식을 고르면 된다. 

해당 서브트리의 지워지는 노드 수를 m개라고 하면, 해당 서브 트리의 리프 노드에 k ~ k-m+1 값을 각각 부여해주는 게 최적이기 때문이다. 

 

따라서 아래와 같이 코드가 만들어진다. 

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()

using namespace std;
vector<int>adj[300001];
int flag[300001];
int leaf = 0;
int dfs(int u) {
	if (sz(adj[u]) == 0) { //leaf
		leaf++;
		return 0; //지워주는 노드 x
	}
	int res = (flag[u]? 1e6 : 0); 
    	//min인 경우에는 지워지는 노드들의 합, max인 경우에는 지워지는 노드의 최솟값
	for (int v : adj[u]) {
		if (flag[u]) res = min(res, dfs(v));
		else res += dfs(v);
	}
    //min인 경우에는 자식들 중 1개를 제외하고 모두 지워지므로 해당 개수 추가
	return (flag[u] ? res : res + sz(adj[u])-1);
}
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 >> flag[i];
	for (int i = 1; i < n; i++) {
		int a; cin >> a;
		adj[a].push_back(i + 1);
	}
	int k = dfs(1);
	cout << leaf - k; 
}