IOI 2018 Day 2 문제 및 해법

문제: 공식 홈페이지

채점: Yandex

1. doll

0번 정점을 시작점이라고 부르고 0번 정점은 나가는 간선이 정확히 1개다. 1번부터 M번까지 번호가 매겨진 나가는 간선이 정확히 1개인 트리거 정점 M개가 존재한다. 그리고 스위치라고 불리는 정점들은 번호가 음수로, 개수가 S개일 때, -1번부터 -S번까지 번호가 매겨진다. 스위치 정점은 나가는 간선이 정확히 2개이며 스위치 상태가 'X'일 때는 'X'로 표시된 간선으로 나가게 되며, 스위치 상태가 'Y'일 때는 'Y'로 표시된 간선으로 나가게 된다. 정점을 나가면서 동시에 스위치 정점의 상태가 뒤집힌다. 초기 0번 정점에서 이동을 시작하며, 이동을 하다가 다시 처음 0번 정점으로 돌아오는 순간 모든 스위치 정점의 상태는 'X'여야하며 트리거 정점은 정확히 N번 방문해야하며, 방문한 순서가 주어진다. 이렇게 이동할 수 있도록 스위치 정점을 적게 사용하여 회로를 구성하는 문제다.

이 문제에서 제일 핵심이 되는 문장은 "다시 시작점으로 돌아왔을 때 모든 스위치의 상태가 초기 상태와 같아야한다"다. 이 조건을 통해, 스위치들을 정점으로 한 루트가 있는 이진트리를 구성하면 어떨까 라는 생각을 할 수 있다.

문제에서 주어진 예제처럼 트리거 정점의 개수 M=4개, 방문한 트리거 정점의 수 N=4개이며, 방문한 순서는 [1, 2, 1, 3]이라고 하자. 이 때, 다음과 같이 스위치 정점들을 통해 루트가 있는 이진트리를 생각할 수 있다.

위 그림에서 스위치로 구성된 이진트리의 높이 $k=3$이라고 하자 이진트리 높이 $k$는 $2^k \geq N+1$를 만족하는 가장 작은 $k$로 결정한다. 그리고 불필요한 정점들을 최대한 제거한다. 그러면 사용한 스위치의 개수는 $N + \log_{2} N$이하가 되며, -1번 정점에 총 $2^k$번 방문하게 되며 다시 시작점 0번 정점으로 돌아갔을 때 모든 스위치의 상태는 'X'가 되고, 트리거 정점의 방문 순서 또한 주어진대로 만들 수 있다.

이진트리를 그리는 자세한 방법은 코드를 참고하자.

#include "doll.h" #include <bits/stdc++.h> using namespace std; const int MAXK = 1<<18; #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() int N, M, K, H; int IDX, num[MAXK]; int nxt[MAXK][2]; struct LEAF { int order; int node_num, sw; }; vector <LEAF> leaves; void make_tree(int n, int& left, int o, int l) { if (!left) return; num[n] = ++IDX; if (n<<1 >= K){ nxt[IDX][0] = nxt[IDX][1] = -1; leaves.pb({o, IDX, 0}); leaves.pb({o|l, IDX, 1}); left--; return; } make_tree(n+n+1, left, o|l, l<<1); nxt[num[n]][1] = num[n+n+1] ? -num[n+n+1] : -1; make_tree(n+n, left, o, l<<1); nxt[num[n]][0] = num[n+n] ? -num[n+n] : -1; } void create_circuit(int M, vector<int> A) { ::M = M; ::N = sz(A); for (H=1;;H++) if (1<<H > N) break; K = 1<<H; int left = (N>>1)+1; make_tree(1, left, 0, 1); sort(all(leaves), [](const LEAF &a, const LEAF &b){ return a.order < b.order; }); for (int i=0;i<N;i++){ auto &l = leaves[i]; nxt[l.node_num][l.sw] = A[i]; } auto &l = leaves.back(); nxt[l.node_num][l.sw] = 0; vector <int> C(M+1, -1), X(IDX, 0), Y(IDX, 0); for (int i=0;i<IDX;i++) X[i] = nxt[i+1][0], Y[i] = nxt[i+1][1]; answer(C, X, Y); }

