ACM ICPC World Finals 2018

문제 링크

B. Comma Sprinkler

길이가 최대 1,000,000인 문장들이 주어진다. 어떤 단어 앞에 콤마(,)가 오면 같은 단어 앞에 모두 콤마가 오도록 바꾸며, 어떤 단어 뒤에 콤마가 올 경우 같은 단어 뒤에 모두 콤마가 오도록 바꿔야한다. 단, 단어의 끝과 시작에서 부자연스럽게 콤마를 추가하진 않는다. 이 때, 최종 문장을 구하는 문제다.

같은 단어들을 묶어 정점으로 만든다. 그리고 정점을 단어 앞에 콤마가 오는 경우, 단어 뒤에 콤마가 오는 경우를 나타내는 두 정점으로 이원화한다. 단어 앞에 콤마가 오거나, 단어 뒤에 콤마가 오는 경우 해당하는 정점에 색칠은 한 뒤, 원래 문장에서 인접한 두 단어의 정점에는 방향성 간선을 만들어주어 Flood-Fill 한다. 그러면 시간복잡도 $O(V+E)$만에 문제에서 요구하는 조건을 만족시킬 수 있다. 단어를 정점으로 만들 때, set등을 쓰지 않고 trie를 사용하면 $O(N)$ 시간에 문제를 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 #define pb push_back int N, K; bool V[MAXN][2]; char S[MAXN]; string words[MAXN]; vector <int> con[MAXN][2]; vector <pair<int, bool>> A; struct NODE { NODE(): num(0){ for (int i=0;i<26;i++) nxt[i] = 0; } int num; NODE *nxt[26]; } root; int getNum(char *str) { NODE *now = &root; for (int i=0;str[i];i++){ if (!now->nxt[str[i]-'a']) now->nxt[str[i]-'a'] = new NODE(); now = now->nxt[str[i]-'a']; } if (!now->num){ now->num = ++K; words[K] = str; } return now->num; } int main() { fgets(S+1, MAXN-2, stdin); N = strlen(S+1); bool bef = 0; int last = 0; for (char *pt=strtok(S+1, " \n\r");pt;pt=strtok(0, " \n\r")){ int n = strlen(pt); bool aft = 0, end = 0; if (pt[n-1] == ',') pt[--n] = 0, aft = 1; if (pt[n-1] == '.') pt[--n] = 0, end = 1; int k = getNum(pt); if (bef) V[k][0] = 1; if (aft) V[k][1] = 1; if (last) con[k][0].pb(last), con[last][1].pb(k); bef = aft; last = k; A.pb({k, end}); if (end) last = 0; } queue <int> que; for (int i=1;i<=K;i++) for (int j=0;j<2;j++) if (V[i][j]) que.push(i), que.push(j); while (!que.empty()){ int q = que.front(); que.pop(); int p = que.front(); que.pop(); for (int t: con[q][p]){ if (V[t][!p]) continue; V[t][!p] = 1; que.push(t); que.push(!p); } } int prv = 0; bool end = 0, prv_out = 1; for (const auto &s: A){ if (V[s.first][0] && !end && !prv_out) putchar(','); if (prv) putchar(' '); printf("%s", words[s.first].c_str()); if (V[s.first][1] && !s.second) putchar(','), prv_out = 1; else prv_out = 0; if (s.second) putchar('.'); prv = s.first; end = s.second; } puts(""); }

F. Go with the Flow

단어 $N$개가 주어진다. 각 단어의 최대 길이는 80이다. 종이의 폭을 적절히 정해 생기는 공백 강(세로로 늘어진 공백 행렬)의 길이를 최대화하는 문제다. 단, 줄의 오른쪽 끝에 자연스럽게 생기는 공백은 공백 강에 포함되지 않는다.

폭으로 가능한 길이의 종류 수는 약 $80N$이며, 폭에 따라 생기는 공백의 개수는 최대 $N$개다. 임의의 폭을 정했을 때, 공백 강의 최대 길이를 two-pointers algorithm과 DP를 통해 $O(N)$ 시간복잡도로 구할 수 있다. 따라서 이 문제를 $O(N^2)$에 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 2503 #define pb push_back #define sz(v) ((int)(v).size()) typedef pair<int, int> pii; int N, X; int A[MAXN], S[MAXN]; auto f = [](int width){ int next_width = 2e9; vector <pii> arr; for (int s=1,y=1;s<=N;s++,y++){ int e = s; while (e < N && S[e+1]-S[s-1]+e-s+1 <= width) e++; if (e < N) next_width = min(next_width, S[e+1]-S[s-1]+e-s+1); for (int i=s;i<e;i++) arr.pb({y, S[i]-S[s-1]+i-s+1}); s = e; } int n = sz(arr); vector <int> dp(n, 1); int ret = 0; for (int i=0,p=0;i<n;i++){ int y = arr[i].first, x = arr[i].second; while (p < n && arr[p] < pii{y-1, x-1}) p++; for (int j=p;j<n;j++){ if (arr[j] > pii{y-1, x+1}) break; dp[i] = max(dp[i], dp[j]+1); } ret = max(ret, dp[i]); } return make_tuple(ret, next_width); }; int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ char buf[82]={0,}; scanf("%s", buf); A[i] = strlen(buf); S[i] = S[i-1]+A[i]; X = max(X, A[i]); } int ans = 0, answ; for (int width=X;width<2e9;){ int mx, nxt; tie(mx, nxt) = f(width); if (ans < mx) ans = mx, answ = width; width = nxt; } printf("%d %d\n", answ, ans); }

