티스토리 뷰

ICPC/World Finals

ACM ICPC World Finals 2016

전명우 2016.06.18 00:31

문제 링크


C. Ceiling Function


$K$개의 노드로 구성된 Binary Search Tree가 $N$개 주어진다. 이 때 서로 다른 모양을 갖는 BST의 개수를 구하는 문제다.


구조체를 써서 BST를 구현하고 두 노드에 대해 각 노드를 루트로한 서브트리가 같은지 비교해주는 재귀 함수를 구현하여 쉽게 해결할 수 있다.


코드 보기


E. Forever Young


수 $Y$를 $b$ 진법으로 나타냈을 때, 0부터 9 사이의 수로 이루어져야하고, 그 수를 10진수처럼 읽었을 때 $L$이상이어야 한다. 이 때 가능한 $b$ 중 최대값을 구하는 문제다.


우선 $b$가 충분히 큰 수인 경우, $b$진법의 자리수가 적을 것이다. 자리수가 5 이하인 경우, $b$진법으로 나타냈을 때 수를 정해놓고 이분탐색을 통해 해당 $b$를 계산하는 방법으로 해결할 수 있다. 만약 $b < 10^{18 / 4} \leq 31,623$으로 충분히 작은 경우에 대해서는 직접 $b$를 정해놓고 확인할 수 있다. $b \geq 10$ 이므로 문자열을 통한 대소비교를 할 필요가 없다.


코드 보기


L. Swap Space


$N$개의 디스크가 있다. 각 디스크에 대해 포맷 전에 포함하는 데이터 용량은 $a$이며, 포맷 후 디스크의 용량은 $b$이다. 각 디스크는 포맷 전에 포함되어있는 데이터를 다른 곳으로 옮겨 백업해야한다. 이 때, 모든 디스크를 포맷하기 위해 마련해야하는 추가 공간의 최소 용량을 구하는 문제다.


디스크를 두 종류를 나눠 생각할 수 있다.

$a \leq b$ 인 경우에 대해 먼저 생각하자. $a$가 작은 순서로 정렬한 뒤에 순서대로 처리한다. 남은 공간이 $a$보다 적으면 추가 공간을 새로 구입하고 아니면 그 공간에 데이터를 백업하고 포맷하는 방식으로 처리한다. 이 때 디스크를 포맷할 때마다 $b - a$ 만큼 총 공간이 증가하므로 최적이다.

이제 $a > b$ 인 경우에 대해 해결하면 된다. 포맷을 다 마친 최종 상태에서 거꾸로 생각해보자. 마지막 포맷을 번복하면 $a - b$ 만큼 총 공간이 증가하는 꼴이 될 것이다. 이 때 추가 공간을 최소로 구입하기 위해서는 $b$가 작은 것을 뒤에 포맷하면 된다. $a \leq b$ 인 경우와 비슷하게 포맷을 $b$의 역순으로 해주면 이 때도 최적이다.


코드 보기


G. Oil


서로 만나지 않는 수평 선분 $N$개가 있다. 수평이 아닌 직선을 그어 직선이 지나는 수평 선분 길이 합의 최대값을 구하는 문제다.


답이 되는 직선이 있다고 하자. 이 직선이 지나는 선분들이 유지되도록 적절히 좌우로 움직이면 어떤 선분의 끝 점에 걸치도록 할 수 있다. 즉, 답이 되는 직선 중 하나는 어떤 선분의 끝 점을 지난다.

이 특성을 이용해서 선분의 끝 점 중 하나를 정한다. 그리고 이 점을 지나는 직선 중 지나는 수평 선분 길이 합이 최대가 되는 직선을 구한다. 이 때 직선을 180도 돌리는 것 처럼 보이지만, 아래 부분에 해당하는 선분들을 점대칭 시켜서 윗부분으로 옮기면 반직선을 180도 돌리는 것처럼 되어 쉽게 해결할 수 있다. 이 문제는 결국 구간들이 주어지고 지나는 구간 길이 합이 제일 큰 수직선을 구하는 문제와 같게 된다.


코드 보기


K. String Theory


