POI 18회 스테이지3 문제2. Monotonicity 2

문제 설명

https://www.acmicpc.net/problem/8195

풀이

* 아래 풀이는 POI 공식 사이트에서 볼 수 있는 풀이(폴란드어로 쓰여 있음)를 참조했습니다. (https://oi.edu.pl/)

 

1. 개요

우리가 해결할 문제는, 주어진 수열 \(a_1, a_2, \dots, a_n\)의 부분수열 \(a_{b_1}, a_{b_2}, \dots, a_{b_k}\) 중, 모든 \(1 \le i \le n-1\)에 대해 \(i\)번째 항과 \(i+1\)번째 항 사이에 \(a_{b_i} \,\langle s_i \rangle\, a_{b_{i+1}}\)이 성립하는 것 중 가장 긴 것을 찾는 것이다.

• 여기서 \(\langle s_i \rangle \)는 부등호 또는 등호인 \(s_i\)를 \(a_{b_i}\)와 \(a_{b_{i+1}}\)의 대소비교에 이용함을 나타낸다.
• 여기서 \(s_i\)는 \(s_1, \dots, s_K, s_1, \dots, s_K, \dots\)와 같이 주어진 monotonicity scheme을 반복해서 나열한 것에서 \(i\)번째를 말한다. 즉, \(i\)를 그냥 사용하지 않고 \(\left\lbrack(i-1) \text{ mod } K\right\rbrack + 1\)로 취한다.

가장 긴 것은 반드시 어떤 끝점을 가져야 한다. 따라서, 위치 \(x \in \lbrace 1,2,\dots, n\rbrace \)에서 끝나면서 monotonicity scheme을 만족하는 \(\lbrace a_i \rbrace^n_{i=1} \)의 부분수열(이하 M부분수열) 중 가장 긴 것의 길이를 \(f(x)\)라고 정의하자. 그러면, 구하는 부분수열의 길이는

$$ \max_{1\le x\le n} f(x) $$

이다.

 

2. 부분구조

위치 \(x\)에서 끝나는 M부분수열 중 가장 긴 것을 '위치 \(x\)에서의 최적M부분수열'라고 하자. (위치 \(x\)에서의 최적M부분수열은 여러 개가 있을 수 있다. 하지만 길이는 같고, 그러므로 그 직후에 와야 하는 monotonicity scheme도 서로 같다.) 그러면 다음 정리가 성립한다.

 

정리 1. 임의의 위치 \(x\)에서의 최적M부분수열 중, 어떤 위치 \(y \,\,(<x)\)에서의 최적M부분수열에 \(a_x\)를 덧붙인 꼴을 하는 것이 항상 존재한다.

 

증명) 수학적 귀납법을 이용하자. 우선, \(x = 1\)에서는 monotonicity scheme과 상관없이 \(f(x) = 1\)이며, 항을 하나 제거한 수열은 빈 수열이므로 monotonicity scheme을 vacuous하게 만족시킨다.

이제 \(x \ge 2\)에 대하여 수학적 귀납법을 적용하여 \(1, 2, \dots, x-1\)에서 정리가 성립한다고 가정하자. \(f(x) = k\)라고 할 때, \(x\)에서 끝나는 어떤 최적M부분수열 \(a_{i_1}, a_{i_2}, \dots, a_{i_{k-1}}, a_{i_k}\) \((i_1 < i_2 < \dots < i_{k-1} < i_k = x)\)가 있다면, 이를 변형시켜 문제의 조건을 만족하는 다른 최적M부분수열을 항상 찾을 수 있음을 보일 것이다.

 

우선, 위에서 존재를 가정한 수열에 의해 \(i_{k-1}\)에서 끝나는 길이 \(k-1\)의 M부분수열이 존재하므로 \(f(i_{k-1}) \ge k-1 \)이다. 따라서 경우를 다음 두 가지로 나누어 생각할 수 있다.

 

Case 1. \(f(i_{k-1}) = k-1\). 이 경우 부분수열 \(a_{i_1}, a_{i_2}, \dots, a_{i_{k-1}}, a_{i_k}\)이 정리의 조건을 만족한다.

Case 2. \(f(i_{k-1}) > k-1\). 이 경우 \(m = i_{k-1}\)이라 하고, \(m\)에서 끝나는 최적M부분수열

$$ a_{b_1}, a_{b_2}, \dots, a_{b_{f(m)}} $$

을 생각하자(\(b_{f(m)} = m\)). 이때, \(m < x\)이므로 귀납가정에 의해 위 수열의 모든 prefix 수열은 그 끝 위치에서의 최적M부분수열이 되도록 잡을 수 있다. 즉, \(f(b_i) = i\). 또한, 가정에 의해 위 수열의 길이는 \(k-1\)보다 크다. 다시 경우를 나누어 생각하자.

 

