IOI 2017 Day 2 문제 및 해법

문제: 공식 홈페이지

채점: Yandex

1. prize

1부터 v까지의 수가 적힌 크기가 N인 배열이 있다. 수 1의 갯수는 항상 1개고, 1보다 큰 t에 대해 수 t의 갯수는 수 t-1의 갯수의 제곱보다 많다. ask(i)를 호출하면, i보다 왼쪽에 있으면서 작은 수, i보다 오른쪽에 있으면서 큰 수를 알려준다. 이 때, 적은 횟수로 ask(i)를 호출하여 하나 뿐인 수 1의 위치를 찾는 문제다.

우선 배열에서 가장 많이 등장하는 수, 즉, 가장 큰 수는 등장 빈도가 과반이다. 가장 큰 수가 아닌 수의 최대 갯수는 조건에 따라 472개(1개, 4개, 21개, 446개, ...)다. 첫 번째로 가장 큰 수의 개수를 구하기 위해 최대 473번의 질문을 하여, 가장 큰 수의 위치 중 하나를 찾을 수 있다. 이후 풀이는 가장 큰 수가 아닌 수들의 위치를 모두 구한 뒤, ask(i)의 결과가 (0, 0)이 되는 위치를 구하는 식으로 진행된다.

가장 큰 수가 아닌 위치들은 배열을 크기가 최대 472인 그룹들로 분할하여 적은 질문 횟수로 구할 수 있다. 왼쪽에 있는 그룹부터 차례대로 그룹에 존재하는 가장 큰 수가 아닌 수들의 위치를 구해나가는데, 그룹마다 가장 큰 수가 아닌 수가 존재하는지 질문 한 번으로 확인을 할 수 있다. 만약 존재하지 않는다면, 해당 그룹에 대해서는 생략할 수 있고, 만약 존재한다면 그 그룹에서 이분탐색을 통해 최대 9번의 질문으로 특정 구간에서 가장 왼쪽에 있는 가장 큰 수가 아닌 수의 위치를 찾을 수 있다. 이를 반복하여, 모든 가장 큰 수가 아닌 수들을 찾을 수 있다.

100점을 받기 위해서는 총 5,000번 이내로 질문을 해야하는데, 여태까지를 비교적 naive하게 구현 할 경우 약 99점을 받게 된다. 100점을 받기 위해서는 처음에 가장 큰 수를 찾기 위해하는 473번의 질문을 그룹의 오른쪽 끝 점에 대해 질문을 해서 이후 질문을 미리하는 느낌으로 효율을 올리면 된다.

#include "prize.h" #include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back int N, M, K=472, G; int S[450], E[450]; vector <int> cache[MAXN]; bool vis[MAXN]; vector<int> my_ask(int p) { auto &ret = cache[p]; if (vis[p]) return ret; vis[p] = 1; return ret = ask(p-1); } bool is_popular(int p) { auto res = my_ask(p); return res[0]+res[1] == M; } int find_leftmost(int s, int e, int p) { int ret = 0; while (s <= e){ int m = (s+e)>>1; if (!is_popular(m)){ ret = m; e = m-1; }else{ if (my_ask(m)[0] != p) e = m-1; else s = m+1; } } return ret; } int find_best(int n) { ::N = n; S[++G] = 1; E[G] = 1; for (int i=2;i<=N;i++){ if (E[G]-S[G]+1 == K) S[++G] = i; E[G] = i; } set <int> to_ask; for (int i=1;i<=G;i++) to_ask.insert(E[i]); for (int i=1;i<=N;i++){ if (to_ask.size() > K) break; to_ask.insert(i); } for (int t: to_ask) M = max(M, my_ask(t)[0]+my_ask(t)[1]); vector <int> non_popular; for (int last=0,prefix=0,g=1;g<=G;){ if (last == E[g] || is_popular(E[g]) && my_ask(E[g])[0] == prefix){ g++; continue; } int p = find_leftmost(max(last+1, S[g]), E[g], prefix); non_popular.pb(p); prefix++; last = p; } for (int t: non_popular) if (!my_ask(t)[0] && !my_ask(t)[1]) return t-1; return 0; }

