ACM ICPC World Finals 2016

문제 링크

C. Ceiling Function

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

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

#include <bits/stdc++.h> using namespace std; int N, M; int A[21]; struct NODE { NODE(int val=0): val(val) { left = right = 0; } int val; NODE *left, *right; } *root[51]; bool identical(NODE *a, NODE *b) { if ((bool)a->left != (bool)b->left || (bool)a->right != (bool)b->right) return 0; bool ret = 1; if (a->left) ret &= identical(a->left, b->left); if (a->right) ret &= identical(a->right, b->right); return ret; } int main() { scanf("%d%d", &N, &M); for (int i=1;i<=N;i++){ for (int j=1;j<=M;j++) scanf("%d", A+j); root[i] = new NODE(A[1]); for (int j=2;j<=M;j++){ NODE *now = root[i]; for (;;){ if (A[j] < now->val){ if (now->left) now = now->left; else{ now->left = new NODE(A[j]); break; } }else{ if (now->right) now = now->right; else{ now->right = new NODE(A[j]); break; } } } } } int ans = 0; for (int i=1;i<=N;i++){ bool sw = 0; for (int j=1;j<i;j++) if (identical(root[j], root[i])){ sw = 1; break; } if (!sw) ans++; } printf("%d\n", ans); }

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$ 이므로 문자열을 통한 대소비교를 할 필요가 없다.

#include <bits/stdc++.h> using namespace std; typedef long long lld; lld Y, L; int main() { scanf("%lld%lld", &Y, &L); lld ans = 10; for (int i=0;i<10;i++) for (int j=0;j<10;j++) for (int k=0;k<10;k++) for (int l=0;l<10;l++) for (int o=0;o<10;o++){ lld s = max({i, j, k, l, o})+1, e = Y, b = 0; while (s <= e){ lld m = (s+e)>>1, v = 0; if (i && (m > Y/m || m*m > Y/m || m*m*m > Y/m)){ e = m-1; continue; } if (j && (m > Y/m || m*m > Y/m)){ e = m-1; continue; } if (k && (m > Y/m)){ e = m-1; continue; } if (l && (m > Y)){ e = m-1; continue; } v = m * m * m * m * i + m * m * m * j + m * m * k + m * l + o; if (v > Y) e = m-1; else if (v == Y){ b = m; break; } else s = m+1; } lld n = o + l*10 + k*100 + j*1000 + i*10000; if (b && L <= n) ans = max(ans, b); } for (int i=11;;i++){ if ((lld)i*i*i > Y/i) break; bool sw = 0; lld n = 0, ten = 1; for (lld v=Y;v;v/=i){ if (v%i > 9){ sw = 1; break; } n += v%i * ten; ten *= 10; } if (!sw && n >= L) ans = max(ans, (lld)i); } printf("%lld\n", ans); }

L. Swap Space

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

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

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

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

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 typedef long long lld; int N; struct Z{ int a, b; } A[MAXN]; int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d%d", &A[i].a, &A[i].b); sort(A + 1, A + N + 1, [](const Z &a, const Z &b){ int p = a.a <= a.b ? -1 : 1, q = b.a <= b.b ? -1 : 1; if (p != q) return p < q; if (p == -1) return a.a < b.a; return a.b > b.b; }); lld ans = 0, free = 0; for (int i = 1; i <= N; i++){ if (free >= A[i].a) free += -A[i].a + A[i].b; else{ ans += A[i].a - free; free = A[i].b; } } printf("%lld\n", ans); }

G. Oil

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

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

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

#include <bits/stdc++.h> using namespace std; #define MAXN 2004 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N; int X1[MAXN], X2[MAXN], Y[MAXN]; struct Z{ int x, y, t; }; int ccw(int ax, int ay, int bx, int by, int cx, int cy) { lld k = (lld)(bx-ax)*(cy-ay) - (lld)(cx-ax)*(by-ay); if (k > 0) return 1; if (k) return -1; return 0; } int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ scanf("%d%d%d", X1+i, X2+i, Y+i); if (X1[i] > X2[i]) swap(X1[i], X2[i]); } lld ans = 0; for (int i=1;i<=N;i++) for (int tp=0;tp<2;tp++){ int x = tp ? X2[i] : X1[i]; vector <Z> arr; for (int j=1;j<=N;j++) if (Y[i] != Y[j]){ if (Y[j] > Y[i]){ arr.pb({-X1[j]+x, Y[j]-Y[i], X2[j]-X1[j]}); arr.pb({-X2[j]+x, Y[j]-Y[i], X1[j]-X2[j]}); }else{ arr.pb({X1[j]-x, Y[i]-Y[j], X1[j]-X2[j]}); arr.pb({X2[j]-x, Y[i]-Y[j], X2[j]-X1[j]}); } } sort(all(arr), [](const Z &a, const Z &b){ int k = ccw(0, 0, a.x, a.y, b.x, b.y); if (k) return k > 0; return a.t > b.t; }); lld sum = X2[i]-X1[i]; ans = max(ans, sum); for (Z &z: arr){ sum += z.t; ans = max(ans, sum); } } printf("%lld\n", ans); }

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이 될 수 없다.

