2020 UCPC 예선 후기 및 문제 풀이

 

https://ucpc.acmicpc.net/info

UCPC 2020

올해 처음이자 마지막으로 2020 UCPC에 참가를 하였습니다 (석박 졸업 때문에..)

먼저 좋은 대회를 열어주신 출제자, 검수자 및 주체자 모든 분들께 감사인사를 드립니다.

https://www.acmicpc.net/board/view/54041(문제와 풀이를 shiftpsh님께서 올려주셨습니다)

글 읽기 - UCPC 2020 예선 종료

문제수는 10문제였고 그 중 A, D, G, H를 해결했습니다. J번은 다 끝나고 초기화를 잘못 시킨걸 발견하고 맞았더라는..ㅠ

주말에 부랴부랴 모여서 문제를 출력하여 풀수있는 문제를 선별하였습니다.

 

문제 A. 수학은 비대면강의입니다. (백준 19532)

19532번: 수학은 비대면강의입니다

ax + by =c 와 dx + fy = e 두 일차 방정식이 주어질 때 두 방정식을 만족하는 x와 y가 유일하며 항상 정수임이 보장될때 x와 y를 찾는 문제였습니다. 

조건때문에 쉬운문제였으며 범위가 -999 ~ 999 로 naive한 방법으로 O(N^2)안에 해결 가능합니다.

#include <iostream>

using namespace std;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
   int a,b,c,d,e,f;
   cin >> a >> b >> c >> d >> e >> f;
   for (int x = -999; x < 1000; x++) {
      for (int y = -999; y < 1000; y++) {
         if (a * x + b * y == c && d * x + e * y == f) {
            cout << x << " " << y;
            return 0;
         }
      }
   }
} /* A번 코드 */

다른 방법으로는 x, y가 유일하므로 [a b, d f]의 역함수를 구하여 [c e]와 행렬곱을 수행하여 x, y를 구할 수 있습니다. (af-bd는 0이 아니므로) 

 

 

H. 사과나무 (백준 19539)

19539번: 사과나무

사과나무를 1 자라게 하는 물뿌리개 A와 2 자라게 하는 물뿌리개 B 두개를 동시에 사용하여 높이가 0인 처음 N개의 사과나무를 주어진 N개의 나무 높이로 만들 수 있는지 확인하는 문제였습니다. (빈 땅에 물을 뿌릴 수 없으므로, A와 B를 사용한 횟수가 같아야함)

접근 방법은 주어진 N개의 입력의 총합이 3의 배수여야 하며, 최소 필요한 물뿌리개 A를 뿌리는 횟수 이상으로 B 물뿌리개를 뿌릴 수 있어야 합니다.

예를 들어 나무의 높이가 1 3 1 3 1로 주어진다면 높이가 홀수인 나무가 5개 이므로 A는 최소 5번 뿌려야하고, B도 5번 이상 뿌릴 수 있어야합니다. 이 경우는 B 물뿌리개를 5번 뿌릴 수 없기 때문에 답이 NO가 됩니다.

저는 먼저 B를 뿌릴 수 있는 최대 횟수 t_num와 A의 최소 횟수 o_num를 구했습니다. 

   int t_num = 0;
   int o_num = 0;
   for (int i = 0; i < n; i++) {
      t_num += arr[i] / 2;
      o_num += (arr[i] & 1 ? 1 : 0);
   }

만약 t_num이 o_num보다 작다면 만들 수 없는건 위에서 증명했고, 작거나 같다면 t_num - o_num의 차이 dif를 구하여 dif가 3의 배수인지 확인합니다.

만약 dif가 3의 배수라면 B를 뿌리는 횟수를 두개의 A로 나누어 뿌리면 되므로 YES 이고 이외에는 NO 를 출력하면 됩니다. ex) B B B -> B B A A 

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

using namespace std;
typedef long long ll;


int n;
int arr[100001];

int main() {
   ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
   cin >> n;
   int t = 0;
   for (int i = 0; i < n; i++) {
      cin >> arr[i];
      t += arr[i];
   }
   if (t % 3) {
      cout << "NO";
      return 0;
   }
   int t_num = 0;
   int o_num = 0;
   for (int i = 0; i < n; i++) {
      t_num += arr[i] / 2;
      o_num += (arr[i] & 1 ? 1 : 0);
   }
   if (t_num < o_num) {
      cout << "NO";
      return 0;
   }
   int dif = t_num - o_num; // 2 를 dif 번 더 뿌려야함 
   if (dif % 3) {
      cout << "NO";
   }
   else {
      cout << "YES";
   }

} /* h */

D. ㄷㄷㄷㅈ (백준 19535)

19535번: ㄷㄷㄷㅈ

노드 4개로 구성되는 트리는 아래와 같은 두 타입의 트리로 구성될 수 있습니다. 빨간색 표시한 부분은 편의상 중간 노드라고 부르겠습니다.