K. Wireless is the New Fiber

$N$개의 정점과, $M$개의 간선으로 이루어진 연결그래프가 주어진다. $N$개의 정점으로 구성된 기존 그래프와 전혀 다른 트리를 새로 만드는데, 차수(degree)가 변한 정점의 수를 최소화하도록 만드는 문제다.

이 문제는 두 파트로 풀이가 나뉜다. 첫 번째 파트는 차수가 변환 정점 수를 최소화하면서 새로 만드는 트리의 각 정점 차수를 구하는 것이고, 두 번째 파트는 구한 각 정점의 차수를 기반으로 트리를 만들어서 출력하는 것이다.

우선, $N$개의 정점 차수 합이 $2 \times (N-1)$이면서 각 정점의 차수가 1이상 $N-1$이하라면, 해당 차수에 알맞은 트리를 항상 만들 수 있다. 이는 필요충분조건이다.

이를 이용하여, 첫 번째 파트를 해결한다. "차수가 변한 정점의 개수가 $x$개 이하면서 모든 정점의 차수를 1이상 N-1이하로 맞출 수 있느냐"라는 결정 문제를 생각해보자. 이는 greedy하게 해결이 가능한데, 차수가 제일 큰 상위 $x$개 정점의 차수를 변화시켜 가능한지 여부를 간단한 수학으로 계산하면 된다. Parametric search와 결정 문제 풀이를 이용해서 첫 번째 파트를 해결할 수 있다.

두 번째 파트는 풀이가 더 간단하다. 각 정점의 차수를 모두 알고 있는 상태에서 트리를 구현하는 문제를 해결하면 된다. 차수 크기의 역순으로 정점들을 정렬한 뒤에, 차수가 큰 정점들끼리 우선으로 간선을 만들어주면 결국 트리가 완성된다. 이와 관련된 증명은 "$k < N$일 때, 차수가 가장 큰 상위 $k$개 정점의 차수 합은 $2 \times (k-1)$을 넘는다."는 사실을 통해 할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 10004 #define pb push_back #define all(v) (v).begin(), (v).end() typedef pair<int, int> pii; int N, M; int deg[MAXN]; bool proc(int cnt, bool fix=0) { vector <pii> arr; for (int i=1;i<=N;i++) arr.pb({deg[i], i}); sort(all(arr), greater<pii>()); int sum = 0; for (int i=cnt;i<N;i++) sum += arr[i].first; if (sum+cnt > 2*(N-1)) return 0; if (!fix || !cnt) return 1; int remain = 2*(N-1) - sum - cnt; for (int i=0;i<cnt;i++) deg[arr[i].second] = 1; int avg = remain / cnt, rest = remain % cnt; for (int i=0;i<cnt;i++) deg[arr[i].second] += avg + (i < rest); return 1; } int main() { scanf("%d%d", &N, &M); for (int i=1;i<=M;i++){ int a, b; scanf("%d%d", &a, &b); a++; b++; deg[a]++; deg[b]++; } int s = 0, e = N, ans; while (s <= e){ int m = s+e >> 1; if (proc(m)) e = m-1, ans = m; else s = m+1; } proc(ans, 1); printf("%d\n%d %d\n", ans, N, N-1); vector <int> ord; for (int i=1;i<=N;i++) ord.pb(i); sort(all(ord), [](const int &a, const int &b){ return deg[a] > deg[b]; }); int pt = 1; for (int n: ord){ while (deg[n]--){ printf("%d %d\n", n-1, ord[pt]-1); deg[ord[pt++]]--; } } }

A. Catch the Plane

$N$개의 버스정류장과 $M$개의 버스 운행 정보가 있다. 버스 운행 정보는 시작점과 도착점, 출발시각과 도착시각, 그리고 파업 확률이 주어진다. 한 순간에 한 정류장에서 여러 버스가 출발하면 그 중에 하나만 선택하여 "탑승 시도"를 할 수 있다. 이 때, 0번 정류장에서 시작하여 1번 정류장까지 이동할 때, 도착 확률이 최대가 되도록 전략을 짜는 문제다.

