오름차순 — NYPC 2023

숫자로 구성된 문자열이 주어진다. 문자 사이에 공백을 적절히 추가해서 $1$ 개 이상의 부분문자열로 나누려고 한다.

단, 아래 조건을 만족해야 한다.

각 부분문자열이 나타내는 수는 오름차순이어야 한다. 단, 한 번의 예외를 둘 수 있다.
가능한 많은 부분문자열을 만들어야 한다.

각 부분문자열이 나타내는 수가 오름차순이라는 것은 모든 인접한 두 수에 대해 오른쪽의 수가 왼쪽의 수보다 크거나 같음을 의미한다. 여기에서 한 번의 예외를 둘 수 있다는 것은 최대 하나의 경우에 대해 왼쪽의 수가 오른쪽의 수보다 클 수 있음을 의미한다.

예를 들어, 33133의 경우, 부분문자열이 나타내는 수가 오름차순이 되도록 공백을 추가하여 가장 많은 부분문자열을 만들 수 있는 경우는 3, 3, 133, 또는 3, 31, 33이다. 그러나 첫 번째 조건에서 한 번의 예외를 둘 수 있으므로, 이를 고려하면 3, 3, 1, 3, 3이 된다.

부분문자열이 0으로 시작할 수 있음에 유의하라. 예를 들어, 103201을 1, 03, 201로 나눌 수 있고, 이 부분문자열들이 나타내는 수는 각각 1, 3, 201이다.

주어진 문자열에 대해 조건을 만족하며 부분문자열로 나눌 때, 부분문자열의 개수를 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 문자열의 수를 나타내는 정수 $T$ 가 주어진다. ( $T \geq 1$ )

이어지는 $2T$ 개의 줄에는 차례로 각 문자열에 대한 정보들이 주어진다.

$2T$ 개의 줄의 $2i-1$ 번째 줄에 $i$ 번째 문자열의 길이를 나타내는 정수 $N_i$ 가 주어진다. ( $1 \leq N_i \leq 3\,000$ )

$2T$ 개의 줄의 $2i$ 번째 줄에 $i$ 번째 문자열이 주어진다. 이 문자열은 0부터 9까지 숫자로 이루어져 있다.

입력으로 주어지는 문자열의 길이 합, 즉, $N_1 + N_2 + \cdots + N_T$ 는 $3\,000$ 을 넘지 않는다.

출력 형식

$T$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에 $i$ 번째 문자열을 조건을 만족하며 부분문자열로 나눌 때, 부분문자열의 개수를 출력한다.

예제

입력

2 5 33133 6 103201

출력

5 4

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 23점

$T \le 10$ ; $N_i \le 20$

종류 2: 31점

$N_i \le 200$

종류 3: 5점

문자열을 구성하는 숫자는 오름차순이다. 예: 03355, 22222

종류 4: 17점

문자열을 구성하는 숫자는 내림차순이다. 예: 999888, 210000

종류 5: 8점

문자열은 1부터 9까지 숫자로 이루어져 있다.

종류 6: 16점

추가적인 제한 조건이 없음.

해설

편의를 위해서, 주어진 문자열을 문자열 $S$ 라고 하고, 문자열 $S$ 의 $i$ 번째 글자를 $S[i]$ 로, 원래 문자열의 $i$ 번째 글자부터 $j$ 번째 글자까지로 이루어진 문자열을 $S[i:j]$ 로 표기한다.

2차원 배열 $L$ 이 있고 다음과 같이 정의하자.

L[i][j] := S[i:n]\text{과 }S[j:n]\text{의 공통된 접두사의 최대 길이}

이는 $\mathcal{O}(N^2)$ 의 시간복잡도로 계산할 수 있다.

또한, 2차원 배열 $D$ 가 있고 다음과 같이 정의하자.

D[i][j] := S[1:i]\text{를 부분문자열로 나누어 나타내는 수가 단조 증가하도록 할 때, }i\text{ 번째 문자가 포함되는 부분문자열의 길이가 }j\text{ 이하가 되게 할 경우 부분문자열들의 최대 개수}

각 $i$ 에 대해 가능한 $j$ 의 범위는 $1$ 이상 $i$ 이하이고, $i$ 번째 문자가 포함되는 부분문자열의 길이가 정확히 $j$ 일 경우의 값이 $v$ 이면, $D[i][j] = \max(D[i][j-1], v)$ 이다.

정확히 $j$ 인 경우의 값을 구하기 위해서, $S[i-2j+1:i-j]$ 와 $S[i-j+1:i]$ 가 나타내는 수를 비교해야 한다. 이때, 두 문자열의 길이가 같으므로, 문자열의 사전순 비교를 하면 된다. 미리 계산해둔 $L$ 의 값을 활용하여, 사전순 비교를 수행한다. 사전순 비교를 수행했을 때, $S[i-2*j+1:i-j]$ 가 나타내는 수가 $S[i-j+1:i]$ 가 나타내는 수보다 작거나 같은 경우, $k \le i-2j+1$ 이면서 $S[k] \ne 0$ 인 k에 대해, $v = D[i-j][i-j-k]$ 이다. 그렇지 않을 경우, $v = D[i-j][j-1]$ 이다.

따라서 한 $D[i][j]$ 의 값을 구하는 시간복잡도는 $\mathcal{O}(1)$ 이므로, 배열 $D$ 의 모든 값을 구하는 시간복잡도는 $\mathcal{O}(N^2)$ 이다.

비슷하게, 2차원 배열 $E$ 가 있고 다음과 같이 정의하자.

E[i][j] := S[i:n]\text{를 부분문자열로 나누어 나타내는 수가 단조 증가하도록 할 때, }i\text{ 번째 문자가 포함되는 부분문자열의 길이가 }j\text{ 이상이 되게 할 경우 부분문자열들의 최대 개수}

배열 $E$ 의 값을 구하는 것은 배열 $D$ 의 값을 구하는 것과 비슷한 방식으로 가능하다. 시간복잡도는 이전과 같이 $\mathcal{O}(N^2)$ 가 걸린다.

문제의 조건을 다르게 표현하면, 크기가 $N$ 인 수열 $A$ 가 있고, $A_1 \le A_2 \le \cdots \le A_i$ 이며, $A_{i+1} \le A_{i+2} \le \cdots \le A_N$ 를 만족하는 어떤 $i$ 가 존재하는지를 의미한다.

따라서, 정답은 모든 $i$ 에 대해 $D[i][i]+E[i+1][1]$ 의 값 중 최댓값이라고 할 수 있다. 배열 $D$ 와 배열 $E$ 가 다 계산됐다면, 이는 $\mathcal{O}(N)$ 의 시간복잡도로 구할 수 있다.

따라서, 이 문제를 해결하는 전체 시간복잡도는 $\mathcal{O}(N^2)$ 이다.