왼쪽 D, 오른쪽 G 그래프

정점 N개와 간선 N-1 개로 구성된 트리가 주어지면, 전체 트리에서 나오는 ㄷ 의 개수와 ㅈ의 개수를 계산하여 ㄷ가 ㅈ에 3배만큼 많으면 DUDUDUNGA, 3배보다 많으면 D, 이외에 G를 출력하는 문제입니다.

편의상 1번 정점을 루트로 잡고 DFS를 통해 부모와 자식의 위상을 강제로 정한뒤 각 노드에서 구할 수 있는 D와 G의 개수를 구해가면 됩니다. 이를 위하여 c_num[i]를 i번째 노드와 직접 연결된 자식의 수를 저장하였습니다.

i번째 노드에서 D 그래프의 개수를 구하는 경우는 i번째 노드가 중간노드인 아래 두가지 경우만 고려합니다. (ㄷ그래프의 개수를 구할때 i번째 노드를 시작점으로 하면 i번째 노드의 자식의 자식의 c_num까지 탐색해야하므로)

1) i번째 노드의 부모로부터 시작하는 D 그래프를 구성하는 경우

모든 자식노드 j에 대하여 c_num[j] 의 합 (1번 노드는 부모가 없으므로 스킵)

2) 자신의 자식 노드로 부터 시작하여 자식노드로 끝나는 D 그래프를 구성하는 경우

모든 자식노드 j에 대하여 (c_num[i] - 1)*c_num[j] 의 합

 

i번째 노드에서 G 그래프의 개수를 구하는 경우는 i번째 노드가 중간노드인 경우만 고려하면 됩니다. 이때 두가지 경우를 고려해야하는데, 

1) 부모와 연결된 간선을 포함하여 G 그래프를 구성하는 경우

c_num[i] 개 중에 2개를 고르는 경우 (1번 노드는 부모가 없으니 스킵)

2) 자식노드와 연결된 간선으로만 G 그래프를 구성하는 경우

c_num[i] 개 중에 3개를 고르는 경우 

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

using namespace std;
typedef long long ll;