여기서 도착 시간제한 $K$가 입력으로 주어지지만, 모든 버스의 도착 시각이 $K$이내인 관계로 $K$ 값 자체와 시간제한 자체가 의미가 없다. 이 문제 풀이의 핵심 아이디어는 DP를 거꾸로 계산한다는 것이다.

다음과 같은 DP 테이블을 생각하자:

D[i][j] = j 시간에 i번 정류장에서 출발할 때, 도착 지점까지 가는 최고 확률

j 시간에 만약 k번 정류장으로 가는 버스가 있고 도착시각이 t이며 파업확률이 p라고 할 때, 이 버스 탑승을 시도할 경우 도착 확률은 D[k][t+1]*p + D[i][j+1]*(1-p)로 계산할 수 있다. 만약 탑승 시도를 하지 않고 시간을 보내는 경우 도착 확률은 D[i][j+1]이다. 이 중에 제일 높은 확률을 D[i][j]에 대입하는 것으로 점화식을 세울 수 있다.

문제는 시간 범위가 최대 10¹⁸으로 굉장히 크다는 것이다. 위에서 설명한 DP를 버스 도착시각 역순으로 계산해가면서 대기 힙과 큐를 이용하여 계산하면 2차원 테이블 없이 1차원 배열만으로 이 문제의 답을 구할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 typedef long long lld; int N, M; lld K; double P[MAXN]; struct EDGE { int a, b; lld x, y; double p; } edge[MAXN]; struct INFO { lld k; int n, e; double p; bool operator < (const INFO &ot)const{ return k < ot.k; } }; int main() { scanf("%d%d%lld", &M, &N, &K); for (int i=1;i<=M;i++){ int a, b; lld x, y; double p; scanf("%d%d%lld%lld%lf", &a, &b, &x, &y, &p); edge[i] = {++a, ++b, x, y, p}; } sort(edge+1, edge+M+1, [](const EDGE &a, const EDGE &b){ return a.y > b.y; }); priority_queue <INFO> que; P[2] = 1; edge[M+1].y = -1; for (int i=1;i<=M+1;i++){ queue <pair<int, double>> wait; lld last = -1; auto flush = [&wait](){ while (!wait.empty()){ auto q = wait.front(); wait.pop(); P[q.first] = max(P[q.first], q.second); } }; while (!que.empty()){ INFO q = que.top(); if (q.k <= edge[i].y) break; que.pop(); if (last != q.k) flush(), last = q.k; wait.push({q.n, q.p*edge[q.e].p + P[q.n]*(1-edge[q.e].p)}); } flush(); if (i > M) break; que.push({edge[i].x, edge[i].a, i, P[edge[i].b]}); } printf("%.9f\n", P[1]); }

H. Single Cut of Failure

$W \times H$ 크기의 직사각형 안에 $N$개의 선분이 주어진다. 선분의 양 끝 점은 직사각형 변 위에 있으며, 꼭지점과 겹치지 않고 선분의 끝 점이 서로 겹치게 주어지지 않는다. 또한 선분이 직사각형 변에 포함되게 주어지지 않는다. 주어진 $N$개의 선분과 모두 교차하게 최소 개수의 선분을 그리는 문제다.

두 대각선을 X 모양으로 그리면 입력이 어떤 식으로 들어오든 상관 없이 모든 선분과 교차함을 알 수 있다. 따라서, 답은 1개 혹은 2개이며, 2개일 경우 출력 내용은 선분과 상관없이 고정된다. 즉, 이 문제는 1개의 선분만을 그려 모든 선분과 교차할 수 있는지 판단하고 가능하다면 그 선분을 어떻게 그릴 것인가를 구하면 해결된다. 문제 제목이 Single Cut of Failure인 것은 풀이에 대한 스포일러다.