Case 2a. \(a_m = a_x\). 이 경우 위 수열에서 마지막 항을 \(a_x\)로 대치한 수열 \(S\)를 생각하자. \(S\)는 마지막 항과 마지막에서 두 번째 항 사이에 monotonicity scheme이 동일하게 성립하므로 정당한 M부분수열이다. 그리고 \(S\)의 길이는 \(f(m) \ge k\)인데, \(f(x) = k\)이므로 길이는 정확히 \(k\)이어야 한다. 따라서 \(S\)는 위치 \(x\)에서의 최적M부분수열이다. 한편 \(S\)는 위치 \({b_{f(m)-1}}\)에서의 한 최적M부분수열에 \(a_x\)를 덧붙인 것이므로, 정리의 조건을 만족한다.

 

노트 1. Case 2a로부터 얻을 수 있는 교훈은 \(a_{b_1}, a_{b_2}, \dots, a_{b_{f(m)}}\)의 prefix를 가져와 \(a_x\)를 덧붙인 수열이 monotonicity scheme을 만족하며 길이가 \(k\)라면 정리의 조건을 만족한다는 사실이다. 이 점을 염두에 두고 나머지 케이스를 보자.

 

Case 2b. \(a_m < a_x\). 이 경우 \(a_{i_1}, a_{i_2}, \dots, a_{i_{k-1}}, a_{i_k}\)을 고려하면 \(s_{k-1} = \)'<'이다. 다시 경우를 나누어 보면,

 

(i) \(a_{b_{k-1}} < a_x\). 이 경우 \(a_{b_1}, a_{b_2}, \dots, a_{b_{k-1}}, a_x\)를 고려하면, \(s_{k-1} = \)'<'에서 마지막 두 항 간의 monotonicity scheme이 성립하며, 나머지는 \(a_{b_i}\)에서 가져왔으므로 monotonicity scheme이 성립한다. 노트 1에 의해 정리의 조건도 만족한다.

 

(ii) \(a_{b_{k-1}} \ge a_x\). 이 경우 \(s_{k-1} = \)'<'에서 \(a_{b_{k-1}} < a_{b_k}\)이므로 \(a_{b_k} > a_x\)이다. 그런데 \(a_{b_k}\)에서 출발하여 \(a_m\)에 도달하기까지 과정을 고려해보면, \(a_{b_k} > a_m\)이므로 반드시 감소('>')하는 인접항이 존재해야 한다. 그 첫 위치를 \(b_w\)라고 하자. 즉, \(a_{b_k} \le \dots \le a_{b_w} > {a_{b_{w+1}}} \dots a_m\). 그러면 \(a_{b_w} \ge a_{b_k} > a_x\)이므로 다음 수열

$$ a_{b_1}, a_{b_2}, \dots, a_{b_k}, \dots, a_{b_w}, a_x $$

은 monotonicity scheme을 만족한다. 그런데 \(w \ge k\)이므로 전체 수열의 길이는 \(k+1\) 이상이 되며, 이는 \(f(x) = k\)임에 모순이다. 즉, 처음에 최적해를 가정했으므로 이 경우가 나타날 수 없다.

 

Case 2c. \(a_m > a_x\). Case 2b와 대칭적이다.

 

즉, 새로운 수 \(a_x\)가 나올 때마다 기존 최적M부분수열의 끝에 덧붙이는 방법들만 모두 시도해보아도 \(a_x\)에서 끝나는 최적M부분수열의 길이를 구할 수 있다. 따라서 다른 M부분수열에 덧붙이는 방법은 굳이 시도할 필요가 없음으로 인해 시간복잡도가 대폭 줄어들게 된다.

3. 구현

정리 1에 의해 \(f(x)\)를 구하기 위해서는 \(1, 2, \dots, x-1\)의 최적M부분수열의 길이만 고려하면 된다. 즉,

$$ f(x) = 1 + \max_{1 \le y < x \text{ and } a_y \, \langle s_{f(y)}\rangle\, a_x} f(y)\,\,\,\, (x \ge 2). $$

단, 조건을 만족하는 \(y\)가 없을 경우 \(f(x) = 1\)로 한다. \(x = 1\)인 경우 역시 \(f(x) = 1\)이다.

 

첫 번째 조건(\(1 \le y < x\))은 \(x\)를 증가하는 순으로 보면서 자료구조에 \(f(x)\)를 추가하는 방식으로 하면 대응 가능하다. 두 번째 조건(\(a_y \, \langle s_{f(y)}\rangle\, a_x\))은 세그먼트 트리를 만들고 좌표는 \(a_x\)값으로, 값은 \(a_x\)값이 같은 것 중 \(f(x)\)의 최댓값으로 저장하면 point update, range query로 해결할 수 있다. 단, 다음 것보다 작은 것, 다음 것과 같은 것, 다음 것보다 큰 것에 대한 세그먼트 트리를 모두 따로 두어야 한다. (또는, 한 세그먼트 트리 내에서 3가지를 별도로 관리)

 

이제 \(x\)를 \(1\)부터 \(n\)까지 돌았다면, \(f(x)\)가 최대가 되는 \(x\)를 찾는다. 이때 원 수열을 구하려면 백트래킹을 해야 한다. 따라서, \(f(x)\)를 구할 때 \(f(x)\)의 최댓값을 주었던 이전 위치 \(y\)를 저장해두었어야 한다.

 

전체 시간복잡도는 \(O(n \lg n)\).