2018년 아시아태평양 정보올림피아드 (APIO2018) 풀이

A. 새 집 (New Home)

$N$개의 상점이 주어진다. $i$번째 상점은 위치 $x_i$에 지어지며, 종류는 $t_i$이고, $a_i$년 초에 생겨, $b_i$년 말에 없어진다. 상점의 종류는 $K$가지이다. $Q$개의 질문이 주어진다. $i$번째 질문은, $y_i$년 중순에 $l_i$위치에 집을 지을 경우, 상점 종류마다 제일 가까운 상점과의 거리를 구해 그 중 최대값을 요구한다.

예를 들어, $K=2$이고 어떤 특정 시점에 1번 종류 상점이 좌표 2, 5, 13에 있고, 2번 종류 상점이 좌표 6, 10, 15에 있다고 했을 때, 아래와 같은 그래프를 그릴 수 있다.

그래프에서 파란색 선은 1번 종류 상점에 대한 거리를 나타내고, 주황색 선은 2번 종류 상점에 대해 거리를 나타낸다. 이 순간 좌표 8에 집이 있다고 하면 문제에서 요구하는 답은 3이 될 것이고, 집이 좌표 11에 있다고 하면 문제에서 요구하는 답은 2가 된다. 즉, 집의 위치가 $l$라고 했을 때, 그래프를 그리고 수직선 $x=l$을 그린 뒤 생기는 교차점 중 $y$ 좌표가 제일 큰 것이 답이 된다.

시간이 지남에 따라 상점은 새로 생기기도 하고, 없어지기도 한다. 상점이 새로 생길 때와 없어질 때를 고려하여, 종류마다 위에서 그린 것과 같은 그래프를 multiset을 이용하여 유지할 수 있다. 이제 수직선 $x=l$에 대해 생기는 교차점 중 $y$ 좌표가 제일 큰 것을 찾으면 되는데, / 모양 사선과 \ 모양 사선에 대해 따로 segment tree를 만들어 구하면 된다. 사선의 peak 지점 $x$ 좌표와 사선의 $x$절편을 이용하면 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 300005 typedef pair<int, int> pii; int N, K, Q; int XX[MAXN], XC; int ans[MAXN]; multiset<int> P[MAXN]; struct STORE { int x, t, a, b; } A[MAXN]; struct QUERY { int x, t, idx; } B[MAXN]; const int TS = 1048576, ST = TS/2-1; int mnTree[TS], mxTree[TS]; multiset<int> leaves1[MAXN], leaves2[MAXN]; void _add(int x0, int xt, char dir) { if (dir == '/'){ int t = upper_bound(XX+1, XX+XC+1, xt)-XX-1; if (t < 1) return; leaves1[t].insert(x0); mnTree[ST+t] = *leaves1[t].begin(); for (int n=ST+t>>1;n;n>>=1) mnTree[n] = min(mnTree[n+n], mnTree[n+n+1]); }else{ int t = lower_bound(XX+1, XX+XC+1, xt)-XX; if (t > XC) return; leaves2[t].insert(x0); mxTree[ST+t] = *leaves2[t].rbegin(); for (int n=ST+t>>1;n;n>>=1) mxTree[n] = max(mxTree[n+n], mxTree[n+n+1]); } } void _del(int x0, int xt, char dir) { if (dir == '/'){ int t = upper_bound(XX+1, XX+XC+1, xt)-XX-1; if (t < 1) return; leaves1[t].erase(leaves1[t].find(x0)); mnTree[ST+t] = leaves1[t].empty() ? 2e9 : *leaves1[t].begin(); for (int n=ST+t>>1;n;n>>=1) mnTree[n] = min(mnTree[n+n], mnTree[n+n+1]); }else{ int t = lower_bound(XX+1, XX+XC+1, xt)-XX; if (t > XC) return; leaves2[t].erase(leaves2[t].find(x0)); mxTree[ST+t] = leaves2[t].empty() ? -2e9 : *leaves2[t].rbegin(); for (int n=ST+t>>1;n;n>>=1) mxTree[n] = max(mxTree[n+n], mxTree[n+n+1]); } } void add(int x, int t) { auto l = P[t].lower_bound(x); auto r = l--; _del(*l, *l+*r>>1, '/'); _del(*r, *l+*r>>1, '\\'); _add(*l, *l+x>>1, '/'); _add(x, *l+x>>1, '\\'); _add(x, x+*r>>1, '/'); _add(*r, x+*r>>1, '\\'); P[t].insert(x); } void del(int x, int t) { auto m = P[t].find(x); auto l = m; l--; auto r = m; r++; _del(*l, *l+x>>1, '/'); _del(x, *l+x>>1, '\\'); _del(x, x+*r>>1, '/'); _del(*r, x+*r>>1, '\\'); _add(*l, *l+*r>>1, '/'); _add(*r, *l+*r>>1, '\\'); P[t].erase(m); } int get(int x) { int t = lower_bound(XX+1, XX+XC+1, x) - XX; int mn = 2e9; for (int l=ST+t,r=ST+XC;l<=r;l>>=1,r>>=1){ if (l&1) mn = min(mn, mnTree[l++]); if (!(r&1)) mn = min(mn, mnTree[r--]); } int mx = -2e9; for (int l=ST+1,r=ST+t;l<=r;l>>=1,r>>=1){ if (l&1) mx = max(mx, mxTree[l++]); if (!(r&1)) mx = max(mx, mxTree[r--]); } return max(x - mn, mx - x); } int main() { scanf("%d%d%d", &N, &K, &Q); for (int i=1;i<=N;i++){ int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b); x <<= 1; A[i] = {x, t, a, b}; } for (int i=1;i<=Q;i++){ int x, t; scanf("%d%d", &x, &t); x <<= 1; B[i] = {x, t, i}; XX[++XC] = x; } sort(XX+1, XX+XC+1); XC = unique(XX+1, XX+XC+1)-XX-1; sort(A+1, A+N+1, [](const STORE &a, const STORE &b){ return a.a < b.a; }); sort(B+1, B+Q+1, [](const QUERY &a, const QUERY &b){ return a.t < b.t; }); for (int i=1;i<TS;i++) mnTree[i] = 2e9, mxTree[i] = -2e9; for (int i=1;i<=K;i++){ P[i] = {(int)-4e8, (int)4e8}; _add(-4e8, 0, '/'); _add(4e8, 0, '\\'); } priority_queue <pii> que; for (int i=1,j=1;i<=Q;i++){ auto& q = B[i]; while (j <= N && A[j].a <= q.t){ add(A[j].x, A[j].t); que.push({-A[j].b, j}); j++; } while (!que.empty() && -que.top().first < q.t){ int x = que.top().second; que.pop(); del(A[x].x, A[x].t); } ans[q.idx] = get(q.x); } for (int i=1;i<=Q;i++) printf("%d\n", ans[i] > 2e8 ? -1 : ans[i] >> 1); }