2. simurgh

$N$개의 정점과 $M$개의 간선으로 이루어진 연결그래프가 주어진다. 이 연결그래프의 (우리가 알 수 없는) 어떤 스패닝 트리를 royal 스패닝 트리라고 하고, royal 스패닝 트리를 이루는 간선들을 royal 간선이라고 한다. 우리는 임의의 스패닝 트리에 대해 해당 스패닝 트리에 몇 개의 royal 간선이 있는지 물어볼 수 있다. 이를 통해 모든 royal 간선들을 찾는 문제다.

우선, 그래프에서 임의의 DFS 트리 $T$를 만들고, 모든 트리 간선에 대해 royal 여부를 판단하려고 한다. 이는 총 $2N$번의 질문을 통해 구할 수 있다.

처음에 $T$에 대해서 질문을 해서 $T$ 안에 있는 royal 간선의 개수를 파악해둔다. 절선이 아니면서 정점 $u$와 정점 $v$를 연결하는 트리 간선 $e$에 대해서 (정점 $u$가 정점 $v$의 부모 정점이다) $low[v]$를 만드는 back 간선 $f$를 찾자. 즉, 간선 $f$는 정점 $v$에서 back 간선 하나만 통해 이동할 때, 최대한 위로 올라갈 수 있게 해주는 back 간선을 의미한다. $T$에서 간선 $e$를 빼고, 간선 $f$를 추가한 새로운 트리에 대해 질문한다. 이를 통해 $R[e]-R[f]$의 값을 알 수 있다. (여기서, $R[e]$는 간선 $e$가 royal 간선이면 1, 아니면 0을 의미하는 배열이다.) 그리고 간선 $f$에 대해서는 트리 $T$에 간선 $f$를 추가했을 때, 생기는 싸이클에 포함된 트리 간선 중 가장 위에 있는 간선 $d$를 찾아, 트리 $T$에서 간선 $d$를 지우고 간선 $f$를 추가해 $R[f]-R[d]$ 값을 알아낸다. 등장하는 모든 간선 $f$를 포함한 집합을 $F$라고 하자.

구한 차이 값들을 종합하여, 트리 간선과 $F$에 포함된 back 간선 중 같은 biconnected component에 속한 간선끼리는 서로 $R$ 값의 차이를 알고 있다. 만약 $R$ 값이 모두 같은 것이 아니라면, 해당 간선들에 대해 $R$ 값이 0인지, 1인지 구분이 바로 가능하다. 만약 $R$ 값이 모두 같다면, 해당 간선들의 $R$ 값이 0이다. 왜냐하면, 해당 간선들이 모두 royal 간선이라면 싸이클이 생기기 때문이다. 이를 통해 모든 트리 간선과 $F$에 속한 간선들의 royal 여부를 계산할 수 있다.

하나의 트리 간선에 대해 최대 2번의 질문을 했기 때문에 질문한 총 횟수는 $2N$번 정도이며, 이를 통해 트리 간선 중 royal 간선인 것들을 찾아냈다.

남은 것은 $F$에 속하지 않은 back 간선들의 royal 여부를 판단하는 것 뿐이다. $F$에 속하지 않은 back 간선들을 '무관심' 간선이라고 말하자.

1) 51점 풀이

모든 무관심 간선 각각에 대해, 한 번의 질문을 통해 royal 여부를 판단할 수 있다. 무관심 간선 $e$에 대해, 트리 $T$에 $e$를 추가하고, 생기는 싸이클 내부의 임의의 트리 간선 $d$를 지워서 새로운 트리를 만들고 질문하면, $R[d]-R[e]$ 값을 알 수 있다. 이미 $R[d]$ 값을 알고 있으므로 바로 $R[e]$ 값을 알 수 있다.

절선을 제외한 모든 간선에 대해 정확히 한 번씩 질문을 했으므로, 질문 횟수는 최대 $M$번이 되며 51점을 받는다.

