IOI2016 Day 1 문제 및 해법

0. 문제 패키지

day1.zip

1. molecules

$n$개의 자연수로 이루어진 집합 $S$가 있다. 한 집합 안에 같은 수가 여러 개 있을 수 있다. 이 때, 속한 원소의 합이 $l$이상 $u$이하가 되는 부분집합을 찾는 문제다. 이 문제에서 중요한 조건은 $u-l \geq \max(S) - \min(S)$이다.

부분집합의 크기 $k$를 정했을 때, 부분집합 원소 합의 최소값을 $s_k$, 부분집합 원소 합의 최대값을 $e_k$라고 하자. $[s_k, e_k]$와 $[l, u]$가 겹치는 것과 속한 원소의 합이 $l$이상 $u$이하가 되는 크기가 $k$인 부분집합이 존재하는 것은 필요충분조건이다. 왜냐하면 $u-l \geq \max(S) - \min(S)$이기 때문이다. 이에 대한 증명은 어렵지 않다.

위와 같은 명제를 알고 있으면 속한 원소의 합이 $l$이상 $u$이하가 되는 부분집합을 찾는 것은 어렵지 않고 굉장히 다양한 방법이 존재한다.

#include "molecules.h" #include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N; int A[MAXN]; lld S[MAXN]; vector<int> find_subset(int l, int u, vector<int> w) { int t = 0; N = sz(w); for (int i=1;i<=N;i++) A[i] = i; sort(A+1, A+N+1, [&w](const int &a, const int &b){ return w[a-1] < w[b-1]; }); for (int i=1;i<=N;i++) S[i] = S[i-1] + w[A[i]-1]; for (int i=1;i<=N;i++){ lld p = S[i]; lld q = S[N]-S[N-i]; if (p <= u && q >= l){ t = i; break; } } vector <int> ret; if (!t) return ret; for (int i=t;i<=N;i++){ lld v = S[i] - S[i-t]; if (v < l || v > u) continue; for (int j=0;j<t;j++) ret.pb(A[i-j]-1); break; } return ret; }

2. railroad

$n$개의 특별 구역이 있다. $i$번 특별 구역에 접근할 때 롤러코스터의 속력은 $s_i$이하여야하고, 특별 구역을 통과하고 나면 롤러코스터의 속력은 항상 $t_i$가 된다. 중간에 롤러코스터의 속력을 줄이기 위해서 특별 구역 사이에 도로를 건설해야하는데 단위 길이의 도로를 지날 때 마다 롤러코스터의 속력은 1씩 줄어든다. 롤러코스터의 초기 속력은 1이고, 특별 구역의 순서를 적절히 정해 모든 특별 구역을 통과할 때, 건설해야하는 도로 길이 합을 최소화하는 문제다.

서브태스크 3번이 답이 0이 되는지 확인하는 문제다. 전체 문제를 해결하기 위해 우선 서브태스크 3번을 해결하는 방법을 소개하겠다. 문제를 조금 변형하여, 롤러코스터의 속력을 증가시키는데는 비용이 들지 않고 감속시킬 때만 비용이 있다고 보고, $i$번 특별 구역에 진입할 때 속력이 정확히 $s_i$인 것으로 보겠다.

1부터 최대 속력까지 각 속력을 정점으로 보고 $i$번 특별 구역을 $s_i$에서 $t_i$로 가는 간선으로 본다. 여기서 $i$에서 $i+1$로 가는 간선을 적절히 추가하여, 1번 정점에서부터 최대 속력에 해당하는 정점으로 가는 오일러 경로가 존재하는지 확인하면 된다. 오일러 경로가 존재하면 도로 건설 없이 모든 특별 구역을 순회할 수 있음이 자명하고, 오일러 경로가 존재하지 않으면 도로 건설 없이 모든 특별 구역을 순회할 수 없음을 알 수 있다. 따라서 오일러 경로의 존재 여부와 답이 0이 되는지는 필요충분조건이다.