B. 원 고르기 (Circle selection)

2차원 좌표평면 위에 $N$개의 원이 주어진다. 남아있는 원들 중 반지름이 가장 큰 원을 고른다. 만약, 그러한 원이 여러 개라면 그 중 인덱스가 가장 작은 것을 고른다. 고른 원을 포함하여 고른 원과 조금이라고 겹치는 원들을 모두 없앤다. 이러한 과정을 남아있는 원이 없을 때까지 반복한다. 이 때, 각 원에 대해 어떤 원에 의해 자신이 없어졌는지를 구하는 문제다.

각 원에 대해 자신을 포함하면서 변이 x축 또는 y축에 평행한 가장 작은 정사각형을 그린다. 이 정사각형 영역이 겹칠 경우에만 원이 서로 겹치는지 판단한다. 즉, 반지름이 제일 큰 원을 고르고, 그 원과 정사각형 영역이 겹치는 원들을 추려내어, 실제로 원이 겹치는지 확인하고 원이 겹친다면 없애는 과정으로 진행한다. 이 과정 중 정사각형 영역이 겹치지만, 실제로 원은 겹치지 않아 없애지 못한 경우를 실패라고 하자. 실패의 총 횟수는 $O(N)$이다. 원마다 자신을 없애는데 실패한 경우를 생각하자. 자신을 없애기 위해 시도하려면 우선 자신보다 반지름이 작지 않고, 정사각형 영역은 겹치되 원은 겹치지 않아야한다. 그리고 자신을 없애기 위해 시도한 원들끼리 원이 서로 겹치면 안된다. 이러한 조건을 만족하면서 원을 가장 많이 그리면 최대 4개 원의 크기와 상관 없이 상수 개수다.

이 문제의 점수를 가르는 것은 결국 반지름이 제일 큰 원을 선택하고 이 원과 정사각형 영역이 겹치는 원들을 빨리 찾아내고, 원들이 없어질 때 또한 빠르게 처리하는 것이다. 처리 과정 중 원들이 새로 생기지 않고 없어지기만 하는 점을 생각해보면, Merge sort tree를 떠올릴 수 있다. Merge sort tree에서 정사각형 모양의 2D range query를 통해 정사각형 영역이 겹치는 원들을 바로 찾아낼 수 있고, 원들의 삭제는 경로압축을 통해 간헐적으로 진행하면 실행 시간이 제일 좋다. 삭제 과정을 lazy하게 해주면 최적화에 도움이 된다. 즉, 2D range query에서 없어진 원이 발견될 때 경로 압축으로 삭제하자.

