IOI2020 Day1 plants 풀이

문제 및 채점: oj.uz

 

서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다.

 

풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시로 들어 설명하겠다.

 

이 때, 최대 크기를 가질 수 있는 식물을 찾을 건데, $i$ 번 식물이 아래 두 조건을 만족하면 최대 크기를 가질 수 있다:

　1) $R[i] = 0$: 시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$ 번 식물보다 큰 식물이 없음

　2) $R[j] = 0$ ($j$는 $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 식물 번호): 반시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$번 식물보다 큰 식물이 없음

 

$2K > N$인 경우(서브태스크 2, 3), 위 조건을 만족하는 $i$는 유일하며 전체 중 가장 큰 크기를 가지는 식물이다.

 

예시에서 두 조건을 만족하는 $i$는 5로 유일하다. 예를 들어, 6의 경우 $R[6] = 0$으로 1)번 조건을 만족하지만, $R[5] = 0$이기 때문에 2)번 조건을 만족하지 못한다.

 

만약 조건을 만족하는 $i$가 여러 개인 경우 그중 아무거나 하나를 찾고, $i$번 식물의 크기가 가장 크다고 가정한다. 그리고 $R[i]$의 값을 없애고, $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 $R$ 배열 값을 1 감소시킨다.

 

그러면 $R[3]$의 값이 1 감소하여 0이 되었고, $R[4]$의 값이 1 감소하여 1이 되었다. 그리고 위의 과정을 반복한다.

 

지금 상황에서 두 조건을 만족하는 $i$는 3과 7로 유일하지 않다. 즉, 3번 식물과 7번 식물의 크기 비교가 불가능한 상황임을 알 수 있다. 앞서 말했던 것처럼, $i$가 여러 개인 경우 그중 아무거나 하나를 찾자. 편의상 번호가 제일 작은 3번 식물로 과정을 진행하겠다.

 

이 방법으로 가능한 여러 식물들의 크기 구성 중 하나를 배열 $H$에 기록했다.

 

서브태스크 2 (14 점)

$N \leq 5000, 2K > N$. 위의 방법을 naive하게 구현하면 시간복잡도는 $O(NK)$가 되며, $2K > N$을 만족하는 경우 매 순간 최대 크기를 가지는 식물 후보 $i$가 유일하므로, 가능한 식물 크기 구성이 유일하다. 따라서 구한 배열 $H$로 모든 질문을 해결할 수 있다.

 

서브태스크 3, 4 (13, 17 점)

위의 방법을 lazy propagation을 이용한 segment tree와, 집합에서 lower bound와 left, right iteration이 가능한 set 같은 자료구조를 사용하면 $O(N \lg N)$ 시간에 해결할 수 있다. 배열 $H$의 내용만 가지고는 크기를 비교할 수 없는 식물 쌍을 확인할 수 없다. 서브태스크 3, 4는 식물 크기를 비교할 수 없는 쌍에 대한 고려를 하지 않아도 해결할 수 있다.

 

다음 서브태스크들을 풀기 위해 필요한 관찰

식물 $i$에 대해 시계방향과 반시계방향으로 $K-1$ 이내에 있는 식물들은 배열 $H$에 있는 값의 대소 비교를 통해 식물 크기를 비교할 수 있다.

 

서브태스크 5 (11 점)

$N \leq 300$. 위의 사실을 이용하여, $a$ 번 식물과 $b$ 번 식물의 크기 비교를 할 수 있고, $a$ 번 식물의 크기가 $b$번 식물보다 큰 경우 정점 $a$에서 정점 $b$로 가는 방향성 간선을 만들어, 간선의 개수가 $O(NK)$가 되는 DAG(Directed Acyclic Graph)를 만들 수 있다. Bellman-Ford 알고리즘을 사용하여 모든 쌍 $(i, j)$에 대해 DAG에서 경로가 있는지 미리 계산할 수 있다. DAG에서 $i$에서 $j$로 가는 경로가 있으면 $i$ 번 식물의 크기가 $j$ 번 식물의 크기보다 큰 것이고, 반대로 $j$에서 $i$로 가는 경로가 있으면 $j$ 번 식물의 크기가 $i$ 번 식물의 크기보다 큰 것이다. 둘다 경로가 없으면 두 식물의 크기를 비교할 수 없음을 의미한다.

 