2. highway

N개의 정점과 M개의 간선으로 이루어진 무방향성 그래프가 주어진다. ask 함수를 통해 각 간선의 가중치를 A 혹은 B로 설정했을 때, 정점 S와 정점 T 사이의 최단 거리를 알 수 있다. ask 함수 호출 횟수가 제한적일 때, ask 함수 호출을 통해 적절한 정보를 얻어 정점 S와 T가 어떤 정점인지를 알아내는 문제다.

Subtask 1 (총 5점)

ask 함수는 최대 100번 호출할 수 있고, 주어지는 그래프는 트리이며, N ≤ 100 이고, S = 0이다.

모든 정점에 대해 그 정점이 T인지 확인을 해볼 수 있다. 정점 S와 정점 T 사이의 거리(간선 가중치 거리가 아닌 경로에 있는 간선 개수) $d$는 모든 간선의 가중치를 A로 두고 ask 함수 호출을 하면 알 수 있다. 그리고 정점 i에 대해 정점 T가 되는지 확인을 하는데, 정점 i가 정점 T인지 확인하기 위해서, 정점 S에서 정점 i까지 가는 모든 간선의 가중치를 B로 두고, 나머지 간선의 가중치는 A라고 두었을 때 거리가 $d \times B$가 되면 정점 i는 정점 T가 되는 것이 확실하다. 함수 호출 횟수는 최대 N번이 된다.

Subtask 2 (총 12점)

ask 함수는 최대 60번 호출할 수 있고, 주어지는 그래프는 트리이며, S = 0이다.

정점 S와의 거리를 기준으로 오름차순으로 정점들을 정렬한 다음에, 이분탐색을 통해 정점 T를 찾을 수 있다. 함수 호출 횟수는 최대 $1 + \lceil\log_2 N\rceil = 18$번이 된다.

#include "highway.h" #include <bits/stdc++.h> using namespace std; #define MAXN 90004 #define MAXM 130004 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N, M, A, B; int U[MAXM], V[MAXM]; vector <int> con[MAXN]; lld C; int dist[MAXN]; void bfs() { for (int i=1;i<=N;i++) dist[i] = 2e9; queue <int> que; dist[1] = 0; que.push(1); while (!que.empty()){ int q = que.front(); que.pop(); for (int t: con[q]) if (dist[t] == 2e9) dist[t] = dist[q]+1, que.push(t); } } int find(const vector<int> &arr) { int s = 0, e = sz(arr)-1; while (s < e){ int m = s+e >> 1; vector <bool> chk(N+1, 0); for (int i=m+1;i<=e;i++) chk[arr[i]] = 1; vector <int> w(M, 0); for (int i=0;i<M;i++) if (chk[U[i]] || chk[V[i]]) w[i] = 1; if (ask(w) > C) s = m+1; else e = m; } return arr[s]; } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { ::N = N, ::M = sz(U), ::A = A, ::B = B; for (int i=0;i<M;i++){ ::U[i] = ++U[i], ::V[i] = ++V[i]; con[U[i]].pb(V[i]); con[V[i]].pb(U[i]); } C = ask(vector<int>(M, 0)); bfs(); vector <int> arr; for (int i=1;i<=N;i++) arr.pb(i); sort(all(arr), [](const int &a, const int &b){ return dist[a] < dist[b]; }); int s = 1, t = find(arr); answer(s-1, t-1); }

Subtask 4 (총 51점)

ask 함수는 최대 60번 호출할 수 있고, 주어지는 그래프는 트리이며, S = 0이다.

한 번의 함수 호출을 통해 정점 S와 정점 T 사이의 거리 $d$를 알 수 있다. 그리고 정점 S와 정점 T 사이의 경로에 포함된 한 간선 e를 간선들의 집합에 대한 이분탐색을 통해 찾아낼 수 있다. 그리고 간선 e를 그래프에서 없애주어 그래프를 두 개의 서브트리로 나눈다.