입력으로 들어온 $N$개의 선분을 1차원 구간으로 펴서 $N$개의 구간으로 만들고 모든 구간과 교차하는 구간이 존재하는지 여부를 구해 답이 1개인지 확인하면 된다. 확인하는 과정에서 모든 구간과 교차하는 구간의 생김세 또한 구할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 #define mt make_tuple int N, W, H; struct Z{ int s, e; } A[MAXN]; int getNum(int x, int y) { if (y == 0) return x; if (x == W) return W+y; if (y == H) return W+H+W-x; return W+H+W+H-y; } auto getCoord = [](double v){ if (v < W) return mt(v, 0.); v -= W; if (v < H) return mt((double)W, v); v -= H; if (v < W) return mt(W-v, (double)H); v -= W; return mt(0., H-v); }; bool checkOneShot() { sort(A+1, A+N+1, [](const Z &a, const Z &b){ return a.e < b.e; }); vector <int> p(N+1, 0), q(N+1, 0); p[N] = q[N] = A[N].s; for (int i=N;--i;) p[i] = max(p[i+1], A[i].s), q[i] = min(q[i+1], A[i].s); int max_s = 0; for (int i=1;i<=N;i++){ max_s = max(max_s, A[i].s); if (A[1].e <= max_s) break; // max_s 보다 0.5 큰 곳에 시작점을 놓고, // A[i].e 보다 큰 곳에 도착점을 놓는다. // j > i인 A[j].s는 모두 max_s보다 커야 한다. // j > i인 A[j].s는 모두 A[i+1].e 보다 작아야한다. // 그러면 A[i+1].e 보다 0.5 작은 곳에 도착점을 둔다. if (i == N || q[i+1] > max_s && p[i+1] < A[i+1].e){ double ax, ay, bx, by; tie(ax, ay) = getCoord(max_s+0.5); tie(bx, by) = getCoord(i == N ? H+H+W+W-0.5 : A[i+1].e-0.5); printf("1\n%.1f %.1f %.1f %.1f\n", ax, ay, bx, by); return 1; } } return 0; } int main() { scanf("%d%d%d", &N, &W, &H); for (int i=1;i<=N;i++){ int x, y; scanf("%d%d", &x, &y); A[i].s = getNum(x, y); scanf("%d%d", &x, &y); A[i].e = getNum(x, y); if (A[i].s > A[i].e) swap(A[i].s, A[i].e); } if (!checkOneShot()) printf("2\n%d %.1f %d %.1f\n%d %.1f %d %.1f\n", 0, H-0.5, W, 0.5, 0, 0.5, W, H-0.5); }

I. Triangles

입력으로 그림이 주어지면, 그림 안에 정삼각형의 개수를 세는 문제다.

우선, △ 모양의 삼각형의 개수만 세면 전체 정삼각형의 개수를 셀 수 있다. ▽ 모양의 삼각형은 전체 그림을 상하로 뒤집은 다음 △ 모양의 삼각형의 개수를 한 번 더 세는 방식으로 셀 수 있다.

△ 모양의 삼각형의 개수는 각 지점마다 오른쪽 위(/)로 변의 길이와, 왼쪽 위로(\)로 변의 길이를 칸 마다 계산해두고, Fenwick Tree와 Heap을 통해 계산할 수 있다. 풀이를 말로 풀어쓰기 복잡하여, 풀이는 코드를 참고하자.

#include <bits/stdc++.h> using namespace std; #define notSpace(x) (x != 0 && x != ' ') typedef long long lld; int yy[]={0, -1, -1, 0, 1, 1}, xx[]={-2, -1, 1, 2, 1, -1}; int N, M; char A[6004][12003]; bool con[3002][6001][3]; int P[6001], Q[6001]; int bit[6001]; int add(int n, int v){ for (;n<=M;n+=(n&-n)) bit[n] += v; } int get(int n){ int ret = 0; for (;n;n^=(n&-n)) ret += bit[n]; return ret; } lld count() { lld ret = 0; for (int i=1;i<=N;i++) for (int j=2-(i&1);j<=M;j+=2) for (int k=0;k<3;k++){ int y = i+yy[k], x = j+xx[k]; if (y < 1 || y > N || x < 1 || x > M) continue; int ty = i+i-1, tx = j+j-1; con[i][j][k] = notSpace(A[ty+yy[k]][tx+xx[k]]); } for (int i=1;i<=N;i++){ struct QUE{ int out, x; bool operator < (const QUE &ot)const{ return out > ot.out; } }; priority_queue <QUE> que; int horz = 0; for (int j=1;j<=M;j++) bit[j] = 0; for (int j=2-(i&1);j<=M;j+=2){ while (!que.empty()){ QUE q = que.top(); if (q.out >= j) break; que.pop(); add(q.x, -1); } P[j] = con[i][j][2] ? P[j+1] + 1 : 0; Q[j] = con[i][j][1] ? Q[j-1] + 1: 0; horz = con[i][j][0] ? horz + 1 : 0; int s = min(horz, Q[j]); ret += get(j)-get(j-s-s-1); que.push({j+P[j]+P[j], j}); add(j, 1); } } // flip for (int i=1;i<N+N-i;i++) for (int j=1;j<M+M;j++) swap(A[i][j], A[N+N-i][j]); for (int i=1;i<N+N;i++) for (int j=1;j<M+M;j++){ char c = A[i][j]; if (c == '/') A[i][j] = '\\'; if (c == '\\') A[i][j] = '/'; } return ret; } int main() { scanf("%d%d ", &N, &M); for (int i=1;i<N+N;i++) gets(A[i]+1); if (!(N&1)) N++; // make N odd for Y axis flip lld ans = count()+count(); printf("%lld\n", ans); }