다음 서브태스크들을 풀기 위해 필요한 관찰

위는 설명을 위한 다른 예시다. $K = 3$이며, $R[i]$에 적힌 값들은 처음 들어온 배열 $R$의 값이고, $H[i]$에 적힌 값들은 앞에 설명한 방법으로 구한 배열 $H$의 값이다.

 

이 예시에서 3번 식물과 9번 식물의 크기를 비교할 수 있는데, 왜냐하면 3번 식물의 크기는 5번 식물의 크기보다 크고, 5번 식물의 크기는 7번 식물의 크기보다 크고, 7번 식물의 크기는 9번 식물의 크기보다 크기 때문이다. 반면, 3번 식물과 10번 식물은 크기 비교를 할 수 없다.

 

3번 식물을 기준으로 오른쪽(원형에서는 시계방향)으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 5번 식물이 나온다. 5번 식물을 기준으로 오른쪽으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 7번 식물이 나온다. 이때, 7번 식물은 자명히 3번 식물보다 크기가 작으며, 7번 식물은 9번 식물과 충분히 거리가 인접하므로 크기 비교를 할 수 있고, 9번 식물은 7번 식물보다 크기가 작다. 이처럼 모든 식물에 대해 오른쪽 방향으로 자기와 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾는다. 마찬가지로 왼쪽 방향에 대해서도 진행한다. 이 과정은 set을 이용하여 $O(N \lg N)$에 구현할 수 있다.

 

서브태스크 6 (15 점)

항상 1번 식물과 다른 식물 $j$를 비교하는 질문만 들어오는 서브태스크다. 1번 식물에 대해 오른쪽으로 갈 때 나타나는 식물들의 순서와, 왼쪽으로 갈 때 나타나는 식물들의 순서를 미리 구한다. 주어지는 $j$에 대해 $j$보다 왼쪽에 있으면서 1번 식물에서 오른쪽으로 갈 때 나타나는 식물들 중 가장 $j$와 가까운 식물의 번호를 이분탐색으로 구한다. 그리고 그 식물과 $j$번 식물의 크기를 비교하여 $j$번 식물의 크기가 더 작다면 1번 식물의 크기가 더 크다는 뜻이다. 마찬가지의 확인을 왼쪽 방향에 대해서도 해준다. 이는 주어지는 질문을 $O(\lg N)$에 해결한다.

 

서브태스크 7 (25 점)

마지막 서브태스크다. 서브태스크 6에서 1번 식물에 대해 한 방향에 대해 나타나는 식물 순서를 미리 구하고 이분탐색한 과정을 sparse table을 이용해 공간복잡도 $O(N \lg N)$에 질문마다 시간복잡도 $O(\lg N)$에 해결할 수 있다.

 