각 정점에 대해서 (out degree - in degree)를 차수로 보자. 1번 정점의 차수는 1이고, 최대 속력에 해당하는 정점의 차수는 -1, 나머지 정점의 차수는 0이 되어야 오일러 경로가 존재한다. $i$에서 $i+1$로 가는 간선을 추가해서 모든 정점의 차수를 맞추는 경우는 유일하다. 정점 차수를 맞춘 이후에는 최종적으로 1번 정점에서 모든 정점으로 갈 수 있는지 확인해야한다.

#include "railroad.h" #include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N, M; int S[MAXN], T[MAXN]; int cnt[MAXN*2]; bool V[MAXN*2]; vector <int> X, con[MAXN*2]; void dfs(int n) { V[n] = 1; for (int t: con[n]) if (!V[t]) dfs(t); } lld plan_roller_coaster(vector<int> s, vector<int> t) { N = sz(s); for (int i=1;i<=N;i++){ S[i] = s[i-1], T[i] = t[i-1]; X.pb(S[i]); X.pb(T[i]); } sort(all(X)); X.erase(unique(all(X)), X.end()); M = sz(X); for (int i=1;i<=N;i++){ S[i] = lower_bound(all(X), S[i]) - X.begin() + 1; T[i] = lower_bound(all(X), T[i]) - X.begin() + 1; cnt[S[i]]++; cnt[T[i]]--; con[S[i]].pb(T[i]); } for (int i=1;i<M;i++){ int t = (i == 1 ? 1 : 0); int df = t - cnt[i]; if (df > 0){ cnt[i] += df; cnt[i+1] -= df; con[i].pb(i+1); }else if (df < 0){ return 1; } } dfs(1); for (int i=1;i<=M;i++) if (!V[i]) return 1; return 0; }

서브태스크 3의 풀이를 개선하여 전체 문제를 해결할 수 있다. 우선 전체 정점의 차수를 맞추기 위해 이제는 $i+1$에서 $i$로 가는 간선도 추가를 해줘야한다. 아까와 마찬가지의 이유로 이러한 경우도 유일하다. 차수를 맞춘 뒤에 1번 정점에서 모든 정점을 방문하도록 해야한다. 1번 정점에서 갈 수 있는 정점들을 제외하고 나머지 정점들은 각각 어떤 강연결요소(SCC)에 속한다. 1번 정점에서 갈 수 있는 정점들은 연결요소라고 볼 순 없지만 편의상 연결요소라고 부르겠다. $i$에서 $i+1$로 가는 간선과 $i+1$에서 $i$로 가는 간선을 동시에 추가하여, 어떤 두 연결 요소를 합칠 수 있다. 이 때 최소 비용으로 모든 연결요소를 하나의 연결요소로 합쳐야하는데, 이는 MST를 구하는 방법과 정확히 동일하다.

#include "railroad.h" #include <bits/stdc++.h> using namespace std; #define MAXN 200005 #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, M, K; int S[MAXN], T[MAXN], G[MAXN*2]; int par[MAXN*2], cnt[MAXN*2]; vector <int> X, con[MAXN*2]; int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); } void dfs(int n, int k) { G[n] = k; for (int t: con[n]) if (!G[t]) dfs(t, k); } lld plan_roller_coaster(vector<int> s, vector<int> t) { N = sz(s); for (int i=1;i<=N;i++){ S[i] = s[i-1], T[i] = t[i-1]; X.pb(S[i]); X.pb(T[i]); } sort(all(X)); X.erase(unique(all(X)), X.end()); M = sz(X); for (int i=1;i<=N;i++){ S[i] = lower_bound(all(X), S[i]) - X.begin() + 1; T[i] = lower_bound(all(X), T[i]) - X.begin() + 1; cnt[S[i]]++; cnt[T[i]]--; con[S[i]].pb(T[i]); } lld ans = 0; for (int i=1;i<M;i++){ int t = (i == 1 ? 1 : 0); int df = t - cnt[i]; if (df > 0){ cnt[i] += df; cnt[i+1] -= df; con[i].pb(i+1); }else if (df < 0){ cnt[i] += df; cnt[i+1] -= df; con[i+1].pb(i); ans += -(lld)df * (X[i]-X[i-1]); } } for (int i=1;i<M;i++) if (!G[i]) dfs(i, ++K); for (int i=1;i<=K;i++) par[i] = i; vector <pii> edges; for (int i=1;i<M;i++) if (G[i] != G[i+1]) edges.pb({X[i]-X[i-1], i}); sort(all(edges)); for (pii &p: edges){ int a = cp(G[p.second]), b = cp(G[p.second+1]); if (a == b) continue; ans += p.first; par[b] = a; } return ans; }

