Splitting Parentheses

서브태스크 2: $K=1$

조각은 문자열 전체 하나뿐이다. $S$는 좋은 괄호 문자열이므로 가능한 ()를 모두 지우면 아무 문자도 남지 않는다. 따라서 $X=0$이고, $S$를 그대로 출력하면 된다.

서브태스크 1: 분할과 재배열을 모두 완전 탐색하기

$N\leq 10$이므로 $K-1$개의 절단 위치를 모두 고를 수 있다. 한 분할이 정해지면 $K!$개의 조각 순서를 모두 시도하고, 각 순서에서 인접한 ()를 스택으로 지워 점수를 계산한다. 각 분할에서 모그가 만들 수 있는 점수의 최댓값을 구하고, 그 값이 가장 작은 분할을 선택한다.

이 방법은 문제의 정의를 그대로 구현한 것이다. 다음 단계에서는 한 분할의 값을 조각 순열을 나열하지 않고 계산한다.

고정된 분할의 점수

문자열의 괄호 높이를 $H_0=0$으로 두고, $S_i=\texttt{(}$이면 $$, 이면 로 정의한다. 또한 라 하자. 은 로 이루어진 조각을 뜻한다.

조각 $S(l,r]$에서 가능한 ()를 모두 지우면 닫는 괄호 $H_l-m_{l,r}$개 뒤에 여는 괄호 개가 남는다. 따라서 , 로 정의한다.

절단 위치가 $0=t_0<t_1<\cdots<t_K=N$일 때 , 라 두면, 이 분할의 값은 정확히 이다.

이를 증명하자. $i$번 조각을 모두 지운 결과가 닫는 괄호 $a_i$개 뒤에 여는 괄호 $b_i$개가 오는 형태라 하자. 그러면 $a_i=H_{t_i}$, 이다.

$\delta_i=b_i-a_i$라 하면 전체 문자열의 괄호 합이 이므로 이고, 이다.

특정 조각 $i$의 닫는 괄호를 처리한 직후의 괄호 합을 최대한 작게 만들고 싶다고 하자. $\delta_j<0$인 다른 조각을 모두 먼저 배치한 뒤 $i$번 조각을 배치하면, 그 순간 부족한 여는 괄호의 수는 ${\displaystyle \sum _{j\mathrm{\ne }i}(-{\delta }_j{)}_{+}+a_{}}$가 된다.

반대로 어떤 순서에서도 $i$번 조각 앞에서 만들 수 있는 음의 괄호 합은 모든 음수 $\delta_j$를 먼저 모은 경우보다 작을 수 없으므로, 이보다 큰 부족량을 만들 수 없다.

따라서 모그가 만들 수 있는 최대 부족량은 $\displaystyle D+\displaystyle \max_i\min(a_i,b_i)=D+Q$ 이다. 전체 괄호 합이 이므로 마지막에는 닫는 괄호와 여는 괄호가 각각 개 남고, 점수는 이다.

서브태스크 4: 완전히 중첩된 문자열

$S=\texttt{(}^{N/2}\texttt{)}^{N/2}$인 경우, 높이 그래프는 한 번 증가한 뒤 한 번 감소한다. 모든 구간에서 내부 최솟값은 양 끝 높이 중 작은 값과 같으므로 $q(l,r)=0$이다. 따라서 이고 만 최소화하면 된다.

절단 위치의 높이를 차례대로 적으면 처음과 끝은 모두 $0$이다. 높이 그래프의 왼쪽에서는 경계가 한 칸 이상 이동할 때마다 높이가 적어도 $1$ 증가하고, 오른쪽에서는 적어도 $1$ 감소한다. 왼쪽에서 오른쪽으로 봉우리를 가로지르는 조각은 최대 하나이므로, $K$개의 조각 중 적어도 $K-1$개 조각에서는 양 끝 높이가 서로 다르다. 따라서 절단 위치 높이들의 총 변화량은 적어도 $K-1$이다.

처음과 끝 높이가 같으므로 총 증가량과 총 감소량은 같다. $D$는 총 감소량이므로 $D\geq\left\lceil\frac{K-1}{2}\right\rceil=\left\lfloor\frac K2\right\rfloor$이다.

$K=2q+1$이면 왼쪽에서 여는 괄호 $q$개를 한 글자씩 떼고, 가운데 남은 부분을 한 조각으로 두고, 오른쪽에서 닫는 괄호 $q$개를 한 글자씩 뗀다. $K=2q$이면 왼쪽에서 여는 괄호 개를 한 글자씩 떼고, 가운데 남은 부분을 한 조각으로 두고, 오른쪽에서 닫는 괄호 개를 한 글자씩 뗀다. 두 경우 모두 위 하한을 달성한다. 따라서 이다.

서브태스크 5: 모든 마지막 조각을 보는 동적 계획법

이제 $Q$의 상한을 $c$로 고정하자. 모든 조각이 $q(l,r)\leq c$를 만족하도록 제한했을 때, $\mathrm{dp}[k][r]$를 앞의 개 문자를 정확히 개 조각으로 나누는 데 필요한 의 최솟값으로 정의한다.

마지막 조각이 $S(l,r]$이면 점화식은 다음과 같다.

$$\mathrm{dp}[k][r] =\min_{\substack{0\leq l<r\ q(l,r)\leq c}} \left(\mathrm{dp}[k-1][l]+d(l,r)\right)$$

$c$는 $0,1,\ldots,N/2$만 확인하면 된다. 고정된 $c$에서 얻는 후보는 $c+\mathrm{dp}[K][N]$이다. 최적 분할의 실제 를 로 잡으면 그 분할이 DP에 포함된다. 반대로 DP가 찾은 분할의 실제 는 이하이므로, 모든 에 대해 구한 최솟값이 정확한 가 된다.

한 $c$에서 전이 수는 $O(KN^2)$이고 가능한 $c$가 $O(N)$개이므로 시간 복잡도는 $$이다. 에서는 충분하다. 부모 위치를 저장하면 분할도 복원할 수 있다.

만점 제약에서는 마지막 조각의 시작점 $l$을 모두 보는 전이를 줄여야 한다. 이를 위해 최적해를 매우 적은 종류의 조각만 사용하는 형태로 바꾼다.

조각을 희소한 형태로 정규화하기

각 경계 $i$에 대해 같은 높이가 직전에 나온 위치를 $p_i=\max\{j<i:H_j=H_i\}$로 정의한다. 가 존재할 때만 사용한다.

다음 두 종류의 조각만 고려하자.

• 한 글자 조각 $(i-1,i]$.
• 같은 높이의 직전 위치부터 현재까지의 조각 $(p_i,i]$.

정점이 $0,1,\ldots,N$인 DAG로 보면 $i-1\to i$와 $p_i\to i$만 존재한다. 따라서 각 정점으로 들어오는 간선은 최대 두 개이다.

임의의 조각 $(l,r]$은 $D$의 합과 $Q$의 최댓값을 증가시키지 않으면서 위 두 종류의 조각들로 세분할 수 있다.

$H_l=H_r$인 경우를 먼저 보자. 중간에 높이 $H_l$인 경계 가 있으면 와 로 나눈다. 두 조각의 는 모두 이고, 각 조각의 내부 최솟값은 원래 조각의 내부 최솟값 이상이므로 두 도 원래 이하이다. 중간에 같은 높이가 없다면 이므로 이미 두 번째 종류이다.

$H_l<H_r$이라 하자. $r$ 이전에 높이 $H_l$이 마지막으로 등장하는 위치를 라 한다. 이면 와 로 나눈다. 첫 조각은 양 끝 높이가 같고, 두 번째 조각은 높이 아래로 내려가지 않으므로 이다. 두 조각의 도 모두 이다. 이면 첫 문자는 반드시 이므로 한 글자 조각 을 떼어 낸다. 나머지 조각의 는 이다.

$H_l>H_r$이라 하자. $l$ 이후 처음으로 높이 $H_r$에 도달하는 위치를 라 한다. 이면 와 로 나눈다. 첫 조각의 내부 최솟값은 이므로 이고 이다. 두 번째 조각은 양 끝 높이가 같고 이다. 이면 마지막 문자는 반드시 이므로 한 글자 조각 을 떼어 낸다. 나머지 조각의 는 이고, 두 조각의 합은 원래 와 같다.

각 단계에서 조각의 길이가 줄어드므로 이 과정을 반복하면 원하는 형태만 남는다.

정확히 $K$개와 $K$개 이상의 관계

원래의 $K$개 조각을 위 방법으로 세분하면 조각 수는 어떤 $L\geq K$가 되고 값은 증가하지 않는다.

반대로 희소 DAG의 경로가 $L>K$개의 조각을 사용했다면, 인접한 조각들을 합쳐 정확히 $K$개로 만들 수 있다. 조각을 합치면 모그가 선택할 수 있는 순열은 합치기 전 순열 중 각 묶음 내부의 순서를 고정한 경우들로 제한된다. 모그의 선택지가 줄어드므로 분할의 값은 증가하지 않는다.

따라서 원래 문제의 최적값은 다음 문제와 같다.

희소 DAG에서 $0$부터 $N$까지 가는 경로 중 간선 수가 $K$ 이상인 경로의 $D+Q$ 최솟값을 구한다.

희소 간선의 비용

한 글자 간선 $i-1\to i$에서 $S_i=\texttt{(}$이면 $d=q=0$이고, 이면 , 이다. 따라서 이 간선은 에 를 더한다.