#include "simurgh.h" #include <bits/stdc++.h> using namespace std; #define MAXN 501 #define MAXM 125000 #define pb push_back #define sz(v) ((int)(v).size()) int N, M; int to[MAXN][MAXN]; int par[MAXN], up_e[MAXN]; int down_e[MAXM], now_child[MAXN]; int disc[MAXN], low[MAXN], low_e[MAXN]; bool interested[MAXM]; bool R[MAXM]; void dfs(int n) { static int code = 0; disc[n] = low[n] = ++code; for (int t=1;t<=N;t++) if (to[n][t]){ int e = to[n][t]; if (!disc[t]){ par[t] = n; up_e[t] = e; now_child[n] = t; dfs(t); if (low[n] > low[t]) low[n] = low[t], low_e[n] = low_e[t]; }else if (t != par[n] && disc[t] < disc[n]){ down_e[e] = now_child[t]; if (low[n] > disc[t]) low[n] = disc[t], low_e[n] = e; } } } int base; int ask(int d=0, int a=0) { vector <int> arr; for (int i=2;i<=N;i++) if (up_e[i] != d) arr.pb(up_e[i]); if (a) arr.pb(a); for (int i=0;i<N-1;i++) arr[i]--; return count_common_roads(arr); } int _par[MAXM], in[MAXM]; int find(int n){ return _par[n] == n ? n : (_par[n] = find(_par[n])); } void add_relation(int a, int b, int diff) { if (diff < 0) swap(a, b), diff *= -1; // diff = R[b] - R[a]; if (!diff){ a = find(a); b = find(b); if (a == b) return; _par[b] = a; in[a] += in[b]; } else in[find(b)]++; } vector <int> find_roads(int n, vector<int> u, vector<int> v) { ::N = n; M = sz(u); for (int i=0;i<M;i++){ int a = u[i]+1, b = v[i]+1; to[a][b] = to[b][a] = i+1; } dfs(1); for (int i=2;i<=N;i++) interested[up_e[i]] = interested[low_e[i]] = 1; base = ask(); for (int i=1;i<=M;i++) _par[i] = i; for (int i=2;i<=N;i++) if (low_e[i]){ int e = low_e[i], v = ask(up_e[i], e); add_relation(up_e[i], e, v-base); v = ask(up_e[down_e[e]], e); add_relation(up_e[down_e[e]], e, v-base); } for (int i=1;i<=M;i++) if (find(i) == i) R[i] = in[i]; for (int i=1;i<=M;i++) R[i] = R[find(i)]; for (int i=2;i<=N;i++) if (!low_e[i]) R[up_e[i]] = 1; for (int i=1;i<=M;i++) if (!interested[i]){ int op = up_e[down_e[i]]; int diff = ask(op, i) - base; if (diff > 0 || !diff && R[op]) R[i] = 1; } vector <int> ret; for (int i=1;i<=M;i++) if (R[i]) ret.pb(i-1); return ret; }

2) 100점 풀이

트리 $T$의 각 간선에 대해 royal 여부를 알고 있다. 이를 이용하여 자기들끼리 싸이클을 이루지 않는 여러 개의 무관심 간선들이 있을 때, 이들 중 royal 간선의 개수를 세어주는 작업을 할 수 있다.

어떤 정점 $v$에 대해 $v$에 인접한 무관심 간선들을 모으고, 이들 중 royal 간선을 찾는 상황을 생각해보자. $v$에 인접한 무관심 간선의 개수가 $c$개이고, 실제로 이들 중 royal 간선이 $k$개 있다라고 했을 때, 위에서 언급한 작업과 무관심 간선 집합을 반으로 줄여가는 행위를 이분탐색 비슷하게 반복하면, 약 $k \lg c$번의 질문을 통해 $k$개의 royal 간선을 모두 찾을 수 있다.

이를 모든 정점에 대해 해주면 추가 질문 횟수는 최대 $N \lfloor \lg N \rfloor + N$가 된다. 따라서 총 질문 횟수는 최대 $N \lfloor \lg N \rfloor + 3N$으로, 5,500번의 질문안에 모든 royal 간선을 찾을 수 있다.

