IOI 2015 Day 2 문제 및 해법

0. 표지

notice_en-KOR_rev27.pdf

1. horses

문제: task-1_en-KOR_rev68.pdf

말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i < j$인 모든 $j$에 대해 $Y[i] \geq X[i+1] \times \dots \times X[j] \times Y[j]$ 를 만족해야한다. 여기서 주목해야할 점은 $Y[i] \leq 10^9$라는 것이다. $X[i] > 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 500005 #define TS 1048576 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld; static const int MOD = 1e9 + 7; static int N; static int X[MAXN], Y[MAXN]; static int tree[TS], ptree[TS], ST = TS/2-1; static priority_queue <int> que; void write(int n, int v) { n += ST; tree[n] = v; for (n>>=1;n;n>>=1) tree[n] = max(tree[n+n], tree[n+n+1]); } void write_p(int n, int v) { n += ST; ptree[n] = v; for (n>>=1;n;n>>=1) ptree[n] = (lld)ptree[n+n] * ptree[n+n+1] % MOD; } int get_max(int l, int r) { int ret = 0; for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){ if (l&1) ret = max(ret, tree[l++]); if (!(r&1)) ret = max(ret, tree[r--]); } return ret; } int get_product(int l, int r) { int ret = 1; for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){ if (l&1) ret = (lld)ret * ptree[l++] % MOD; if (!(r&1)) ret = (lld)ret * ptree[r--] % MOD; } return ret; } int calc() { int max_y = 1e9; vector <int> arr = {N+1}, y; lld product = 1; while (!que.empty()){ int q = que.top(); que.pop(); if (X[q] == 1) continue; product *= X[q]; arr.pb(q); if (product > max_y) break; } if (product <= max_y && arr.back() != 1) arr.pb(1); reverse(all(arr)); for (int i=1;i<sz(arr);i++) y.pb(get_max(arr[i-1], arr[i]-1)); lld acc = 1, mx = X[arr[0]]; int t = 0; for (int i=0;i<sz(arr)-1;i++){ acc *= X[arr[i]]; if (y[t] < acc/mx*y[i]) mx = acc, t = i; } int ret = (lld)get_product(1, arr[t]) * y[t] % MOD; for (int t: arr) if (X[t] > 1) que.push(t); return ret; } int init(int n, int x[], int y[]) { N = n; for (int i=1;i<=N;i++) X[i] = x[i-1], Y[i] = y[i-1]; for (int i=1;i<=N;i++) if (X[i]) que.push(i); for (int i=1;i<=N;i++) tree[ST+i] = Y[i], ptree[ST+i] = X[i]; for (int i=ST;i;i--){ tree[i] = max(tree[i+i], tree[i+i+1]); ptree[i] = (lld)ptree[i+i] * ptree[i+i+1] % MOD; } return calc(); } int updateX(int n, int v) { n++; if (v > 1 && X[n] == 1) que.push(n); X[n] = v; write_p(n, v); return calc(); } int updateY(int n, int v) { n++; Y[n] = v; write(n, v); return calc(); }

2. sorting

문제: task-2_en-KOR_rev80.pdf

우선 가장 먼저 파라매트릭 서치를 생각할 수 있다. $R$ 라운드 이내에 정렬이 가능하다고 가정하고 답이 되는지 확인한다. 파라매트릭 서치가 되는 이유는 $R$ 라운드에 정렬이 가능하면 $R+1, R+2, \dots, M$ 라운드에도 항상 정렬이 가능하기 때문이다. $R$ 라운드에 정렬이 완료되고 나서 이후 라운드에서는 에르맥이 스왑한 것만 따라 스왑하면 항상 정렬 상태를 유지할 수 있기 때문이다.

파라매트릭 서치로 $R$을 정했을 때, $R$ 라운드에 답이 되는지 확인하는 방법을 설명하겠다. 기본적인 아이디어는 아이잔이 앞으로 수열을 전혀 안건드렸을 때, 오직 에르맥의 스왑으로 각 수들이 어느 위치로 가는지 계산한다. 그러면 아이잔은 에르맥의 움직임에 맞춰 최후에 정렬되도록 적절히 스왑해주면 된다.

예제 1번의 경우를 예로 들겠다. $R = 3$일 때 가능한지 확인한다.