#include <bits/stdc++.h> using namespace std; #define MAXN 300005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; typedef pair<int, int> pii; int N; int X[MAXN], Y[MAXN], R[MAXN], A[MAXN], P[MAXN], Q[MAXN]; int ans[MAXN]; int XX[MAXN*2], XC; const int TS = 2097152, ST = TS/2-1; struct NODE { vector <pii> arr; vector <int> nxt; int find(int n){ return nxt[n] == n ? n : (nxt[n] = find(nxt[n])); } void relax(){ int n = sz(arr); nxt.resize(n+1); for (int i=0;i<=n;i++) nxt[i] = i; } void merge(const NODE &a, const NODE &b){ int n = sz(a.arr), m = sz(b.arr); arr.resize(n+m); for (int i=0,j=0,k=0;i<n||j<m;){ if (j == m || i < n && a.arr[i] < b.arr[j]) arr[k++] = a.arr[i++]; else arr[k++] = b.arr[j++]; } relax(); } } tree[TS]; inline bool intersect(int a, int b){ return (lld)(X[a]-X[b])*(X[a]-X[b]) + (lld)(Y[a]-Y[b])*(Y[a]-Y[b]) <= (lld)(R[a]+R[b])*(R[a]+R[b]); } void doIt(int n) { auto iterate = [&](NODE &v){ for (int i=lower_bound(all(v.arr), pii(Y[n]-R[n], 0))-v.arr.begin();;i++){ i = v.find(i); if (i >= sz(v.arr) || v.arr[i].first > Y[n]+R[n]) break; int t = v.arr[i].second; if (ans[t]) v.nxt[i] = v.find(i+1); else if (intersect(n, t)) ans[t] = n; } }; for (int l=ST+P[n],r=ST+Q[n];l<=r;l>>=1,r>>=1){ if (l&1) iterate(tree[l++]); if (!(r&1)) iterate(tree[r--]); } } int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ scanf("%d%d%d", X+i, Y+i, R+i); A[i] = i; XX[++XC] = X[i]-R[i]; XX[++XC] = X[i]+R[i]; } sort(XX+1, XX+XC+1); XC = unique(XX+1, XX+XC+1)-XX-1; sort(A+1, A+N+1, [](const int &a, const int &b){ return R[a] != R[b] ? R[a] > R[b] : a < b; }); for (int i=1;i<=N;i++){ P[i] = lower_bound(XX+1, XX+XC+1, X[i]-R[i]) - XX; Q[i] = lower_bound(XX+1, XX+XC+1, X[i]+R[i]) - XX; tree[ST+P[i]].arr.pb({Y[i]-R[i], i}); tree[ST+P[i]].arr.pb({Y[i]+R[i], i}); tree[ST+Q[i]].arr.pb({Y[i]-R[i], i}); tree[ST+Q[i]].arr.pb({Y[i]+R[i], i}); } for (int i=1;i<=XC;i++) sort(all(tree[ST+i].arr)), tree[ST+i].relax(); for (int i=ST;i;i--) tree[i].merge(tree[i+i], tree[i+i+1]); for (int i=1;i<=N;i++) if (!ans[A[i]]) doIt(A[i]); for (int i=1;i<=N;i++) printf("%d%s", ans[i], i < N ? " " : ""); puts(""); }

C. 이종 경기 (Duathlon)

N개의 정점과 M개의 무방향성 간선으로 이루어진 그래프가 주어진다. 이 그래프에서 서로 다른 세 정점 $s$, $c$, $f$를 선택하는데, $s$에서 $c$를 거쳐 $f$로 가는 단순경로(simple path)가 있어야한다. 이러한 조건을 만족하는 $(s, c, f)$ 순서쌍의 수를 구하는 문제다.

입력으로 주어지는 그래프가 연결그래프가 아닐 수 있지만, 각 연결요소에 대해 답을 따로 구하면 되므로 연결그래프에 대한 풀이를 생각하자. 무방향성 연결그래프에서 이중연결요소(BiConnected Components, BCC)를 생각할 수 있다.