#include <bits/stdc++.h> #include "plants.h" using namespace std; #define MAXN 200005 #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr); typedef pair<int, int> pii; int N, K, R[MAXN]; int H[MAXN], nxt_r[MAXN][18], nxt_l[MAXN][18]; template <typename T> struct SegTree{ int n_bits, TS, ST; int range_l(int x){ return ((x<<(__builtin_clz(x)-31+n_bits)) ^ (1<<n_bits)) + 1; } int range_r(int x){ return ((x<<(__builtin_clz(x)-31+n_bits) ^ ((1<<(__builtin_clz(x)-31+n_bits))-1)) ^ (1<<n_bits)) + 1; } struct Value{ T value, lazysum; }; vector<Value> tree; SegTree(int arr[]){ n_bits = 32-__builtin_clz(N-1); TS = 1 << n_bits+1; ST = TS/2-1; tree.resize(TS, {0, 0}); for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9; for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value); } void propagate(int n){ if (n <= ST){ tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum; tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum; } tree[n].lazysum = 0; } void update(int n, int l, int r, const int &v){ int s = range_l(n), e = range_r(n); if (l > r || e < l || r < s) return; if (l <= s && e <= r){ tree[n].value += v, tree[n].lazysum += v; return; } propagate(n); update(n*2, l, r, v); update(n*2+1, l, r, v); tree[n].value = min(tree[n*2].value, tree[n*2+1].value); } int findzero(int n){ if (tree[n].value != 0) return 0; propagate(n); if (n > ST) return n-ST; if (!tree[n*2].value) return findzero(n*2); else if (!tree[n*2+1].value) return findzero(n*2+1); else assert(0); } }; struct ZeroContainer{ set<int> pos, non_covered; set<int>::iterator _left(set<int>::iterator it){ auto ret = it; if (ret == pos.begin()) ret = pos.end(); return --ret; } set<int>::iterator _right(set<int>::iterator it){ auto ret = it; ret++; if (ret == pos.end()) return pos.begin(); return ret; } void insert(int p){ auto it = pos.insert(p).first; auto l = _left(it), r = _right(it); if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p); if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r); } void remove(int p){ auto it = pos.find(p); auto l = _left(it), r = _right(it); if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r); pos.erase(it); } int pop_smallest(){ int ret = *non_covered.begin(); non_covered.erase(ret); remove(ret); return ret; } }; int go_left(int n, int d) { return (n - d%N - 1 + N)%N + 1; } int go_right(int n, int d) { return (n + d%N - 1 + N)%N + 1; } void init(int K, vector<int> r) { ::K = K; N = r.size(); for (int i=1;i<=N;i++) R[i] = r[i-1]; { SegTree<int> segtree(R); ZeroContainer zc; for (int ord=N;ord;ord--){ for (;;){ int p = segtree.findzero(1); if (!p) break; zc.insert(p); segtree.update(1, p, p, 1e9); } int x = zc.pop_smallest(); H[x] = ord; segtree.update(1, max(1, x-K+1), x-1, -1); if (x-K+1 < 1) segtree.update(1, N-(1-(x-K+1))+1, N, -1); } } { set <pii> s; for (int i=1;i<=K;i++) s.insert({H[i], i}); for (int i=1;i<=N;i++){ auto it = s.lower_bound({H[i], 0}); if (it != s.begin()){ it--; nxt_r[i][0] = (it->second - i + N) % N; } int t = (i+K-1)%N+1; s.insert({H[t], t}); s.erase({H[i], i}); } } { set <pii> s; for (int i=1;i<K;i++) s.insert({H[i], i}); for (int i=1;i<=N;i++){ int t = (i+K-2)%N+1; auto it = s.lower_bound({H[t], 0}); if (it != s.begin()){ it--; nxt_l[t][0] = (t - it->second + N) % N; } s.insert({H[t], t}); s.erase({H[i], i}); } } for (int i=0;i+1<18;i++) for (int j=1;j<=N;j++){ nxt_l[j][i+1] = min(N+10, nxt_l[go_left(j, nxt_l[j][i])][i] + nxt_l[j][i]); nxt_r[j][i+1] = min(N+10, nxt_r[go_right(j, nxt_r[j][i])][i] + nxt_r[j][i]); } } bool has_left_path(int a, int b) { int d = (a-b+N)%N; for (int i=18;i--;) if (d >= nxt_l[a][i]){ d -= nxt_l[a][i]; a = go_left(a, nxt_l[a][i]); } return (a-b+N)%N < K && H[a] >= H[b]; } bool has_right_path(int a, int b) { int d = (b-a+N)%N; for (int i=18;i--;) if (d >= nxt_r[a][i]){ d -= nxt_r[a][i]; a = go_right(a, nxt_r[a][i]); } return (b-a+N)%N < K && H[a] >= H[b]; } int compare_plants(int a, int b) { a++; b++; if (has_left_path(a, b) || has_right_path(a, b)) return 1; if (has_left_path(b, a) || has_right_path(b, a)) return -1; return 0; }