#include "simurgh.h" #include <bits/stdc++.h> using namespace std; #define MAXN 501 #define MAXM 125000 #define pb push_back #define sz(v) ((int)(v).size()) int N, M; int U[MAXM], V[MAXM]; int to[MAXN][MAXN]; int par[MAXN], up_e[MAXN]; int down_e[MAXM], now_child[MAXN]; int disc[MAXN], low[MAXN], low_e[MAXN]; bool interested[MAXM]; bool R[MAXM]; void dfs(int n) { static int code = 0; disc[n] = low[n] = ++code; for (int t=1;t<=N;t++) if (to[n][t]){ int e = to[n][t]; if (!disc[t]){ par[t] = n; up_e[t] = e; now_child[n] = t; dfs(t); if (low[n] > low[t]) low[n] = low[t], low_e[n] = low_e[t]; }else if (t != par[n] && disc[t] < disc[n]){ down_e[e] = now_child[t]; if (low[n] > disc[t]) low[n] = disc[t], low_e[n] = e; } } } int base; int ask(int d=0, int a=0) { vector <int> arr; for (int i=2;i<=N;i++) if (up_e[i] != d) arr.pb(up_e[i]); if (a) arr.pb(a); for (int i=0;i<N-1;i++) arr[i]--; return count_common_roads(arr); } int _par[MAXM], in[MAXM]; int find(int n){ return _par[n] == n ? n : (_par[n] = find(_par[n])); } void add_relation(int a, int b, int diff) { if (diff < 0) swap(a, b), diff *= -1; // diff = R[b] - R[a]; if (!diff){ a = find(a); b = find(b); if (a == b) return; _par[b] = a; in[a] += in[b]; } else in[find(b)]++; } int K; int A[MAXN]; int get_cnt(int s, int e) { vector <int> earr, arr; for (int i=s;i<=e;i++) earr.pb(A[i]); for (int i=2;i<=N;i++) earr.pb(up_e[i]); for (int i=1;i<=N;i++) _par[i] = i; int base = 0; for (int e: earr){ int a = find(U[e]), b = find(V[e]); if (a == b) continue; if (interested[e] && R[e]) base++; arr.pb(e-1); _par[b] = a; } return count_common_roads(arr) - base; } void find_royal(int s, int e, int cnt) { if (!cnt) return; if (s == e){ R[A[s]] = 1; return; } int m = s+e >> 1; int lc = get_cnt(s, m); find_royal(s, m, lc); find_royal(m+1, e, cnt-lc); } vector <int> find_roads(int n, vector<int> u, vector<int> v) { ::N = n; M = sz(u); for (int i=1;i<=M;i++){ int a = u[i-1]+1, b = v[i-1]+1; to[a][b] = to[b][a] = i; U[i] = a, V[i] = b; } dfs(1); for (int i=2;i<=N;i++) interested[up_e[i]] = interested[low_e[i]] = 1; base = ask(); for (int i=1;i<=M;i++) _par[i] = i; for (int i=2;i<=N;i++) if (low_e[i]){ int e = low_e[i], v = ask(up_e[i], e); add_relation(up_e[i], e, v-base); v = ask(up_e[down_e[e]], e); add_relation(up_e[down_e[e]], e, v-base); } for (int i=1;i<=M;i++) if (find(i) == i) R[i] = in[i]; for (int i=1;i<=M;i++) R[i] = R[find(i)]; for (int i=2;i<=N;i++) if (!low_e[i]) R[up_e[i]] = 1; for (int i=1;i<N;i++){ K = 0; for (int j=i+1;j<=N;j++) if (to[i][j]){ int e = to[i][j]; if (!interested[e]) A[++K] = e; } if (!K) continue; find_royal(1, K, get_cnt(1, K)); } vector <int> ret; for (int i=1;i<=M;i++) if (R[i]) ret.pb(i-1); return ret; }

3. books