#include <bits/stdc++.h> using namespace std; int N; int A[101]; int main() { scanf("%d", &N); int sum = 0; for (int i=1;i<=N;i++) scanf("%d", A+i), sum += A[i]; if (sum&1){ puts("no quotation"); return 0; } int ans = sum == 2 ? 1 : 0; for (int k=2;;k++){ if (sum < k*(k+1)) break; int t = 1, left = A[1]; bool fail = 0; for (int i=k;i;i--){ if (!left) left += A[++t]; if (left < i) fail = 1; left -= i; } t = N, left = A[N]; for (int i=k;i;i--){ if (!left) left += A[--t]; if (left < i) fail = 1; left -= i; } if (!fail) ans = k; } if (!ans) puts("no quotation"); else printf("%d\n", ans); }

D. Clock Breaking

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

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

#include <bits/stdc++.h> using namespace std; #define mp make_pair typedef pair<int, int> pii; int N; char A[101][8][23]; void print_digit(int x, int d, char board[6][23]) { vector <pii> pos[10] = { {{1, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 0}, {3, 3}, {5, 0}, {5, 3}, {6, 0}, {6, 3}, {7, 1}, {7, 2}}, // 0 {{2, 3}, {3, 3}, {5, 3}, {6, 3}}, // 1 {{1, 1}, {1, 2}, {2, 3}, {3, 3}, {4, 1}, {4, 2}, {5, 0}, {6, 0}, {7, 1}, {7, 2}}, // 2 {{1, 1}, {1, 2}, {2, 3}, {3, 3}, {4, 1}, {4, 2}, {5, 3}, {6, 3}, {7, 1}, {7, 2}}, // 3 {{2, 0}, {2, 3}, {3, 0}, {3, 3}, {4, 1}, {4, 2}, {5, 3}, {6, 3}}, // 4 {{1, 1}, {1, 2}, {2, 0}, {3, 0}, {4, 1}, {4, 2}, {5, 3}, {6, 3}, {7, 1}, {7, 2}}, // 5 {{1, 1}, {1, 2}, {2, 0}, {3, 0}, {4, 1}, {4, 2}, {5, 0}, {5, 3}, {6, 0}, {6, 3}, {7, 1}, {7, 2}}, // 6 {{1, 1}, {1, 2}, {2, 3}, {3, 3}, {5, 3}, {6, 3}}, // 7 {{1, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 0}, {3, 3}, {4, 1}, {4, 2}, {5, 0}, {5, 3}, {6, 0}, {6, 3}, {7, 1}, {7, 2}}, // 8 {{1, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 0}, {3, 3}, {4, 1}, {4, 2}, {5, 3}, {6, 3}, {7, 1}, {7, 2}}, // 9 }; for (auto &p: pos[d]) board[p.first][x+p.second] = 'X'; } void print(int h, int m, char board[8][23]) { for (int i=1;i<8;i++){ for (int j=1;j<22;j++) board[i][j] = '.'; board[i][22] = 0; } if (h/10) print_digit(1, h/10, board); print_digit(6, h%10, board); board[3][11] = board[5][11] = 'X'; print_digit(13, m/10, board); print_digit(18, m%10, board); } void cmp(char org[8][23], char inp[8][23], char status[8][23]) { for (int i=1;i<8;i++) for (int j=1;j<22;j++) status[i][j] = 7; for (int i=1;i<8;i++) for (int j=1;j<22;j++){ int real = org[i][j] == 'X'; int cur = inp[i][j] == 'X'; if (real && cur) status[i][j] &= 3; if (!real && cur) status[i][j] &= 2; if (real && !cur) status[i][j] &= 4; if (!real && !cur) status[i][j] &= 5; } } void combine(char to[8][23], char tar[8][23], int type=1) { for (int i=1;i<8;i++) for (int j=1;j<22;j++){ if (type == 1) to[i][j] &= tar[i][j]; else to[i][j] |= tar[i][j]; } } bool poss(int h, int m, char status[8][23]) { for (int i=1;i<8;i++) for (int j=1;j<22;j++) status[i][j] = 7; for (int i=1;i<=N;i++){ char tmp[8][23], stmp[8][23]; print(h, m, tmp); cmp(tmp, A[i], stmp); combine(status, stmp); m++; if (m == 60) m = 0, h++; if (h == 24) h = 0; } for (int i=1;i<8;i++) for (int j=1;j<22;j++) if (!status[i][j]) return 0; return 1; } int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ for (int j=1;j<8;j++) scanf("%s", A[i][j]+1); } char status[8][23] = {0, }; for (int i=1;i<8;i++) for (int j=1;j<22;j++) status[i][j] = 0; bool exists = 0; for (int h=0;h<24;h++){ for (int m=0;m<60;m++){ char tmp[8][23]; if (poss(h, m, tmp)){ exists = 1; combine(status, tmp, 2); } } } if (!exists){ puts("impossible"); return 0; } for (int i=1;i<8;i++) for (int j=1;j<22;j++) if (!status[i][j]){ puts("impossible"); return 0; } char tmp[8][23]; print(88, 88, tmp); for (int i=1;i<8;i++){ for (int j=1;j<22;j++){ if (tmp[i][j] == '.') printf("."); else printf("%c", "-W1?0???"[status[i][j]]); } puts(""); } }