3. shortcut

$n$개의 기차역이 번호 순서대로 일렬로 중앙 라인에 배치되어 있다. 각 기차역에 곁가지가 붙어있을 수 있는데, $i$번 기차역에 붙어있는 곁가지의 길이는 $d_i$이다. 곁가지가 붙어있을 경우 곁가지의 끝 쪽에는 번호가 매겨지지 않은 기차역이 존재한다. 중앙 라인에 있는 두 기차역 사이에 길이 $c$의 지름길을 만들어 가장 먼 두 기차역 사이의 거리를 최소화시키는 문제다.

우선 $n \leq 3\,000$인 경우 해결하는 방법에 대해 설명하겠다. 이 방법은 71점을 받는다.

이분검색으로 답을 미리 정한다. 정한 답을 $X$라 하자. 그러면 가장 먼 두 기차역 사이의 거리가 $X$이하가 되는지 확인만 해주면 되는 결정 문제를 풀면 된다. 이제 지름길이 없을 경우 거리가 $X$ 보다 큰 두 기차역 쌍들만 고려하면 된다. 즉, $d_i + d_j + p_j - p_i > X$인 $(i, j)$ 순서쌍에 대해서만 고려한다(여기서 $i < j$이고 $p_i$는 $0$번 기차역과 $i$번 기차역의 거리). 지름길이 연결하는 왼쪽 기차역의 번호를 $l$이라 하고, 오른쪽 기차역의 번호를 $r$이라 하자. 이제 $l$, $r$은 다음 조건을 만족해야한다. $|p_i-p_l| + |p_j-p_r| \leq X - d_i - d_j - c$ 이는 $(p_l, p_r)$가 $(p_i, p_j)$를 기준으로한 마름모 안에 들어가야함을 의미한다. 따라서 $O(n^2)$개의 마름모의 공통영역을 구하고, 그 영역 안에 실제로 $l$과 $r$이 있는지 확인해주면 된다. 결정 문제를 해결하는 시간복잡도는 $O(n^2)$이다.

#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define MAXN 3006 typedef long long lld; int N, C; int L[MAXN], D[MAXN]; lld X[MAXN]; int proc(lld m) { lld p = -1e18, q = 1e18, r = -1e18, s = 1e18; for (int i=1;i<N;i++) for (int j=i+1;j<=N;j++){ lld v = X[j]-X[i] + D[i] + D[j]; if (v <= m) continue; lld z = m - D[i] - D[j] - C; if (z < 0) return 0; p = max(p, X[i]-X[j]-z); q = min(q, X[i]-X[j]+z); r = max(r, X[i]+X[j]-z); s = min(s, X[i]+X[j]+z); } int t = 1; for (int i=1;i<=N;i++){ lld a = max(p + X[i], r - X[i]); lld b = min(q + X[i], s - X[i]); while (t > 1 && X[t-1] >= a) t--; while (t <= N && X[t] < a) t++; if (t <= N && X[t] <= b) return 1; } return 0; } lld find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { N = n; C = c; if (N > 3000) return 0; for (int i=1;i<=N;i++){ L[i] = l[i-1]; D[i] = d[i-1]; X[i] = X[i-1] + L[i-1]; } lld s = 1, e = 1e16, ans; while (s <= e){ lld m = (s+e)>>1; if (proc(m)) e = m-1, ans = m; else s = m+1; } return ans; }