편의상 간선 e가 정점 x와 정점 y를 연결하는 간선이라고 하고, 또한 정점 x가 정점 S와 같은 서브트리 안에, 정점 y가 정점 T와 같은 서브트리 안에 있다고 하자. 정점 x가 있는 서브트리에 대해 Subtask 2와 동일한 상황이 되고, 마찬가지로 정점 y가 있는 서브트리에 대해 Subtask 2의 풀이와 동일하게 정점 S와 정점 T를 각각 독립적이게 찾을 수 있다. 따라서 총 함수 호출 횟수는 최대 $1 + 17 + 16 + 16 = 50$번이 된다.

#include "highway.h" #include <bits/stdc++.h> using namespace std; #define MAXN 90004 #define MAXM 130004 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N, M, A, B; int U[MAXM], V[MAXM]; vector <int> con[MAXN]; lld C; int X, Y; int dist[2][MAXN]; int find_e() { int s = 0, e = M-1; while (s < e){ int m = s+e >> 1; vector <int> w(M, 0); fill(w.begin()+s, w.begin()+m+1, 1); if (ask(w) > C) e = m; else s = m+1; } return s; } void bfs(int n, int dist[], int r) { for (int i=1;i<=N;i++) dist[i] = 2e9; queue <int> que; dist[n] = 0; que.push(n); while (!que.empty()){ int q = que.front(); que.pop(); for (int t: con[q]) if (t != r){ if (dist[t] == 2e9) dist[t] = dist[q]+1, que.push(t); } } } int find(const vector<int> &arr) { int s = 0, e = sz(arr)-1; while (s < e){ int m = s+e >> 1; vector <bool> chk(N+1, 0); for (int i=m+1;i<=e;i++) chk[arr[i]] = 1; vector <int> w(M, 0); for (int i=0;i<M;i++) if (chk[U[i]] || chk[V[i]]) w[i] = 1; if (ask(w) > C) s = m+1; else e = m; } return arr[s]; } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { ::N = N, ::M = sz(U), ::A = A, ::B = B; for (int i=0;i<M;i++){ ::U[i] = ++U[i], ::V[i] = ++V[i]; con[U[i]].pb(V[i]); con[V[i]].pb(U[i]); } C = ask(vector<int>(M, 0)); int e = find_e(); X = U[e], Y = V[e]; bfs(X, dist[0], Y); bfs(Y, dist[1], X); vector <int> cx, cy; for (int i=1;i<=N;i++){ if (dist[0][i] < 2e9) cx.pb(i); else cy.pb(i); } sort(all(cx), [](const int &a, const int &b){ return dist[0][a] < dist[0][b]; }); sort(all(cy), [](const int &a, const int &b){ return dist[1][a] < dist[1][b]; }); int s = find(cx); int t = find(cy); answer(s-1, t-1); }

Subtask 6 (총 100 점)

ask 함수는 최대 50번 호출할 수 있다.

Subtask 4에서와 비슷한 방법으로 정점 S와 정점 T를 연결하는 최단 경로에 속한 임의의 간선 e를 구할 수 있다. 단, 정점 S와 정점 T를 연결하는 최단 경로가 여러 개가 존재할 수 있으므로 Subtask 4에서의 이분탐색을 살짝 보완해야한다.

편의상 간선 e가 정점 x와 정점 y를 연결하는 간선이라고 하자. 그리고 일반성을 잃지 않고 정점 S, x, y, T가 모두 속한 최단 경로에서 각 정점의 방문 순서가 S, x, y, T 순이라고 하자. 정점 S는 정점 y보다 정점 x와 더 가까울 것이며, 정점 T는 정점 x보다 정점 y와 더 가까울 것이다. 정점 y보다 정점 x와 더 가까운 정점들의 집합을 P라고 하고, 그렇지 않은 정점들의 집합을 Q라고 하자. 집합 P와 Q는 서로소 집합이고 집합 P와 집합 Q의 합집합은 전체 정점 집합이 된다. 자명히 정점 S는 집합 P에 있고, 정점 T는 집합 Q에 있다.

