BOJ20617 Longest Common Subsequence

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

 

요약: $1, 2, 3$으로 이루어진 길이 $n \leq 10^6$의 수열 $a$와 길이 $m \leq 10^6$의 수열 $b$ 의 Longest Common Increasing Subsequence (LCIS) 를 구하라.

 

편의상 $m = n$이라 하겠다.

 

만약 수열이 $1, 2$로만 이루어졌다면 어떨까? $SA_x(l, r)$을 $a$의 구간 $[l, r]$에서 $x$의 개수라 하자. $SB_x(l, r)$도 비슷하게 정의하자. $a$에선 구간 $[1, i_a]$에서 $1$만을, 구간 $[i_a + 1, n]$에서 $2$만을 선택하고, $b$에선 구간 $[1, i_b]$에서 $1$만을, 구간 $[i_b + 1, n]$에서 $2$만을 선택하는 모든 경우에 대해 답을 구해보자. 그럼 식은 다음과 같다.

$\max_{1 \leq i_a \leq n, 1 \leq i_b \leq n} \min \{ SA_1(1, i_a), SB_1(1, i_b) \} + \min \{ SA_1(i_a + 1, n), SB_1(i_b + 1, n) \}$. 하지만 이 식을 계산하는 데에는 $O(n^2)$이 걸린다. 

 

이때 어떤 LCIS에 대해, $1$들을 각 수열마다 앞에서부터 선택해줘도 된다는 점을 관찰하면, $a$와 $b$에서 같은 개수의 $1$을 선택한 경우에 대해서만 위 식을 계산해줘도 됨을 알 수 있다. 다음과 같은 집합 $id_x = \{ (i_a, i_b) | a_{i_a} = b_{i_b} = x, SA_x(1, i_a) = SB_x(1, i_b) \}$에 대해, $\max_{(i_a, i_b) \in id_1} SA_1(1, i_a) + \min \{ SA_1(i_a + 1, n), SB_1(i_b + 1, n) \}$ 은 $O(n)$에 계산해줄 수 있다.

 

이제 다시 원문제로 돌아와서, $1, 2, 3$으로 이루어진 수열에 대해 생각해보자. 비슷하게 각 수열마다 앞에서부터 차례대로 $1, 2, 3$을 고르고 $min$을 취해주는 식을 생각해볼 수 있지만, $O(n^2)$을 $O(n)$으로 줄인 관찰과 비슷하게 $1$을 앞에서부터 같은 개수로 선택해주고, $2$를 그 앞에서부터 다시 같은 개수로 취해주는 경우에 대해 생각해보면, 다음과 같은 식이 나온다. $\max_{(i_a, i_b) \in id_1} \{ SA_1(1, i_a) + \max_{(j_a, j_b) \in id_2, j_a > i_a, j_b > i_b} \{ SA_2(i_a + 1, j_a) + \min \{ SA_3(j_a + 1, n), SB_3(j_b + 1, n) \} \} \}$

 

이 식을 제곱 미만에 계산하려면 어떻게 해야할까? $SA_3(j_a + 1, n)$이 언제 $min$값이 되는지, 즉 각 $i$에 대해 $SA_3(i, n) \leq SB_3(j, n)$인 $j$들은 어떤 값들일지 생각해보자. $SB_3(j, n)$ 는 $j$가 증가함에 따라 값이 단조감소함을 생각해보면, 각 $i$에 대해 $j$는 $[1, r_i]$형태의 연속적인 구간 또는 공집합이 될 것이다. 그럼 다시 답을 구하는 식으로 돌아와서, $r_i$들을 전처리 하였다면 $j_b + 1 \leq r_{j_a}$인 $j_a$들에 대해 $max$ 쿼리를 날려주면 됨을 알 수 있다. 추가적으로 $j_a > i_a$도 만족해야 하기에, 2차원 쿼리가 될 것이고, 이는 스위핑과 세그먼트 트리를 사용하면 오프라인 쿼리로 처리해줄 수 있다. 비슷하게 $SB_3(j_b + 1, n)$이 언제 최솟값이 되는지에 대해 생각하며 이도 처리해주면 문제를 해결할 수 있다.

 

최종 시간복잡도는 $O(n \log n)$이 된다.