결정 문제를 $O(n \lg n)$에 해결할 수 있다. 모든 점 $i$에 대해서 $i < j$와 $d_j + p_j > X + p_i - d_i$를 만족하는 $j$에 대해서 $p_j + d_j$가 최대가 되는 $j$, $p_j - d_j$가 최소가 되는 $j$에 대해서만 마름모 영역을 고려해주면 된다. $p_j + d_j$가 최대가 되는 $j$는 쉽게 구할 수 있고, $p_j - d_j$가 최소가 되는 $j$는 Indexed Tree, Segment Tree등의 자료구조를 통해 구해야한다. 93점과 97점 풀이의 차이는 이를 얼마나 효율적으로 구현했는지의 차이로 판단된다. 아래 코드는 97점 풀이이며 $n \leq 300\,000$ 일 때 0.8초 안에 해결한다. 그리고 $n \leq 1\,000\,000$ 일 때 3.2초가 걸려 100점을 받지 못한다.

#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define MAXN 300005 #define TS 1048576 typedef long long lld; int N, C; int L[MAXN], D[MAXN]; int A[MAXN], pos[MAXN]; int tree[TS], ST = TS/2-1; lld X[MAXN], V1[MAXN], V2[MAXN]; void reg(int n, int v) { n += ST; tree[n] = v; for (n>>=1;n;n>>=1){ if (V2[tree[n]] > V2[v]) tree[n] = v; else break; } } int find(lld v) { int n = 1, ret = 0; if (V1[tree[1]] > v) return tree[1]; while (n < TS){ if (V1[tree[n+n+1]] > v){ if (V2[ret] > V2[tree[n+n+1]]) ret = tree[n+n+1]; n = n+n; }else n = n+n+1; } return ret; } int proc(lld d) { lld p = -1e18, q = 1e18, r = -1e18, s = 1e18; int mxt = 0; for (int i=1;i<TS;i++) tree[i] = 0; for (int i=N;i;i--){ lld v = d + X[i] - D[i]; if (mxt && V1[mxt] > v){ // find j that maximize X[j] + D[j] int j = mxt; lld v = d - D[i] - D[j] - C; q = min(q, X[i]-X[j]+v); r = max(r, X[i]+X[j]-v); // find j that minimize X[j] - D[j] && X[j] + D[j] > d + X[i] - D[i] j = find(d + X[i] - D[i]); v = d - D[i] - D[j] - C; p = max(p, X[i]-X[j]-v); s = min(s, X[i]+X[j]+v); if (p > q || r > s) return 0; } if (pos[mxt] < pos[i]) mxt = i; reg(pos[i], i); } int t = 1; for (int i=1;i<=N;i++){ lld a = max(p + X[i], r - X[i]); lld b = min(q + X[i], s - X[i]); while (t > 1 && X[t-1] >= a) t--; while (t <= N && X[t] < a) t++; if (t <= N && X[t] <= b) return 1; } return 0; } lld find_shortcut(int n, vector<int> l, vector<int> d, int c) { N = n; C = c; int mx1 = 0, mx2 = 0; lld mx3 = -1e16, mx4 = 0; for (int i=1;i<=N;i++){ L[i] = l[i-1]; D[i] = d[i-1]; X[i] = X[i-1] + L[i-1]; V1[i] = X[i] + D[i]; V2[i] = X[i] - D[i]; if (mx1 < D[i]) mx2 = mx1, mx1 = D[i]; else if (mx2 < D[i]) mx2 = D[i]; mx4 = max(mx4, X[i]+D[i] + mx3); mx3 = max(mx3, D[i]-X[i]); } V1[0] = V2[0] = 1e18; for (int i=1;i<=N;i++) A[i] = i; sort(A+1, A+N+1, [](const int &a, const int &b){ return V1[a] < V1[b]; }); for (int i=1;i<=N;i++) pos[A[i]] = i; lld s = mx1+mx2, e = mx4, ans; while (s <= e){ lld m = (s+e)>>1; if (proc(m)) e = m-1, ans = m; else s = m+1; } return ans; }