집합 P에 있는 정점들을 정점 x와의 최단 거리 기준으로 정렬해서 Subtask 2에서 했던 이분탐색으로 정점 S를 찾을 수 있다. 마찬가지로 집합 Q에 있는 정점들을 정점 y와의 최단 거리 기준으로 정렬해서 이분탐색으로 정점 T를 찾을 수 있다. 정리하면 Subtask 4에서 정점 x의 서브트리를 집합 P로 볼 수 있으며, 정점 y의 서브트리를 집합 Q로 보는 것과 같다. 즉, Subtask 4와 아주 비슷한 상황이 된다. 따라서 Subtask 4에서와 마찬가지로 최대 50번의 호출 안에 문제를 해결할 수 있다.

#include "highway.h" #include <bits/stdc++.h> using namespace std; #define MAXN 90004 #define MAXM 130004 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N, M, A, B; int U[MAXM], V[MAXM]; vector <int> con[MAXN]; lld C; int X, Y; int dist[2][MAXN]; int find_e() { int s = 0, e = M-1; vector <int> w(M, 0); auto fill = [&w](int s, int e, int v){ ::fill(w.begin()+s, w.begin()+e+1, v); }; while (s < e){ int m = s+e >> 1; fill(s, m, 1); if (ask(w) > C) fill(s, m, 0), e = m; else s = m+1; } return s; } void bfs(int n, int dist[]) { for (int i=1;i<=N;i++) dist[i] = 2e9; queue <int> que; dist[n] = 0; que.push(n); while (!que.empty()){ int q = que.front(); que.pop(); for (int t: con[q]) if (dist[t] == 2e9) dist[t] = dist[q]+1, que.push(t); } } int find(const vector<int> &arr) { int s = 0, e = sz(arr)-1; while (s < e){ int m = s+e >> 1; vector <bool> chk(N+1, 0); for (int i=m+1;i<=e;i++) chk[arr[i]] = 1; vector <int> w(M, 0); for (int i=0;i<M;i++) if (chk[U[i]] || chk[V[i]]) w[i] = 1; if (ask(w) > C) s = m+1; else e = m; } return arr[s]; } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { ::N = N, ::M = sz(U), ::A = A, ::B = B; for (int i=0;i<M;i++){ ::U[i] = ++U[i], ::V[i] = ++V[i]; con[U[i]].pb(V[i]); con[V[i]].pb(U[i]); } C = ask(vector<int>(M, 0)); int e = find_e(); X = U[e], Y = V[e]; bfs(X, dist[0]); bfs(Y, dist[1]); vector <int> cx, cy; for (int i=1;i<=N;i++){ if (dist[0][i] < dist[1][i]) cx.pb(i); else cy.pb(i); } sort(all(cx), [](const int &a, const int &b){ return dist[0][a] < dist[0][b]; }); sort(all(cy), [](const int &a, const int &b){ return dist[1][a] < dist[1][b]; }); int s = find(cx); int t = find(cy); answer(s-1, t-1); }

3. meetings

N개의 산이 있고, 왼쪽부터 오른쪽까지 차례대로 0부터 N-1번까지 번호가 매겨져있다. 그리고 각 산에는 정확히 한 명씩 사람이 살고 있다. Q개의 모임이 있는데, i번째 모임은 L[i]번 산부터 R[i]번 산까지 살고 있는 모든 사람들을 한 곳에 모여야한다. 각 사람이 이동하면서 드는 비용은 이동 경로 위에 놓인 가장 높은 산의 높이만큼이고, 모임의 전체 비용은 모이는 각 사람의 비용 합이다. 문제는 각 모임마다 모임의 최소 비용을 구하는 것이다.

Subtask 2 (총 19점)

N ≤ 5,000, Q ≤ 5,000

각 모임마다 $O(N)$ 시간복잡도로 최소 비용을 구하면 되며, 이는 왼쪽에서 오른쪽으로 가는 방향과 오른쪽에서 왼쪽으로 가는 방향, 두 방향에 대해 스택을 이용하여 비용을 계산할 수 있다. 전체 시간복잡도는 $O(QN)$이다.

