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)$.