결정 문제를 $O(n)$에 해결할 수 있다. 97점 풀이와 거의 동일한데 한 가지 중요한 관찰이 필요하다. 바로 $i < j$ 라는 조건을 고려하지 않아도 된다는 것이다. 만약 $i > j$일 때 $d_j + p_j > X + p_i - d_i$를 만족한다면, $d_i + d_j + (p_j - p_i) > X$이고 이 때 $p_j - p_i < 0$ 이므로 $X$는 답이 될 수 없다는 결론이 나온다. 다르게 말하면, $X$를 이분탐색으로 정할 때 하한을 잘 정하여, $d_i + d_j$보다 작은 값이 $X$가 되지 않으면, $i > j$일 때 $d_j + p_j > X + p_i - d_i$를 만족하는 경우가 절대 없다는 것이다.

이러한 관찰을 통해 $p_i - d_i$를 역순으로 정렬한 배열, $p_j + d_j$를 역순으로 정렬한 배열을 미리 만들어놓은 뒤, Two Pointers Algorithm을 통해 간단히 해결 가능하다. 다만 $i=j$가 되지 않도록 신경을 잘 써야한다. 아래 코드는 $n \leq 1\,000\,000$ 일 때 0.5초 안에 해결한다.

#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define MAXN 1000005 typedef long long lld; int N, C; int L[MAXN], D[MAXN]; int A[MAXN], B[MAXN]; lld X[MAXN], V1[MAXN], V2[MAXN]; int proc(lld d) { lld p = -1e18, q = 1e18, r = -1e18, s = 1e18; lld mn1 = 1e18, mn2 = 1e18; for (int i=1,j=1;i<=N;i++){ while (j <= N && V1[B[j]] > d+V2[A[i]]){ lld v = V2[B[j]]; if (mn1 > v) mn2 = mn1, mn1 = v; else if (mn2 > v) mn2 = v; j++; } if (j == 1 || j == 2 && B[1] == A[i]) continue; int x = A[i], y = B[1] == A[i] ? B[2] : B[1]; lld v = d - D[x] - D[y] - C; q = min(q, X[x]-X[y]+v); r = max(r, X[x]+X[y]-v); v = d - D[x] - C + (mn1 == V2[x] ? mn2 : mn1); p = max(p, X[x]-v); s = min(s, X[x]+v); if (p > q || r > s) return 0; } // Check there is exact station for l, r we have int t = 1; for (int i=1;i<=N;i++){ lld a = max(p + X[i], r - X[i]); lld b = min(q + X[i], s - X[i]); while (t > 1 && X[t-1] >= a) t--; while (t <= N && X[t] < a) t++; if (t <= N && X[t] <= b) return 1; } return 0; } lld find_shortcut(int n, vector<int> l, vector<int> d, int c) { N = n; C = c; int mx1 = 0, mx2 = 0; for (int i=1;i<=N;i++){ L[i] = l[i-1]; D[i] = d[i-1]; X[i] = X[i-1] + L[i-1]; V1[i] = X[i] + D[i]; V2[i] = X[i] - D[i]; if (mx1 < D[i]) mx2 = mx1, mx1 = D[i]; else if (mx2 < D[i]) mx2 = D[i]; } V1[0] = V2[0] = 1e18; for (int i=1;i<=N;i++) A[i] = B[i] = i; sort(A+1, A+N+1, [](const int &a, const int &b){ return V2[a] > V2[b]; }); sort(B+1, B+N+1, [](const int &a, const int &b){ return V1[a] > V1[b]; }); lld s = mx1+mx2, e = 1e16, ans; while (s <= e){ lld m = (s+e)>>1; if (proc(m)) e = m-1, ans = m; else s = m+1; } return ans; }