작은 따옴표(')가 들어있는 문자열 중에 특정 문자열을 k-quotation이라고 정의한다. 문제에서 문자열에서 연속된 작은 따옴표 수들이 수열로 주어질 때, 문자열이 k-quotation인 경우 가장 큰 k를 구하는 문제다.


k-quotation의 특징은 양 옆에 k개의 연속된 작은 따옴표와 그 사이에 (k-1)-quotation이 나열되어 있다는 것이다. 따라서 만약 문자열이 k-quotation이라면 작은 따옴표가 왼쪽에 연속해서 k개, k-1개, ..., 2개, 1개 그리고 오른쪽에 1개, 2개, ..., k-1개, k개 이런식으로 있어야한다. 이제 그 사이 있는 따옴표 배열에 따라 k-quotation인지 아닌지가 결정되는 것으로 생각할 수 있다. 하지만 아주 단순하게 그 사이에 있는 작은 따옴표의 개수가 짝수라면 이 문자열은 k-quotation이다. 왜냐하면 그 사이에 있는 모든 작은 따옴표를 모두 1-quotation으로 봐도 무방하기 때문이다. 만약 그 사이에 있는 작은 따옴표의 개수가 홀수라면 전체 따옴표의 개수가 홀수가 되기 때문에 k-quotation이 될 수 없다.


코드 보기


D. Clock Breaking


4개의 숫자를 표시하는 LED 시계가 있다. 어떤 부분은 항상 꺼져있고, 어떤 부분은 항상 켜져있고, 어떤 부분은 잘 동작한다. 어떤 시각부터 연속해서 n분 동안의 상태가 입력으로 주어졌을 때, 시계의 각 LED판의 상황을 구하는 문제다.


가능한 모든 시작시각에 대해 테스트를 해보고 판의 상황을 유추해보면되는 구현 문제다. 각 부분에 대해 상황을 비트로 표현하면 보다 쉽게 해결할 수 있다.


코드 보기


A. Balanced Diet


매 순간 다이어트 목적에 맞게 사탕을 먹을 때, 추가로 먹을 수 있는 사탕 개수의 최대값을 구하는 문제다.

무슨 사탕을 먹는 것이 제일 좋을까? 종류에 따라 너무 빨리 먹어서도 안되고 너무 늦게 먹어서도 안된다. 즉, 사탕 종류마다 먹을 수 있는/먹어야되는 순간이 정해지게 된다. 그러면 현재 먹을 수 있는 사탕 종류들이 있다. 현재 먹을 수 있는 사탕 종류들 중에 먹어야되는 순간이 제일 짧은 사탕 종류를 먼저 먹는 것이 항상 좋다. 문제에서 주어진 부등식을 통해 사탕 종류를 먹을 수 있게 되는 순간과 언제까지 먹어야되는지를 계산할 수 있다.

하지만 무한히 많은 사탕을 먹을 수 있는 경우도 존재한다. $f_i$의 분모를 $M$이라고 하자. 추가적으로 $M$개의 사탕을 먹었다면, 그 것과 똑같은 순서로 $M$개의 사탕을 다시 먹어도 다이어트 조건을 만족한다. 그러므로 $M$개 이상의 사탕을 추가적으로 먹을 수 있다면, 무한히 많은 사탕을 먹을 수 있다는 것이다.


코드 보기


B. Branch Assignment


정점이 $N$개고 간선이 $R$개인 방향성 그래프가 주어진다. $1$번 정점부터 $B$번 정점은 특별한 정점이고, 특별한 정점들을 $S$개의 그룹으로 나눠야한다. 그룹마다 비용을 정의할 수 있는데, 그룹의 비용은 그룹에 속해 있는 모든 정점 순서쌍 $(i, j)$들의 비용 합이다. 정점 순서쌍 $(i, j)$의 비용은 $i$번 정점에서 $j$번 정점으로 $B+1$번 정점을 거쳐가는 최단 거리다. $B$개의 특별한 정점을 $S$개의 그룹으로 나누고 그룹 비용의 합을 최소화하는 문제다.


특별한 $i$번 정점이 크기가 $K_i$인 그룹에 속해있다고 하자. $i$번 정점이 전체 비용에 미치는 영향은 $(K_i-1)(\text{dist}(i, B+1) + \text{dist}(B+1, i))$ 만큼인 것을 알 수 있다. 즉, $i$번 정점을 기준으로 볼 때 비용이 그룹의 크기에 영향을 받지 어떤 정점들과 함께 그룹에 있는지는 중요하지 않다는 것이다.

따라서 $S$개 그룹의 크기를 미리 정했다고 했을 때, $V_i = \text{dist}(i, B+1) + \text{dist}(B+1, i)$ 값이 큰 정점이 작은 그룹에 들어가고, $V_i$ 값이 작은 정점이 큰 그룹에 들어가는 것이 최적이다. 즉, $V_i$ 순으로 특별한 정점을 정렬하고 일렬로 나타내었을 때, 같은 그룹에 속한 정점들은 연속되게 그룹을 나눠도 최적해를 구할 수 있다. 이 때 우리는 아래와 같은 DP배열을 정의할 수 있다.


$D[c][i]$ = $V_i$ 값 순으로 정렬해 일렬로 나타날 때, 때 첫 번째 정점부터 $i$번째 정점까지 그룹을 $c$개로 나누었을 때 최소 비용

$D[c][i] = \min_{k<i}(D[c-1][k] + (i-k-1)(V_{k+1}+V_{k+2}+\dots+V_i)$


DP 시간복잡도는 $O(SB^2)$이지만, Divide & Conquer Optimization을 통해 $O(SB \lg B)$로 줄일 수 있다. 이 경우 비용 함수 $C[i][j] = (j-i-1)(V_{i+1}+V_{i+2}+\dots+V_j)$가 사각부등식을 만족하기 때문에 Divide & Conquer Optimization을 이용할 수 있다.


코드 보기


'ICPC > World Finals' 카테고리의 다른 글

ACM ICPC World Finals 2016  (0) 2016.06.18
ACM ICPC World Finals 2015  (1) 2015.05.22
ACM ICPC World Finals 2011  (0) 2015.05.18
댓글
댓글쓰기 폼