$s$에서 $c$를 거쳐 $f$로 가는 모든 경로가 단순경로가 아니라는 것은 반드시 두 번 이상 지나는 정점 $x$가 존재한다는 것이다. 그래프에서 정점 $x$를 지웠을 경우, $c$와 $s$의 연결과, $c$와 $f$의 연결이 끊어진다. 그러므로 정점 $x$가 그래프의 절단점이라는 것을 알 수 있다. 때문에, $s$와 $c$, $f$ 세 정점이 모두 같은 이중연결요소 안에 있다면 조건을 만족하는 단순경로가 반드시 존재함을 알 수 있다.

이 문제를 비교적 간단히 해결하기 위해서는 답에 대한 여집합을 구하면 된다. 즉, 조건을 만족하는 단순경로가 없는 $(s, c, f)$ 순서쌍의 수를 구하면 되고, 위에서 말한 것에 따라 $s$와 $c$는 다른 이중연결요소에, $f$와 $c$는 다른 이중연결요소에 있어야한다. 위에서 링크한 위키 문서에 있는 이미지는 연결그래프의 이중연결요소들을 서로 다른 색으로 나타냈다. 참고로 여러 색을 포함하고 있는 정점은 모두 절단점이다.

정점 $c$가 빨간색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(4-1) \times ^{11}\!P_{2} = 330$

정점 $c$가 옥색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(2-1) \times (^{4}\!P_{2} + ^{10}\!P_{2}) = 102$

정점 $c$가 분홍색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(2-1) \times (^{5}\!P_{2} + ^{9}\!P_{2}) = 92$

정점 $c$가 노란색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(2-1) \times (^{6}\!P_{2} + ^{8}\!P_{2}) = 86$

정점 $c$가 파란색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(2-1) \times ^{13}\!P_{2} = 156$

정점 $c$가 초록색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(6-1) \times (^{8}\!P_{2} + ^{2}\!P_{2}) = 290$

정점 $c$가 회색색 이중연결요소에 있는 경우 $(s, c, f)$의 수는 $(2-1) \times ^{13}\!P_{2} = 156$

최종적으로 답은 $^{14}\!P_{3} - (330+102+92+86+156+290+156) = 972$개다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back #define nP2(n) ((lld)(n)*(n-1)) #define nP3(n) ((lld)(n)*(n-1)*(n-2)) typedef long long lld; int N, M, V; int sz[MAXN], bccSz[MAXN]; lld pairCnt[MAXN]; int dep[MAXN], up[MAXN]; vector <int> con[MAXN]; void prec(int n, int p = 0) { // DFS 트리에서 각 정점의 서브트리 크기를 미리 구해놓는 함수 sz[n]++; for (int t: con[n]) if (t != p && !sz[t]){ prec(t, n); sz[n] += sz[t]; } } lld dfs(int n, int p = 0) { // BCC는 DFS 트리를 이용하여 구할 수 있다 lld ret = 0; int cnt = 1; up[n] = dep[n] = dep[p]+1; bccSz[n] = 1; for (int t: con[n]) if (t != p){ if (dep[t]){ // 단순 up edge 계산 up[n] = min(up[n], dep[t]); }else{ ret += dfs(t, n); up[n] = min(up[n], up[t]); if (up[t] < dep[n]){ // 이 경우, n과 p를 연결하는 간선과, n과 t를 연결하는 간선은 같은 BCC 안에 속하게 된다 bccSz[n] += bccSz[t]; pairCnt[n] += pairCnt[t]; } else{ // 정점 n이 절단점인 경우 cnt += sz[t]; } } } pairCnt[n] += nP2(cnt); if (p && up[n] >= dep[p]){ // 정점 n의 부모 정점 p가 절단점인 경우 // 즉, 이 때 정점 n과 정점 p가 동시에 속한 BCC에 대해 경우의 수를 계산한다 ret += (lld)bccSz[n] * (pairCnt[n] + nP2(V-sz[n])); // bccSz[n]: 실제 BCC 크기 - 1 (왜냐하면 정점 p가 개수에 포함되지 않았기 때문) // pairCnt[n]: DFS 트리에서 정점 n의 서브트리에 대한 (s, f) 순서쌍의 총 개수 // nP2(V-sz[n]): DFS 트리에서 절단점 p와 연결되어있는 부분에 대해 (s, f) 순서쌍 개수 } return ret; } int main() { scanf("%d%d", &N, &M); for (int i=1;i<=M;i++){ int a, b; scanf("%d%d", &a, &b); con[a].pb(b); con[b].pb(a); } lld ans = 0; for (int i=1;i<=N;i++) if (!sz[i]){ prec(i); V = sz[i]; ans += nP3(sz[i]) - dfs(i); } printf("%lld\n", ans); }