int n;
vector<int> v[300001];
int c_num[300001] = { 0, }; // 자기 자식의 개수
ll dnum = 0;
ll gnum = 0;
inline ll ncr(ll n, ll r) {
	if (n < r) {
		return 0;
	}
	if (r == 2LL) {
		return n * (n - 1) / 2LL;
	}
	if (r == 3LL) {
		return n * (n - 1) * (n - 2) / 6LL;
	}
}
void dfs(int node, int p) {
	for (auto nxt : v[node]) {
		if (nxt != p) {
			c_num[node] += 1;
			dfs(nxt, node);
		}
	}
	if (~p) {
		// g 인데 한쪽을 부모로 하는 경우
		gnum += ncr(c_num[node], 2LL);
		// d 인데 한쪽을 부모로 하는 경우
		for (auto nxt : v[node]) {
			if (nxt != p) {
				dnum += c_num[nxt];
			}
		}
	}

	// g 인데 자기 자식으로만 하는 경우
	gnum += ncr(c_num[node], 3LL);
	// d 인데 자기 자식으로만 하는 경우
	for (auto nxt : v[node]) {
		if (nxt != p) {
			dnum += c_num[nxt] * (c_num[node] - 1);
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, -1);
	if (dnum == gnum * 3) {
		cout << "DUDUDUNGA";
	}
	else {
		if (dnum > gnum*3) {
			cout << "D";
		}
		else {
			cout << "G";
		}
	}
} /* D번 코드*/

 

G. 루머 (백준 19538)

19538번: 루머

이웃한 사람들 중 절반 이상이 루머를 믿어야 대상이 루머를 믿을때, N명의 사람이 루머를 믿는 시간 (혹은 끝까지 믿지않는 경우 -1)을 출력하는 문제입니다.

출처 : https://www.acmicpc.net/problem/19538

 

루머를 믿는 시점을 기록하여 방문체크를 하므로써 해당 사용자가 루머를 믿은 시간이 현재 시간 t보다 작은 경우만 카운트해서 BFS를 진행하면 됩니다. 제한시간이 10초여서 고민없이 코딩했습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
typedef long long ll;


int n;
vector<int> v[200001];
int r[200001];
queue<pair<int, int> > q;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		while(1){
			int a;
			cin >> a;
			if (!a) break;
			v[i].push_back(a);
		}
	}
	memset(r, -1, sizeof(r));
	int m;
	cin >> m;
	for (; m--;) {
		int num;
		cin >> num;
		r[num] = 0;
		q.push({ num,0 });
	}
	while (!q.empty()) {
		int node = q.front().first;
		int t = q.front().second; q.pop();
		for (auto nxt : v[node]) {
			if (r[nxt] == -1) {
				int cnt = 0;
				for (auto _nxt : v[nxt]) {
					if (~r[_nxt] && r[_nxt] <= t) {
						cnt += 1;
					}
				}
				int _size = v[nxt].size();
				int half = _size / 2 + (_size & 1 ? 1 : 0);
				if (cnt >= half) {
					r[nxt] = t + 1;
					q.push({ nxt,t + 1 });
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << r[i] << " ";
	}
} 

 

J. 역학 조사 (백준 19541)

19541번: 역학 조사

제일 골머리를 앓았던 문제입니다. m개의 모임이 순서대로 열리고 마지막 모임 후 N명의 사람에 대한 최종 감염된 사실이 주어졌을 때, 초기 감염자를 역추적 가능한지 여부를 묻는 문제입니다.

모임을 역순으로 거슬러 올라가면서 해당 모임에서 최종 비감염자가 있는 경우, 해당 모임에 참여한 모든 인원들은 초기 감염자가 될 수 없음은 자명합니다. 처음 모임까지 거슬러 올라가면서 초기 감염자가 될 수 없는 후보에서 제외시킵니다. 이 후, 남은 후보들을 초기감염자로 가정한 뒤, 모임을 시간 순서대로 진행하여 감염시켜가면서 입력으로 주어진 최종 감염 사실과 비교하여 다르면 NO, 같으면 YES를 출력하면 됩니다. 

위의 경우, 모임 5에서 1, 2, 3번 중 1, 3 번이 최종 비감염자이기 때문에 2번은 모임 5번 이후 감염된 것이므로 역추적 할 수 없습니다.

만약 모임이 4번까지만 있었다면

모임 4번 참가자 중 최종 비감염자가 없기 때문에 아무도 초기 감염자 후보에서 제외되지 않습니다.

후보 [ 2 4 5 ]

모임 3번으로 거슬러 올라가면, 참가자 중 1번이 최종 비감염자 이므로 이 당시 2번과 4번 참가자는 비감염 상태라는 것을 알 수 있으므로 1, 2, 4번을 초기 감염자 후보에서 제외시킬 수 있습니다.

후보 [ 5 ]

모임 2번에서 3번은 최종 비감염자이며, 4번은 모임 3번 이후로 감염된 것을 확인하였기 때문에 모임 2번 당시는 감염자가 아닌 상태입니다.

모임 1번에서 2, 3, 4번 모두 이미 비감염자 상태입니다.

즉, 위 예제의 정답은 YES, 0 0 0 0 1 이되며, 2번 4번은 모임 4에서 감염된 사실을 알 수 있습니다.

최종 감염자가 모임에 안나타 나는 경우를 고려하지 못해서 맞왜틀을 시전하다가 참교육 당한 문제입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
typedef long long ll;

int n, m;
vector<int> v[100001];
int infe[100001];
int init[100001];
int last[100001];
int check[100001] = { 0, };
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			int a;
			cin >> a;
			v[i].push_back(a);
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> infe[i];
		last[i] = infe[i];
		init[i] = infe[i]; // 초기 감염자일 경우 1
	}
	for (int i = m - 1; i > -1; i--) {
		int no = 0;
		for (auto user : v[i]) {
			if (infe[user] == 0) {
				no = 1;
				break;
			}
		}
		if (no) {
			for (auto user : v[i]) {
				init[user] = 0;
				infe[user] = 0;
			}
		}
	}
	// init 은 초기 감염자 후보
	for (int i = 1; i <= n; i++) {
		infe[i] = init[i]; 
	}
	for (int i = 0; i < m; i++) {
		int yes = 0;
		for (auto user : v[i]) {
			if (infe[user]) {
				yes = 1;
			}
		}
		if (yes) {
			for (auto user : v[i]) {
				infe[user] = 1;
			}
		}
	}
	int flag = 1;
	for (int i = 1; i <= n; i++) {
		if (infe[i] != last[i]) {
			flag = 0;
		}
	}
	if (flag) {
		cout << "YES\n";
		for (int i = 1; i <= n; i++) {
			cout << init[i] << " ";
		}
	}
	else {
		cout << "NO";
	}
}

마지막 역학 조사를 제외한 나머지 4문제를 AC 받아서 본선에 진출하였습니다만 공부가 많이 필요할 거 같습니다..

처음이자 마지막 UCPC! 좋은 경험이였습니다.

 

본선 A번

2020/08/06 - [알고리즘] - [UCPC] A번 전단지 돌리기, 백준 19542

[UCPC] A번 전단지 돌리기, 백준 19542

본선 B번

2020/08/18 - [알고리즘] - [UCPC] B번 던전 지도, 백준 19543

[UCPC] B번 던전 지도, 백준 19543