#include <bits/stdc++.h> using namespace std; #define MAXN 5004 #define sz(v) ((int)(v).size()) typedef long long lld; int N, Q; int H[MAXN]; lld A[MAXN]; vector <lld> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { N = sz(h); Q = sz(L); if (N > 5000 || Q > 5000) return {}; for (int i=1;i<=N;i++) H[i] = h[i-1]; vector <lld> ans(Q); for (int i=0;i<Q;i++){ int l = ++L[i], r = ++R[i]; vector <int> stk; lld v = 0; for (int j=l;j<=r;j++){ while (!stk.empty() && H[stk.back()] <= H[j]){ int t = stk.back(); stk.pop_back(); int b = stk.empty() ? l-1 : stk.back(); v -= (lld)H[t] * (t-b); } int b = stk.empty() ? l-1 : stk.back(); stk.push_back(j); v += (lld)H[j] * (j-b); A[j] = v; } stk.clear(); v = 0; for (int j=r;j>=l;j--){ while (!stk.empty() && H[stk.back()] <= H[j]){ int t = stk.back(); stk.pop_back(); int b = stk.empty() ? r+1 : stk.back(); v -= (lld)H[t] * (b-t); } int b = stk.empty() ? r+1 : stk.back(); stk.push_back(j); v += (lld)H[j] * (b-j); A[j] += v; } ans[i] = 1e18; for (int j=l;j<=r;j++) ans[i] = min(ans[i], A[j]-H[j]); } return ans; }

Subtask 3 (누적 36점)

N ≤ 100,000, Q ≤ 100,000, H[i] ≤ 2

이 서브태스크에서는 높이가 1 또는 2로 두 종류만 있다. 그리디하게 생각해보면 모임 비용을 최소화하는 모임 장소는 $[L_i, R_i]$ 구간안에 있는 1로만 이루어진 가장 긴 부분구간에 있는 곳이다. Segment tree를 이용해 1로만 이루어진 가장 긴 부분구간의 크기를 구하면 문제를 해결할 수 있으며, 모임 당 시간복잡도는 $O(\lg N)$이고, 전체 시간복잡도는 $O((N+Q) \lg N)$이다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N, Q; int H[MAXN]; const int TS = 1<<18, ST = TS/2-1; struct NODE { int ml, mr, ma; bool all; } tree[TS]; void relax(NODE &n, const NODE &l, const NODE &r) { n.all = l.all & r.all; n.ml = l.all ? l.ma + r.ml : l.ml; n.mr = r.all ? r.ma + l.mr : r.mr; n.ma = max({l.ma, r.ma, l.mr+r.ml}); } vector <lld> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { N = sz(h); Q = sz(L); for (int i=1;i<=N;i++) H[i] = h[i-1]; for (int i=1;i<=N;i++) if (H[i] == 1) tree[ST+i] = {1, 1, 1, 1}; for (int i=ST;i;i--) relax(tree[i], tree[i+i], tree[i+i+1]); vector <lld> ans(Q); for (int i=0;i<Q;i++){ int l = ++L[i], r = ++R[i]; vector <NODE> arr1, arr2; for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){ if (l&1) arr1.pb(tree[l++]); if (~r&1) arr2.pb(tree[r--]); } reverse(all(arr2)); arr1.insert(arr1.end(), all(arr2)); NODE v = arr1[0]; for (int i=1;i<sz(arr1);i++){ NODE tmp; relax(tmp, v, arr1[i]); v = tmp; } ans[i] = (R[i]-L[i]+1)*2 - v.ma; } return ans; }

Subtask 4 (누적 60점)

N ≤ 100,000, Q ≤ 100,000, H[i] ≤ 20

이 서브태스크에서는 높이가 모두 20이하이다. 따라서 다음과 같은 정의를 가지고 있는 배열에 알맞는 값들을 $O(HN)$ 만에 계산할 수 있다.