0부터 N-1까지 총 N개의 수가 있는 순열이 주어진다. 사람이 시작 위치 S에서 이동하면서 순열을 정렬하려고 한다. 사람은 수를 최대 한 개만 들고 이동할 수 있고, 칸에 도착할 때마다 들고 있는 수와 칸에 놓여있는 수를 바꾸며 정렬한다. 이 때, 순열을 정렬하고 다시 시작점으로 돌아올 때 필요한 최소 이동 거리를 구하는 문제다.

우선, 순열을 정렬하기 위해서 |P[i] - i|의 합 만큼은 반드시 이동해야한다. 이외에 추가로 어쩔 수 없이 이동하는 것을 추가 이동이라고 하자. 이 문제에서는 꼭 필요한 이동 말고 추가 이동을 최소화하는 문제라고 볼 수 있다.

다음과 같은 순열을 정렬한다고 했을 때, 순열 정보를 토대로 여러 개의 싸이클이 나오는 것을 볼 수 있다.

서로 엉켜있는 싸이클들의 무리를 싸이클 덩어리라고 하자. 위 그림에서는 싸이클 덩어리가 총 3개 있다. 1번 싸이클 덩어리는 2번, 3번 싸이클 덩어리를 포함하고 있고, 자기 자신은 아무 싸이클 덩어리한테도 포함되어 있지 않다. 이러한 싸이클 덩어리를 루트 싸이클 덩어리라고 하자. 2번 싸이클 덩어리를 포함하는 가장 작은 싸이클 덩어리는 1번 싸이클 덩어리다. 이를 부모 싸이클 덩어리라고 부르자. 그러면 싸이클 덩어리 사이의 관계가 트리 혹은 forest 형태로 나타나게 된다.

1) S = 0인 경우 풀이 (50점)

S = 0인 경우, 시작점은 어떠한 싸이클 덩어리에도 포함되어 있지 않거나, 루트 싸이클 덩어리의 끝점이 된다. 이 경우는 문제를 해결하기가 쉽다. 왜냐하면 루트 싸이클 덩어리의 칸에서 사람이 정렬을 시작하는 경우 그 루트 싸이클 덩어리 영역 안에 포함되는 모든 싸이클들을 추가 이동 없이 필요한 만큼만 이동하면서 정렬할 수 있기 때문이다. 따라서 S = 0인 경우, 루트 싸이클 덩어리들 사이를 이동하는 추가 이동거리만 계산해주면 되므로 싸이클 덩어리를 자세히 구할 필요도 없이 루트 싸이클 덩어리들만 구하여 간단한 연산으로 추가 이동거리를 계산할 수 있다.

#include "books.h" #include <bits/stdc++.h> using namespace std; #define MAXN 1000006 #define sz(v) ((int)(v).size()) typedef long long lld; int N, S, M; int P[MAXN]; bool vis[MAXN]; struct Z{ int s, e; } A[MAXN]; lld minimum_walk(vector<int> p, int s) { N = sz(p); S = ++s; for (int i=1;i<=N;i++) P[i] = p[i-1]+1; lld total = 0; for (int i=1;i<=N;i++) total += abs(i-P[i]); int last_s = 0, last_e = 0; for (int i=1;i<=N;i++) if (!vis[i] && P[i] != i){ int e = i; for (int t=i;!vis[t];t=P[t]){ vis[t] = 1; e = max(e, t); } if (last_e && last_e < i){ A[++M] = {last_s, last_e}; last_e = 0; } if (!last_e) last_s = i; last_e = max(last_e, e); } if (last_e) A[++M] = {last_s, last_e}; if (S == 1){ lld ret = total; A[0].e = 1; for (int i=1;i<=M;i++) ret += (A[i].s-A[i-1].e)*2; return ret; } return 0; }

2) 전체 풀이 (100점)

우선, 위 그림처럼 싸이클 덩어리를 나누는 것은 union-find와 stack을 이용하여, $O(N \lg N)$ 시간에 해결할 수 있다. 그리고 S = 0인 경우 풀이에서 루트 싸이클 덩어리들 사이를 이동하는 추가 이동도 불가피하다는 것을 알 수 있다. 이 문제가 까다로운 이유는 시작점이 싸이클 덩어리 깊숙히 있는 경우, 루트 싸이클 덩어리까지 최단 거리로 이동해서 나오는 경우를 계산해주어야하기 때문이다.

