Splitting Parentheses

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

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

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

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

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

고정된 분할의 점수

문자열의 괄호 높이를 $H_0=0$으로 두고, $S_i=`(`$이면 $H_i=H_{i-1}+1$, $S_i=`)`$이면 $H_i=H_{i-1}-1$로 정의한다. 또한 $\displaystyle m_{l,r}=\displaystyle \min_{l\leq x\leq r}H_x$라 하자. $S(l,r]$은 $S_{l+1},S_{l+2},\ldots,S_r$로 이루어진 조각을 뜻한다.

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

절단 위치가 $0=t_0<t_1<\cdots<t_K=N$일 때 $D=\displaystyle \sum_{i=1}^{K}d(t_{i-1},t_i)$, $Q=\displaystyle \displaystyle \max_{1\leq i\leq K}q(t_{i-1},t_i)$라 두면, 이 분할의 값은 정확히 $2(D+Q)$이다.

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

$\delta_i=b_i-a_i$라 하면 전체 문자열의 괄호 합이 $0$이므로 $\displaystyle \sum_i\delta_i=0$이고, $D=\displaystyle \sum_i(-\delta_i)_+$이다.

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

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

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

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

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

절단 위치의 높이를 차례대로 적으면 처음과 끝은 모두 $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$이면 왼쪽에서 여는 괄호 $q$개를 한 글자씩 떼고, 가운데 남은 부분을 한 조각으로 두고, 오른쪽에서 닫는 괄호 $q-1$개를 한 글자씩 뗀다. 두 경우 모두 위 하한을 달성한다. 따라서 $X=2\lfloor K/2\rfloor$이다.

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

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

마지막 조각이 $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]$이다. 최적 분할의 실제 $Q$를 $c$로 잡으면 그 분할이 DP에 포함된다. 반대로 DP가 찾은 분할의 실제 $Q$는 $c$ 이하이므로, 모든 $c$에 대해 구한 최솟값이 정확한 $D+Q$가 된다.

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

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

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

각 경계 $i$에 대해 같은 높이가 직전에 나온 위치를 $p_i=\max\{j<i:H_j=H_i\}$로 정의한다. $p_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$인 경계 $u$가 있으면 $(l,u]$와 $(u,r]$로 나눈다. 두 조각의 $d$는 모두 $0$이고, 각 조각의 내부 최솟값은 원래 조각의 내부 최솟값 이상이므로 두 $q$도 원래 $q(l,r)$ 이하이다. 중간에 같은 높이가 없다면 $l=p_r$이므로 이미 두 번째 종류이다.

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

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

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

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

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

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

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

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

희소 간선의 비용

한 글자 간선 $i-1\to i$에서 $S_i=`(`$이면 $d=q=0$이고, $S_i=`)`$이면 $d=1$, $q=0$이다. 따라서 이 간선은 $D$에 $[S_i=`)`]$를 더한다.

점프 간선 $p_i\to i$는 양 끝 높이가 같으므로 $d=0$이다. 이 간선의 $q$를 $q_i=H_i-\displaystyle \min_{p_i\leq x\leq i}H_x$라 하자.

만점 풀이: 병목값 $Q$를 고정한 희소 DP

허용할 최대 점프 라벨을 $c$로 고정한다. $\mathrm{dp}[k][i]$를 $0$에서 $i$까지 정확히 $k$개 간선을 사용하고, 사용한 모든 점프 간선이 $q_i\leq c$를 만족할 때 가능한 $D$의 최솟값으로 정의한다. 초깃값은 $\mathrm{dp}[0][0]=0$이고 나머지는 무한대이다.

$i$로 들어오는 간선은 최대 두 개이므로 전이는 다음과 같다.

$$\mathrm{dp}[k][i] =\min\left( \mathrm{dp}[k-1][i-1]+[S_i=`)`], \mathrm{dp}[k-1][p_i] \right)$$

두 번째 항은 $p_i$가 존재하고 $q_i\leq c$일 때만 사용할 수 있다.

고정된 $c$에서 답 후보는 $c+\displaystyle \min_{k\geq K}\mathrm{dp}[k][N]$이다. 어떤 경로의 실제 최대 점프 라벨이 $Q^*$라면 $c=Q^*$에서 그 경로가 고려된다. 반대로 임의의 $c$에서 DP가 찾은 경로의 실제 $Q$는 $c$ 이하이다. 따라서 모든 $c$에 대한 후보의 최솟값은 정확한 $D+Q$이다.

확인할 $c$는 $\{0\}\cup\{q_i:p_i\text{가 존재한다}\}$만으로 충분하다. 최적 경로의 최대 점프 라벨은 $0$이거나 실제로 사용한 점프 간선의 라벨이기 때문이다.

$p_i$는 높이별 마지막 위치를 저장하여 구할 수 있다. $q_i$는 단순한 $O(N^2)$ 전처리로 계산해도 전체 복잡도에 영향을 주지 않는다. 가능한 $c$가 $O(N)$개이고, 고정된 $c$에서 $k=1,2,\ldots,N$과 $i=1,2,\ldots,N$을 한 번씩 계산하므로 전체 시간 복잡도는 $O(N^3)$이다.

값만 계산할 때는 이전 $k$층만 필요하므로 메모리 복잡도는 $O(N)$이다. 실제 분할을 출력하려면 최적의 $c$와 간선 수를 찾은 뒤, 그 $c$에서 DP를 한 번 더 수행하며 부모 간선을 저장한다. 얻은 경로가 $L>K$개 조각을 사용했다면 인접한 조각을 합쳐 정확히 $K$개로 만든다. 부모 배열을 저장하는 구현의 메모리 복잡도는 $O(N^2)$이다.

최종 답 $X$는 구한 $D+Q$의 최솟값에 $2$를 곱한 값이다.

Solution written by GPT5.6