A. Balanced Diet

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

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

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

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define mp make_pair typedef long long lld; typedef pair<int, int> pii; int N, M, K; int A[MAXN], B[MAXN]; int S[MAXN], E[MAXN]; priority_queue <pii> can_eat, not_yet; void update(int n) { S[n] = (lld)B[n]*M / A[n]; E[n] = ((lld)(B[n]+1)*M - 1) / A[n]; } int main() { scanf("%d%d", &N, &K); for (int i=1;i<=N;i++) scanf("%d", A+i), M += A[i]; for (int i=1;i<=K;i++){ int t; scanf("%d", &t); B[t]++; } for (int i=1;i<=N;i++){ update(i); not_yet.push(mp(-S[i], i)); } for (int i=K;i<K+M;i++){ while (!not_yet.empty() && -not_yet.top().first <= i){ int n = not_yet.top().second; not_yet.pop(); can_eat.push(mp(-E[n], n)); } if (can_eat.empty() || -can_eat.top().first < i){ printf("%d\n", i-K); return 0; } int n = can_eat.top().second; can_eat.pop(); B[n]++; update(n); not_yet.push(mp(-S[n], n)); if (!can_eat.empty() && -can_eat.top().first <= i){ printf("%d\n", i-K); return 0; } } puts("forever"); }

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을 이용할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 5003 #define pb push_back typedef pair<int, int> pii; typedef long long lld; int N, B, K, M; int P[MAXN], Q[MAXN], A[MAXN], V[MAXN]; lld D[MAXN], E[MAXN], S[MAXN]; vector <pii> con[MAXN], rcon[MAXN]; void dijkstra(int st, int dist[], vector<pii> conn[]) { for (int i=1;i<=N;i++) dist[i] = 1e9; priority_queue <pii> que; dist[st] = 0; que.push({0, st}); while (!que.empty()){ int q = que.top().second, d = -que.top().first; que.pop(); if (d != dist[q]) continue; for (auto &p: conn[q]){ int v = d + p.second, t = p.first; if (dist[t] > v) dist[t] = v, que.push({-v, t}); } } } void dfs(int s, int e, int p, int q) { if (s > e) return; int m = (s+e)>>1, opt; D[m] = 1e18; for (int k=p;k<=q&&k<m;k++){ lld v = E[k] + (lld)(m-k-1)*(S[m]-S[k]); if (D[m] > v) D[m] = v, opt = k; } dfs(s, m-1, p, opt); dfs(m+1, e, opt, q); } int main() { scanf("%d%d%d%d", &N, &B, &K, &M); for (int i=1;i<=M;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); con[a].pb({b, c}); rcon[b].pb({a, c}); } dijkstra(B+1, P, con); dijkstra(B+1, Q, rcon); for (int i=1;i<=B;i++) A[i] = i, V[i] = P[i]+Q[i]; sort(A+1, A+B+1, [](const int &a, const int &b){ return V[a] < V[b]; }); for (int i=1;i<=B;i++) E[i] = 1e18, S[i] = S[i-1] + V[A[i]]; for (int i=1;i<=K;i++){ dfs(i, B, 0, B); for (int j=0;j<=B;j++) E[j] = D[j]; } printf("%lld\n", D[B]); }