그래서 싸이클 덩어리 마다 자신의 루트 싸이클 덩어리까지 가는 최단 추가 이동거리를 계산해야한다. 왼쪽에서 오른쪽으로 순회하는 것 한 번, 오른쪽에서 왼쪽으로 순회하는 것 한 번, 총 두 번의 선형 탐색을 통해 각 싸이클 덩어리마다 자신의 부모 싸이클 덩어리로 이동하는 최단거리가 나오게되고 이를 이용하여 루트 싸이클 덩어리까지 올라가는 최단거리를 구할 수 있다. 최단거리를 구하는 시간복잡도는 $O(N)$이다.

최단거리를 구하고나서는 시작점에서 i번 점까지 이동하고 i번 점에서 i번 점의 루트 싸이클 덩어리까지 올라가는 최단거리를 알고 있으므로 이를 이용하여 필요한 최소 추가 이동거리를 구할 수 있다.

총 시간복잡도는 $O(N \lg N)$이지만 이는 union-find에 의한 $O(\lg N)$이므로 전체 실행시간은 매우 빠르게 나온다.

#include "books.h" #include <bits/stdc++.h> using namespace std; #define MAXN 1000006 #define sz(v) ((int)(v).size()) typedef long long lld; int N, S; int P[MAXN]; int C; int par[MAXN], num[MAXN]; int L[MAXN], R[MAXN], U[MAXN]; int DL[MAXN], DR[MAXN], D[MAXN]; int rec[MAXN]; int find(int n){ return par[n] == n ? n : (par[n] = find(par[n])); } lld minimum_walk(vector<int> p, int s) { N = sz(p); S = ++s; for (int i=1;i<=N;i++) P[i] = p[i-1]+1; lld ret = 0; for (int i=1;i<=N;i++) ret += abs(i-P[i]); if (!ret) return 0; for (int i=1;i<=N;i++) if (!num[i] && P[i] != i){ L[++C] = i; for (int t=i;!num[t];t=P[t]){ num[t] = C; R[C] = max(R[C], t); } } for (int i=1;i<=C;i++) par[i] = i; stack <int> stk; for (int i=1;i<=N;i++) if (num[i]){ if (L[num[i]] == i) stk.push(num[i]); else{ int c = find(num[i]); while (L[stk.top()] > L[c]){ int t = stk.top(); stk.pop(); par[t] = c; R[c] = max(R[c], R[t]); } if (R[c] == i){ stk.pop(); if (!stk.empty()) U[c] = stk.top(); } } } for (int i=1;i<=C;i++) U[i] = find(U[i]); int last = 0; for (int i=1;i<=C;i++) if (find(i) == i){ if (last && R[last] > R[i]) continue; if (last) ret += (L[i]-R[last])*2; last = i; } bool in = 0; int l = N, r = 0; for (int i=1;i<=C;i++) if (find(i) == i){ if (L[i] < S && S < R[i]) in = 1; l = min(l, L[i]); r = max(r, R[i]); } if (!in && l <= S && S <= r) return ret; for (int i=1;i<=N;i++) if (num[i]){ int c = find(num[i]); rec[c] = i; if (U[c] && L[c] == i) DL[c] = i-rec[U[c]]; if (R[c] == i) rec[U[c]] = max(rec[U[c]], i-DL[c]); } for (int i=N;i;i--) if (num[i]){ int c = find(num[i]); rec[c] = i; if (U[c] && R[c] == i) DR[c] = rec[U[c]]-i; if (L[c] == i) rec[U[c]] = min(rec[U[c]], i+DR[c]); } for (int i=1;i<=C;i++) D[i] = min(DL[i], DR[i]); for (int i=1;i<=C;i++) if (U[i]) D[i] += D[U[i]]; int mn = N; for (int i=1;i<=N;i++) if (num[i]){ int c = find(num[i]); mn = min(mn, D[c] + abs(S-i)); } return ret + mn*2; }