BOJ 19933 Comparing Plants
sorohue가 PS하는 블로그
문제 링크입니다. IOI 2020 기출문제입니다. 그것도 국산인.
문제 요약
높이가 서로 다른 식물 $N$개를 원형으로 배치합니다. 각 식물마다 오른쪽으로 $K-1$개의 식물 중 자신보다 높은 식물이 몇 개인지를 알 수 있습니다. $i$번째 식물에 대한 이 값을 $r[i]$로 표현합니다.
두 식물의 번호가 주어졌을 때, 두 식물의 높이를 비교하는 함수를 구현해야 합니다. 이때 주어진 정보만으로 높이를 비교할 수 없는 경우까지 고려해야 합니다.
서브태스크 1 - $K = 2$
각 식물과 인접한 식물 사이의 대소 관계를 알 수 있습니다.
식물들 사이에 주어진 $r[i]$의 값을 토대로 부등호를 그려줍시다. 그 부등호를 따라 화살표를 그렸다고 생각합시다. 우리는 한 방향으로만 화살표를 타고 가면서 대소관계를 이어야 합니다. 역방향의 화살표를 지나게 되면 기존까지 가지고 있던 대소관계의 연쇄는 모두 뭉개지고, 새로운 방향으로의 대소관계만이 연쇄됩니다.
그러니 각 방향으로 화살표를 타고 갈 수 있는 맨 끝 위치를 전처리해 두면 각 요청을 $\mathcal{O}(1)$에 처리할 수 있습니다.
- 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#include "plants.h" #include<bits/stdc++.h> using namespace std; vector<int> L, R; int n; void init(int k, vector<int> r){ n = r.size(); L.resize(2*n+1); R.resize(2*n+1); for(int i = 0; i < 2*n; i++) L[i] = R[i] = i; for(int i = 0; i < 2*n; i++){ if(r[i%n]) R[i+1] = R[i]; else L[i+1] = L[i]; } } int compare_plants(int x, int y){ if(L[x] == L[y] || R[x+n] == R[y]) return 1; if(R[x] == R[y] || L[x+n] == L[y]) return -1; return 0; }
서브태스크 2 - $N \le 5000,\ 2K > N$
각 식물에 대한 구간이 전체 구간의 절반을 초과합니다.
$r[i]$의 값이 0인 경우, 자신의 오른쪽 $K-1$개 식물 중 자신보다 높은 게 없다는 뜻이 됩니다. 어떤 식물이 가장 높은 식물이려면, 자신의 $r[i]$ 값이 0이어야 하고, 자신을 구간에 포함하고 $r[i]$가 0인 식물이 없어야 합니다.
어쨌든 가장 높은 식물이 존재하니 $r[i]$가 0인 식물이 적어도 하나 존재합니다. 그중 다른 $r[i]$가 0인 식물의 구간에 들어가지 않는 식물이 둘 이상이라고 해 봅시다. 그러면 조건의 $2K > N$에 의해 둘 중 한 식물이 다른 식물의 구간에 들어가게 되어 모순입니다. 따라서 우리는 가장 높은 식물을 유일하게 결정할 수 있습니다.
편의상 식물의 높이를 1부터 $N$까지의 서로 다른 정수라고 합시다. 우리가 찾은 식물은 높이가 $N$이 되겠네요. 이 식물 자리에 높이가 0인 식물이 들어왔다 치고 다른 식물의 $r[i]$ 값을 업데이트하고 나면, 이제 두 번째로 높은 식물의 위치를 알아낼 수 있을 겁니다.
같은 작업을 반복해서 $\mathcal{O}(N^2)$에 모든 식물의 실제 높이를 알아낼 수 있습니다. 그 뒤에는 각 요청을 $\mathcal{O}(1)$에 처리해 주면 됩니다.
서브태스크 3 - $N \le 200\ 000,\ 2K > N$
$N$의 제한이 큽니다. 가장 큰 식물을 찾고 다른 식물의 $r[i]$ 값을 업데이트하는 과정을 최적화합시다. 느리게 갱신되는 세그먼트 트리를 이용해 $r[i]$의 구간 최솟값을 찾고 구간에 특정 값을 더하는 업데이트를 처리해 주면 $\mathcal{O}(N \log N)$에 문제를 해결할 수 있습니다.
$N-1$과 $0$에 걸치는 구간은 적당히 둘로 나눠서 처리해 줍시다.
- 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
#include "plants.h" #include<bits/stdc++.h> #define mid (l+r>>1) using namespace std; int lazy[1208080], a[202020]; pair<int, int> tree[1208080]; int len, n; void prop(int now, int l, int r){ if(l != r){ lazy[now<<1] += lazy[now]; lazy[now<<1|1] += lazy[now]; } tree[now].first += lazy[now]; lazy[now] = 0; } void upd(int now, int l, int r, int L, int R, int v){ prop(now, l, r); if(L > r || l > R) return; if(L <= l && r <= R){ lazy[now] += v; if(L == R) tree[now].second = l; prop(now, l, r); return; } upd(now<<1, l, mid, L, R, v); upd(now<<1|1, mid+1, r, L, R, v); tree[now] = min(tree[now<<1], tree[now<<1|1]); } pair<int, int> qry(int now, int l, int r, int L, int R){ prop(now, l, r); if(L > r || l > R) return {n+1, n}; if(L <= l && r <= R) return tree[now]; auto lq = qry(now<<1, l, mid, L, R); auto rq = qry(now<<1|1, mid+1, r, L, R); return min(lq, rq); } void init(int k, vector<int> r){ len = k; n = r.size(); for(int i = 0; i < n; i++) upd(1, 0, n-1, i, i, r[i]); for(int i = n; i >= 1; i--){ auto [c, now] = qry(1, 0, n-1, 0, n-1); bool changed = 0; if(now-k+1 < 0){ auto [nc, nnow] = qry(1, 0, n-1, now-k+1+n, n-1); if(nc == 0) c = nc, now = nnow; } if(!changed && now > 0){ auto [nc, nnow] = qry(1, 0, n-1, max(0, now-k+1), now-1); if(nc == 0) c = nc, now = nnow; } a[now] = i; upd(1, 0, n-1, now, now, 6*n); if(now > 0) upd(1, 0, n-1, max(0, now-k+1), now-1, -1); if(now-k+1 < 0) upd(1, 0, n-1, now-k+1+n, n-1, -1); } } int compare_plants(int x, int y){ if(a[x] > a[y]) return 1; if(a[x] < a[y]) return -1; return 0; }
서브태스크 5 - $N \le 300$
어떻게든 모든 두 식물의 쌍에 대한 대소 관계 비교 결과를 전처리해 두면, 각 요청을 $\mathcal{O}(1)$에 처리할 수 있습니다.
서브태스크 1에서 그렸던 부등호 화살표를 가져옵시다. 이번에는 인접한 것끼리만 그리는 게 아니라, 가장 큰 것부터 순서대로 자신이 포함하거나 자신을 포함하는 자기보다 작은 모든 식물들에 화살표를 날려줍니다. 적당히 나이브하게 구현해도 괜찮습니다.
우리는 화살표를 따라서 한 식물에서 다른 식물로 이동할 수 있습니다. 이제 $\mathcal{O}(N^3)$에 플로이드-워셜을 돌려 모든 대소 관계 비교의 결과를 만들어낼 수 있습니다.
- 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
#include "plants.h" #include<bits/stdc++.h> #define mid (l+r>>1) using namespace std; int n; bool e[333][333]; void init(int k, vector<int> r){ n = r.size(); for(int i = 0; i < n; i++){ int now = i%n; if(r[now]) continue; bool go = 1; for(int j = 1; j < k; j++){ int pre = (now-j+n)%n; if(!r[pre]){ go = 0; i = pre-1; break; } } if(go){ for(int j = 1; j < k; j++){ int nxt = (now+j)%n; if(r[nxt] < 0) continue; e[now][nxt] = 1; } for(int j = 1; j < k; j++){ int pre = (now-j+n)%n; if(r[pre] < 0) continue; e[now][pre] = 1; if(r[pre]) r[pre]--; } r[now] = -1; i = -1; } } for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) e[i][j] |= e[i][k]&e[k][j]; } int compare_plants(int x, int y){ if(e[x][y]) return 1; if(e[y][x]) return -1; return 0; }
만점 풀이
서브태스크 5에서의 화살표를 단방향 간선이라는 더 있어 보이는 이름으로 불러볼 수 있습니다. 작은 식물에서 큰 식물로 역행할 수는 없으니 이 식물과 화살표는 DAG를 이룹니다.
DAG랑 세트로 딸려오는 위상 정렬을 생각해 봅시다. 우리는 위상 정렬 상 더 뒤에 있는 것이 앞에 있는 것보다 크다고는 할 수 없습니다. 뭐… 실제로 위상 정렬을 할 건 아니고, 대신 레벨의 개념을 도입할 겁니다. 우리는 가장 클 것 같은 식물들부터 순서대로 보면서 화살표를 추가합니다. 이때, 이미 자신한테 꽂힌 화살표 중 레벨이 가장 높은 식물보다 1 높도록 이번 식물의 레벨을 설정해 줍니다. 그러면 간선을 타고 이동할 때 자기보다 레벨이 낮거나 같은 식물로는 이동할 수 없습니다. 레벨이 같은 식물로 이동할 수 있으면 그쪽의 레벨이 더 높게 설정되어야 합니다.
우리는 모든 화살표를 만들어 둘 수 없습니다. 대신, 식물마다 화살표가 꽂히는 구간이 연속적임을 이용합시다. 각 식물에서 레벨을 최대한 낮게 유지하면서 최대한 멀리 갈 수 있는 화살표를 찾습니다. 그러면, 원래의 식물과 각 화살표가 향하는 식물 사이의 원래의 식물보다 레벨이 높은 식물로는 자연히 갈 수 있는 상태임을 알 수 있게 됩니다.
이를 여러 번 반복하면 궁극적으로 어느 정점까지 어느 레벨을 거치면서 갈 수 있는지를 전처리해둘 수 있습니다. 희소 배열을 활용하면 시간과 메모리를 획기적으로 절약할 수 있겠네요. 구현 상의 편의를 위해 원형 배열을 그대로 뒤에 하나 이어붙여 길이 $2N$의 직선으로 보는 테크닉을 이용할 수 있습니다.
기본적인 구현은 서브태스크 3의 느리게 갱신되는 세그먼트 트리를 사용합니다. 거기에 레벨과 왼쪽 끝, 오른쪽 끝을 구할 때 사용하기 위한 세그먼트 트리를 3개 추가하고, $r[i]$ 값이 0인 것 중 다른 구간에 들어가지 않는 것을 빠르게 찾기 위해 std::set과 같이 정렬성을 유지하는 자료 구조를 사용합니다.
코드
구현 디테일이 꽤 중요합니다. 아마 실제로 필요없는 정보를 관리하고 있을 거 같은데 무서워서 건드릴 수가 없네요ㅋㅋ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include "plants.h"
#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
int lazy[1208080], a[202020];
pair<int, int> tree[1208080];
int atree[604040];
int L[20][404040], R[20][404040], La[20][404040], Ra[20][404040];
pair<int, int> lt[1212121], rt[1212121];
int len; int n;
vector<int> lvl[808080];
void lrupd(int now, int l, int r, int i, int v){
if(i < l || r < i) return;
if(l == r){
lt[now] = rt[now] = {v, i};
return;
}
lrupd(now<<1, l, mid, i, v);
lrupd(now<<1|1, mid+1, r, i, v);
if(lt[now<<1].first == 0) lt[now] = lt[now<<1|1];
else if(lt[now<<1|1].first == 0) lt[now] = lt[now<<1];
else lt[now] = min(lt[now<<1], lt[now<<1|1]);
if(rt[now<<1].first == 0) rt[now] = rt[now<<1|1];
else if(rt[now<<1|1].first == 0) rt[now] = rt[now<<1];
else if(rt[now<<1].first != rt[now<<1|1].first) rt[now] = min(rt[now<<1], rt[now<<1|1]);
else rt[now] = max(rt[now<<1], rt[now<<1|1]);
}
pair<int, int> lqry(int now, int l, int r, int L, int R){
if(l > R || L > r) return {0, 2*n+1};
if(L <= l && r <= R) return lt[now];
auto lq = lqry(now<<1, l, mid, L, R);
auto rq = lqry(now<<1|1, mid+1, r, L, R);
if(lq.first == 0) return rq;
else if(rq.first == 0) return lq;
else return min(lq, rq);
}
pair<int, int> rqry(int now, int l, int r, int L, int R){
if(l > R || L > r) return {0, 2*n+1};
if(L <= l && r <= R) return rt[now];
auto lq = rqry(now<<1, l, mid, L, R);
auto rq = rqry(now<<1|1, mid+1, r, L, R);
if(lq.first == 0) return rq;
else if(rq.first == 0) return lq;
else if(lq.first != rq.first) return min(lq, rq);
else return max(lq, rq);
}
void aupd(int now, int l, int r, int i, int v){
if(i < l || r < i) return;
if(l == r){
atree[now] = a[l] = v;
return;
}
aupd(now<<1, l, mid, i, v);
aupd(now<<1|1, mid+1, r, i, v);
atree[now] = max(atree[now<<1], atree[now<<1|1]);
}
int aqry(int now, int l, int r, int L, int R){
if(l > R || L > r) return 0;
if(L <= l && r <= R) return atree[now];
return max(aqry(now<<1, l, mid, L, R), aqry(now<<1|1, mid+1, r, L, R));
}
void prop(int now, int l, int r){
if(l != r){
lazy[now<<1] += lazy[now];
lazy[now<<1|1] += lazy[now];
}
tree[now].first += lazy[now];
lazy[now] = 0;
}
void upd(int now, int l, int r, int L, int R, int v){
prop(now, l, r);
if(L > r || l > R) return;
if(L <= l && r <= R){
lazy[now] += v;
if(L == R) tree[now].second = l;
prop(now, l, r); return;
}
upd(now<<1, l, mid, L, R, v);
upd(now<<1|1, mid+1, r, L, R, v);
tree[now] = min(tree[now<<1], tree[now<<1|1]);
}
pair<int, int> qry(int now, int l, int r, int L, int R){
prop(now, l, r);
if(L > r || l > R) return {n+1, n};
if(L <= l && r <= R) return tree[now];
auto lq = qry(now<<1, l, mid, L, R);
auto rq = qry(now<<1|1, mid+1, r, L, R);
return min(lq, rq);
}
void init(int k, vector<int> r){
len = k; n = r.size();
for(int i = 0; i < n; i++) upd(1, 0, n-1, i, i, r[i]);
set<int> cand;
for(int i = n; i >= 1; i--){
int now;
if(cand.empty()){
now = qry(1, 0, n-1, 0, n-1).second;
cand.insert(now);
upd(1, 0, n-1, now, now, 6*n);
}
now = *cand.begin();
now %= n; now += 2*n; now %= n;
while(1){
bool changed = 0;
if(now-k+1 < 0){
auto [nc, nnow] = qry(1, 0, n-1, now-k+1+n, n-1);
if(nc == 0){
changed = 1;
cand.insert(nnow-n*((nnow-*cand.begin())/n+1));
upd(1, 0, n-1, nnow, nnow, 6*n);
now = nnow;
}
}
if(!changed && now > 0){
auto [nc, nnow] = qry(1, 0, n-1, max(0, now-k+1), now-1);
if(nc == 0){
changed = 1;
cand.insert(nnow-n*((nnow-*cand.begin())/n+1));
upd(1, 0, n-1, nnow, nnow, 6*n);
now = nnow;
}
}
if(!changed) break;
}
cand.erase(*cand.begin());
int A = 0;
if(now > 0){
upd(1, 0, n-1, max(0, now-k+1), now-1, -1);
A = max(A, aqry(1, 0, n-1, max(0, now-k+1), now-1));
}
if(now-k+1 < 0){
upd(1, 0, n-1, now-k+1+n, n-1, -1);
A = max(A, aqry(1, 0, n-1, now-k+1+n, n-1));
}
if(now < n-1){
A = max(A, aqry(1, 0, n-1, now+1, min(n-1, now+k-1)));
}
if(now+k-1 >= n){
A = max(A, aqry(1, 0, n-1, 0, now+k-1+n));
}
aupd(1, 0, n-1, now, A+1);
lvl[A+1].push_back(now);
}
for(int tmp = n; tmp; tmp--){
for(auto now : lvl[tmp]){
auto [la, lidx] = lqry(1, 0, 2*n-1, now+n-k+1, now+n-1);
auto [ra, ridx] = rqry(1, 0, 2*n-1, now+1, now+k-1);
if(!la){
L[0][now] = now;
L[0][now+n] = now+n;
La[0][now] = La[0][now+n] = a[now];
}
else{
L[0][now+n] = lidx;
L[0][now] = max(0, lidx-n);
La[0][now] = La[0][now+n] = a[lidx%n];
}
if(!ra){
R[0][now] = now;
R[0][now+n] = now+n;
Ra[0][now] = Ra[0][now+n] = a[now];
}
else{
R[0][now] = ridx;
R[0][now+n] = min(2*n-1, ridx+n);
Ra[0][now] = Ra[0][now+n] = a[ridx%n];
}
}
for(auto now : lvl[tmp]){
lrupd(1, 0, 2*n-1, now, tmp);
lrupd(1, 0, 2*n-1, now+n, tmp);
}
}
for(int bit = 1; bit < 20; bit++) for(int i = 0; i < 2*n; i++){
L[bit][i] = L[bit-1][L[bit-1][i]];
R[bit][i] = R[bit-1][R[bit-1][i]];
La[bit][i] = La[bit-1][L[bit-1][i]];
Ra[bit][i] = Ra[bit-1][R[bit-1][i]];
}
}
int compare_plants(int x, int y){
int now = x, na = a[x];
for(int bit = 19; bit >= 0; bit--) if(R[bit][now] < y) na = Ra[bit][now], now = R[bit][now];
na = Ra[0][now%n]; now = R[0][now]; if(na <= a[y] && now >= y) return 1;
now = x+n, na = a[x];
for(int bit = 19; bit >= 0; bit--) if(L[bit][now] > y) na = La[bit][now], now = L[bit][now];
na = La[0][now%n+n]; now = L[0][now]; if(na <= a[y] && now <= y) return 1;
now = y, na = a[y];
for(int bit = 19; bit >= 0; bit--) if(R[bit][now] < x+n) na = Ra[bit][now], now = R[bit][now];
na = Ra[0][now%n]; now = R[0][now]; if(na <= a[x] && now >= x+n) return -1;
now = y, na = a[y];
for(int bit = 19; bit >= 0; bit--) if(L[bit][now] > x) na = La[bit][now], now = L[bit][now];
na = La[0][now%n+n]; now = L[0][now]; if(na <= a[x] && now <= x) return -1;
return 0;
}