에르맥	(0, 1)	에르맥의 이동 경로: 0 3 1 2 4  수열: 3 4 2 1 0
아이잔	(1, 0)	에르맥의 이동 경로: 0 3 1 2 4 아이잔 수열: 4 3 2 1 0
에르맥	(1, 2)	에르맥의 이동 경로: 0 1 3 2 4 아이잔 수열: 4 2 3 1 0
아이잔	(0, 4)	에르맥의 이동 경로: 0 1 3 2 4 아이잔 수열: 0 2 3 1 4
에르맥	(2, 3)	에르맥의 이동 경로:  0 1 2 3 4 아이잔 수열: 0 2 1 3 4
아이잔	(1, 2)	에르맥의 이동 경로: 0 1 2 3 4 아이잔 수열: 0 1 2 3 4

위 표에서 에르맥의 이동 경로가 0 3 1 2 4라 함은 아이잔 수열에서 0번 위치에 있는 수가 아이잔이 가만히 있는다고 했을 때 0의 위치로 가고 1번 위치에 있는 수가 3번 위치에, 2번 위치에 있는수가 1번 위치에, 3번 위치에 있는 2번 위치에, 4번 위치에 있는 수가 4번 위치에 간다는 뜻이다. 이후 정렬되어 있으면 $R$ 라운드 안에 마침이 가능하다는 것이고, 아니라면, 불가능하다는 것이다. 방법을 보면 에르맥의 스왑 정보와 상관 없이 적어도 $N-1$ 라운드 안에는 끝남이 보장된다. 시간복잡도는 $O(N \lg N)$이다.

#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define MAXM 600005 #define mp make_pair typedef pair<int, int> pii; static int N, M; static int A[MAXN], B[MAXN], C[MAXN]; static int pos_b[MAXN], pos_c[MAXN]; static int X[MAXM], Y[MAXM]; static int P[MAXM], Q[MAXM]; bool proc(int m) { for (int i=1;i<=N;i++){ B[i] = pos_b[i] = i; C[i] = A[i], pos_c[C[i]] = i; } for (int i=m;i;i--){ swap(B[X[i]], B[Y[i]]); swap(pos_b[B[X[i]]], pos_b[B[Y[i]]]); } queue <int> que; for (int i=1;i<=N;i++) if (B[i] != C[i]) que.push(B[i]); for (int i=1;i<=m;i++){ swap(B[X[i]], B[Y[i]]); swap(pos_b[B[X[i]]], pos_b[B[Y[i]]]); swap(C[X[i]], C[Y[i]]); swap(pos_c[C[X[i]]], pos_c[C[Y[i]]]); while (!que.empty() && pos_b[que.front()] == pos_c[que.front()]) que.pop(); if (!que.empty()){ int q = que.front(); que.pop(); int x = pos_b[q], y = pos_c[q]; swap(C[x], C[y]); swap(pos_c[C[x]], pos_c[C[y]]); P[i] = x, Q[i] = y; }else{ P[i] = Q[i] = 1; } } for (int i=1;i<=N;i++) if (C[i] != i) return 0; return 1; } int findSwapPairs(int n, int S[], int m, int x[], int y[], int to_p[], int to_q[]) { N = n, M = m; for (int i=1;i<=M;i++) X[i] = x[i-1]+1, Y[i] = y[i-1]+1; for (int i=1;i<=N;i++) A[i] = S[i-1]+1; bool sw = 0; for (int i=1;i<=N;i++) if (A[i] != i) sw = 1; if (!sw) return 0; int s = 1, e = N-1, ret; while (s <= e){ int m = (s+e)>>1; if (proc(m)) e = m-1, ret = m; else s = m+1; } proc(ret); for (int i=1;i<=ret;i++) to_p[i-1] = P[i]-1, to_q[i-1] = Q[i]-1; return ret; }

3. towns

문제: task-3_en-KOR_rev87.pdf

0번 도시에서 제일 먼 도시를 찾는다. 그 도시의 번호가 $X$번이라 하자. $X$번 도시에 대해 제일 먼 도시를 찾는다. 그 도시의 번호가 $Y$번이라 하자. 트리의 지름이 $dist(X, Y)$임을 알 수 있다. 지금까지 질의 회수는 $2N - 3$ 이다.

여러 가지 증명이 필요한 명제들이 있다. 글에서 증명은 생략하겠다.

1) 트리의 지름이 여러가지일 수 있다. 그러나 허브는 임의의 한 지름의 위에만 존재한다.

2) 허브는 최대 2개다.

3) 1번에서 더 확장하여 허브는 0번 도시와 X번 도시 사이의 경로 위에만 존재한다. (즉, 아래 그림에서 빨간색 대도시는 허브가 될 수 없다.)