D[i][j] = i번째 산에서 전체 모임을 가지고 모든 산들의 높이가 j이하라고 할 때, 즉, 높이가 j보다 높은 산들은 높이를 j라고 가정할 때, 모임 비용을 N*j에서 뺀 것

그리고 segment tree를 이용하여 다음 함수의 값을 $O(\lg N)$ 시간에 계산할 수 있다.

get(h, l, r) = l이상 r이하인 i에 대해 D[i][h]의 최대값

구간 $[L_i, R_i]$가 있을 때, 아래 그림처럼 구간에 대해 maximal 부분을 구한다.

각 빨간색 범위에 대해, 그 범위 안에 모임 장소가 있을 경우 최소 모임 비용을 get(h, l, r) 함수를 통해서 $O(\lg N)$ 구할 수 있다. 높이의 범위가 $H$이므로, 생기는 빨간색 범위의 개수는 $O(H)$가 되며, 전체 시간복잡도는 D 배열 값을 구하는 전처리 시간을 포함하여 $O(H(N + Q \lg N))$ 이 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; int N, Q; int H[MAXN]; lld D[MAXN][21]; vector <int> lstk[MAXN], rstk[MAXN]; const int TS = 1<<18, ST = TS/2-1; lld tree[21][TS]; lld get(int h, int l, int r) { lld ret = 0; for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){ if (l&1) ret = max(ret, tree[h][l++]); if (~r&1) ret = max(ret, tree[h][r--]); } return ret; } vector <lld> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { N = sz(h); Q = sz(L); for (int i=1;i<=N;i++) H[i] = h[i-1]; { vector <int> stk; for (int i=1;i<=N;i++){ while (!stk.empty() && H[stk.back()] <= H[i]) stk.pop_back(); stk.pb(i); lstk[i] = stk; } } { vector <int> stk; for (int i=N;i;i--){ while (!stk.empty() && H[stk.back()] <= H[i]) stk.pop_back(); stk.pb(i); rstk[i] = stk; } } for (int i=1;i<=N;i++){ vector <int> l = lstk[i], r = rstk[i]; lld sum = 0; for (int j=1;j<H[i];j++) D[i][j] = 1e18; for (int j=H[i]+1;j<21;j++){ while (!l.empty() && H[l.back()] < j) l.pop_back(); while (!r.empty() && H[r.back()] < j) r.pop_back(); int lx = l.empty() ? 0 : l.back(); int rx = r.empty() ? N+1 : r.back(); int width = rx-lx-1; sum += width; D[i][j] = sum; } } for (int i=1;i<21;i++){ for (int j=1;j<=N;j++) tree[i][ST+j] = D[j][i]; for (int j=ST;j;j--) tree[i][j] = max(tree[i][j+j], tree[i][j+j+1]); } vector <lld> ans(Q); for (int i=0;i<Q;i++){ int l = ++L[i], r = ++R[i]; ans[i] = 1e18; int lx = 0, rx = 0; { auto ls = rstk[l]; lld area = 0; { int t = r+1; for (int x: ls) if (x <= r) area += (lld)(t-x)*H[x], t = x; } while (!ls.empty() && ls.back() <= r){ int x = ls.back(); ls.pop_back(); if (!lx){ lx = x; continue; } area -= (lld)(x-lx)*H[lx]; ans[i] = min(ans[i], (lld)(x-l)*H[lx] + area - get(H[lx], lx, x-1)); lx = x; } } { auto rs = lstk[r]; lld area = 0; { int t = l-1; for (int x: rs) if (x >= l) area += (lld)(x-t)*H[x], t = x; } while (!rs.empty() && rs.back() >= l){ int x = rs.back(); rs.pop_back(); if (!rx){ rx = x; continue; } area -= (lld)(rx-x)*H[rx]; ans[i] = min(ans[i], (lld)(r-x)*H[rx] + area - get(H[rx], x+1, rx)); rx = x; } } ans[i] = min(ans[i], (lld)(r-l+1)*H[lx] - get(H[lx], lx, rx)); } return ans; }

Subtask 5 (총 100점)

N ≤ 750,000, Q ≤ 750,000

풀이 준비 중.