$dist(0, i)$와 $dist(X, i)$를 이용해서 $i$번 도시에서 0번 도시에서 $X$번 도시로 가는 경로 상에 위치한 가장 가까운 대도시와의 거리를 구할 수 있다. (그림에서 파란색 가상 간선의 길이) 마찬가지로 $X$번 도시에서 경로 상에 위치한 대도시 와의 거리들(그림에서 초록색 선에 해당)도 구할 수 있다. 이 정보로 경로상에 위치한 대도시의 개수, 허브, 그리고 $R$ 값을 알 수 있다. 이 때 추가 질의 회수는 없다.

구한 허브에 대해서 그 허브가 균형 잡힌 허브인지 확인하는 것이 까다롭다. 그림에서 검정색 대도시들 중 허브가 있을 텐데, 허브에 딸린 파란색 도시들의 개수가 $\frac{N}{2}$ 보다 많다면, 추가적으로 질의를 하여 $\frac{N}{2}$ 보다 큰 파란색 도시 그룹이 나오는지 확인을 해주어야한다. 위에서 말한대로 최대 2개의 허브가 있을 수 있는데, 이러한 추가 확인 작업은 최대 한 개의 허브에 대해서만 해주면 된다. 그 이유는 파란색 도시들을 $\frac{N}{2}$개 보다 많게 가지고 있는 허브는 최대 한 개이기 때문이다.

추가 확인 작업은 $n$개의 원소가 있고, 원소끼리 비교하는 질의만 가능할 때 같은 값을 가지는 원소의 개수가 $\frac{n}{2}$ 보다 많이 있는지, 있다면 몇 개인지 계산하는 문제로 바꾸어 풀 수 있다. 최대 $\frac{3}{2} n$질의 만에 할 수 있다. Majority Vote Algorithm 포스트에 자세히 적혀있다.

#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(v) ((int)(v).size()) int getDistance(int i, int j); static int N, X, Y; static int w[111][111]; static int L[111], P[111]; inline int get(int a, int b) { if (a == b) return 0; if (!w[a][b]) w[a][b] = w[b][a] = getDistance(a, b); return w[a][b]; } inline bool is_in_same_group(int a, int b) { return P[a] + P[b] - get(a, b); } bool is_over_size(vector <int> cand) { vector <int> arr[7], chk[7]; arr[0] = cand; for (int i=0;i<7;i++){ chk[i].resize(sz(arr[i]), 0); for (int j=0;j+1<sz(arr[i]);j+=2){ if (is_in_same_group(arr[i][j], arr[i][j+1])){ arr[i+1].pb(arr[i][j]); chk[i][j] = chk[i][j+1] = 1; } } } int rep = -1, sum = 0; for (int i=7;i--;) if (sz(arr[i]) & 1){ rep = arr[i].back(); break; } if (rep == -1) return 0; for (int i=0;i<7;i++){ for (int j=0;j<sz(arr[i]);j++) if (!chk[i][j]){ if (is_in_same_group(arr[i][j], rep)) sum += (1 << i); } } return sum > N/2; } int hubDistance(int leafs, int sub) { N = leafs; for (int i=0;i<N;i++){ for (int j=0;j<N;j++) w[i][j] = 0; P[i] = L[i] = 0; } X = 1, Y = 0; for (int i=2;i<N;i++){ if (get(0, X) < get(0, i)) X = i; } for (int i=1;i<N;i++) if (get(X, Y) < get(X, i)) Y = i; int R = 2e9; for (int i=1;i<N;i++) if (i != X){ P[i] = (get(0, i) + get(X, i) - get(0, X)) / 2; L[i] = get(X, i) - P[i]; R = min(R, max(L[i], get(X, Y)-L[i])); } int t = 0, cnt = 0, small = 0; L[0] = get(0, X); for (int i=0;i<N;i++){ if (L[i] == R) cnt++; if (L[i] < R) small++; } if (cnt && small <= N/2 && N-cnt-small <= N/2){ if (cnt > N/2) t = R; else return R; } cnt = small = 0; for (int i=0;i<N;i++){ if (L[i] == get(X, Y) - R) cnt++; if (L[i] < get(X, Y) - R) small++; } if (cnt && small <= N/2 && N-cnt-small <= N/2){ if (cnt > N/2) t = get(X, Y) - R; else return R; } if (!t) return -R; vector <int> cand; for (int i=0;i<N;i++) if (L[i] == t) cand.pb(i); if (is_over_size(cand)) return -R; return R; }