SciOI 2023 Open Contest

$MK$명의 학생이 $M$개의 우산을 쓰고 융합인재관으로 이동한 다음 $1$명의 학생이 $M$개의 우산을 갖고 창의인재관으로 돌아오는 것을 반복하는 것이 최적입니다. 이를 시뮬레이션하면 답을 구할 수 있습니다.

$M=K=1, N > 1$일 경우 모든 학생이 융합인재관으로 건너가는 것이 불가능하므로 $-1$을 출력해야 합니다.

SciOI 2023 Open Contest - A-1 - Editorial

$i=1$부터 $N$까지 차례대로 살펴봅시다. 다음과 같은 세 가지 경우를 생각해 봅시다. 단, $A_0 = -\infty$라고 생각합니다.

* 만약 $A_i + K \le A_{i-1}$라면, 어떤 방법으로도 $A$를 증가 수열로 만들 수 없습니다. 따라서 `-1`을 출력해야 합니다.
* 만약 $A_i \le A_{i-1} < A_i + K$라면, $A_i$에 $K$를 더해야만 증가 수열로 만들 수 있습니다. 따라서 $A_i$에 $K$를 더합니다.
* 만약 $A_{i-1} < A_i$라면, $K$를 더해도, 더하지 않아도 됩니다. 그러나 $K$를 더하는 최적해가 존재할 경우, $A_i$에 $K$를 더하지 않아도 여전히 증가 수열이고, $K$를 더한 횟수가 한 번 줄어들었으므로 모순입니다. 따라서 $K$를 더하지 않는 것이 항상 최적입니다.

위와 같은 간단한 그리디 알고리즘으로 문제를 $\mathcal{O}(N)$에 해결할 수 있습니다. 

SciOI 2023 Open Contest - A-2 - Editorial

## 구간 나누기

학생들을 $A_i$ 기준으로 정렬합니다. 만약 $A_i$가 같은 학생이 여럿 있다면 $B_i$ 기준으로 정렬합니다. 이제부터는 $1 \le i < j \le N$이면 $A_i < A_j$이거나, $A_i = A_j; B_i \le B_j$라고 가정합니다.

먼저 무조건 같은 등급을 받아야 하는 학생들끼리 그룹으로 나눠야 합니다. 만약 $B_i \ge B_j$인 두 학생 $i, j$ $(i < j)$가 있다면, 서로 다른 등급을 주는 것이 불가능합니다.

* 학생 $i$에게 더 좋은 등급을 준다면 $A_i \le A_j$이므로 모순입니다.
* 학생 $j$에게 더 좋은 등급을 준다면 $B_j \le B_i$이므로 모순입니다.

따라서 두 학생 $i, j$는 같은 등급을 주어야 합니다. 그런데 이때 $i < k < j$인 임의의 학생 $k$에 대해 $B_i \ge B_k$ 또는 $B_k \ge B_j$가 반드시 성립합니다. 따라서 구간 $[i, j]$에 있는 모든 학생은 같은 등급을 주어야 합니다.

$prf[i]$를 $j \in [1, i]$에 대해 $B_j$의 최댓값으로 정의합시다. 이 배열은 누적 합 기법을 이용해 $\mathcal{O}(N)$에 계산할 수 있습니다. 이제 아래 과정을 통해 무조건 같은 등급을 주어야 하는 학생의 묶음을 계산합니다.

* 아직 묶음을 만들지 못한 학생 중 가장 번호가 큰 학생을 선택합니다. 이 학생의 번호를 $j$라고 정의하겠습니다.
* 이후 구간의 시작점 $i$를 $j$로 초기화하고, $i-1$번 학생이 이 묶음에 포함되는지의 여부를 계산하며 구간을 확장합니다.
  * 만약 $prf[i-1] \ge B_k$인 학생 $k \, (i \le k \le j)$가 있다면, $i-1$번 학생은 구간에 포함되어야 합니다.
  * 그렇지 않다면, 번호가 $i-1$ 이하인 학생은 모두 번호가 $i$ 이상인 학생보다 $B$ 값이 작으므로, 구간에 합쳐질 필요가 없습니다.
  * 위 조건을 빠르게 판단하기 위해 $min_{i \le k \le j} B_k$를 저장하는 변수를 만들고, $i$를 $1$씩 줄일 때마다 갱신하면 매번 $\mathcal{O}(1)$에 판별할 수 있습니다.
* 아직 묶음에 포함되지 않는 학생이 있다면 이 과정을 반복합니다.

위의 구간 나누기 과정은 $\mathcal{O}(N)$에 수행할 수 있습니다. 

## 답 계산하기

구간 나누기 과정이 끝난 뒤 구간의 크기를 구간에 포함된 학생의 번호가 작은 것부터 $S_1, \cdots, S_k$라고 정의합시다. 이때 $k$는 총 구간의 개수이며, 구간의 개수가 $3$개 미만이라면 등급을 부여하는 것이 불가능합니다.

이제 문제는 수열 $S$를 세 구간으로 나눠, 세 구간 중 합이 가장 큰 것과 합이 가장 작은 것의 합 차이를 최소화하는 것이 되었습니다. $S$를 구간 $[1, a]$, $[a+1, b]$, $[b+1, k]$로 나누었다고 합시다. $(1 \le a < b < k)$ 또한 각각의 구간에서 $S_i$의 합을 $A$, $B$, $C$로 정의합시다.

아래 사실을 증명할 수 있습니다.

* $a$를 고정했을 때, 문제의 답, 즉 $\max(A, B, C) - \min(A, B, C)$는 $\max(B, C) - \min(B, C)$가 최소일 때 최소가 됩니다.
* 증명
  * $a$를 고정하면 $A$의 값도 고정됩니다. 또한 $A+B+C=N$입니다.
  * 문제의 목표는 구간 $[\min(A, B, C), \max(A, B, C)]$의 길이를 최소화하는 것인데, $B+C=N-A$이므로 이 구간은 $\frac{N-A}{2}$를 반드시 포함합니다.
  * $\frac{N-A}{2}$에서 $B$와 $C$의 값이 점점 멀어질수록 $\max(B, C) - \min(B, C)$의 값도 증가하고, 동시에 구간 $[\min(A, B, C), \max(A, B, C)]$의 양끝점 중 한쪽이 변하게 되어 구간의 길이가 증가합니다.

$S$의 누적합을 계산해 배열 $sum$에 저장합니다. $sum[i]=\sum_{j=1}^{i} S_j$로 정의됩니다.

$a$는 $[1, k-2]$ 내의 값을 가집니다. 이때 $A=sum[a]$로 고정되고, $B$와 $C$는 $\frac{N-A}{2}$에 가장 가까운 값이어야 합니다. 이때 $sum[b]=A+B$이므로, $b$는 $sum[x]$가 $\frac{N+A}{2}$에 가장 가까운 $x$여야 합니다. 이 값의 후보는 이분 탐색을 이용해 찾을 수 있고, 각 $a$에 대한 값을 $\mathcal{O}(\log N)$에 구할 수 있습니다.

따라서 전체 문제를 $\mathcal{O}(N \log N)$에 해결할 수 있습니다.

SciOI 2023 Open Contest - A-3 - Editorial

## 서브태스크 1 (10점)
모든 $N!$가지 경우에 대해서 $\mathcal{O}(N^2)$에 조건을 만족하는지 확인하면 됩니다. 

## 서브태스크 2, 3, 4 (100점)

### 순열의 조건
조건을 만족하는 수열이 존재하려면 주어진 그래프 $G$가 연결 그래프여야 함은 자명합니다.

순열의 앞 $k$개 수 $\pi_1, \pi_2, \cdots, \pi_k$를 정했을 때 $\pi_{k+1}$는 $\pi_1, \pi_2, \cdots, \pi_k$ 중 하나와 인접해야 하고, $G$에서 정점 $\pi_1, \pi_2, \cdots, \pi_{k+1}$을 삭제하였을 때 남은 점들이 모두 연결되어 있어야 합니다.

### 순열이 존재하는지 판별하기
그래프 $G$의 블록 컷 트리가 선형이라면 순열이 존재하고, 선형이 아니라면 순열이 존재하지 않습니다. 

- 만약 블록 정점과 3개 이상의 정점이 연결되어 있으면 두번째 단절점이 순열에 추가되었을 때 남은 정점들로 이루어진 그래프가 두개 이상의 연결성분으로 나뉘기 때문에 순열이 존재하지 않습니다. 
- 만약 단절점과 3개 이상의 정점이 연결되어 있으면 이 단절점이 순열에 추가되었을 때 그래프가 나뉘어져 조건을 만족할 수 없습니다. 

만약 블록 컷 트리가 선형이라면, 아래에서 설명할 방법으로 블록 정점에 대하여 st-ordering을 구해 올바른 순열을 구성할 수 있습니다. 

서브태스크 2의 경우 단절점이 존재하지 않으니 항상 순열을 구성할 수 있습니다. 

### 순열이 존재한다면 구성하기
블록 컷 트리가 선형이라면 한쪽 끝에 있는 정점에서 시작하여 블록 컷 트리를 따라가며 순열을 구성할 수 있습니다. 

각 블록 정점에서 문제를 해결하는것은 biconnected component의 st-ordering을 찾는것과 동치이고, 이를 $\mathcal{O}(N+M)$ 또는 $\mathcal{O}((N+M)\log N)$에 하게 된다면 문제를 해결 할 수 있습니다. 

서브태스크 2, 3의 경우 현재 순열에 존재하는 정점 중 적어도 하나와 인접해 있고, 현재 보고 있는 BCC 안에 존재하고, 단절점이 아닌 정점을 아무거나 $\mathcal{O}(N+M)$에 찾아 순열에 추가하는 방법으로 $\mathcal{O}(N(N+M))$에 문제를 해결 할 수 있습니다. 만약 현재 BCC에서 순열에 존재하는 정점과 인접한 모든 정점이 단절점이라면 모순이 발생함을 보일 수 있고, 이로 인해 단절점이 아닌 순열에 추가 가능한 정점이 존재합니다. 

SciOI 2023 Open Contest - A-4 - Editorial

## 서브태스크 1 (10점)

$\binom{N-1}{K}$개의 경우에 대해서 $K!$개의 순서 중 가장 시간이 짧은 것을 계산하여 합하면 됩니다. 

## 서브태스크 2, 3 (100점)

트리에서 $K$개의 노드를 골랐을 때, 최단 시간으로 모든 노드를 방문하려면 다음과 같이 방문해야 합니다.
- 부모와 자식을 잇는 모든 복도에 대해, 자식의 서브트리에 학생이 존재하는 경우 복도는 두 번 방문합니다. 
  - 자식의 서브트리로 들어갈 때 한 번, 자식의 서브트리에서 나올 때 한 번 방문합니다.
  - 예외적으로, 마지막으로 방문하는 노드는 가장 depth가 높은 노드이며, 이 노드부터 루트까지의 경로에 있는 복도들은 한 번만 방문합니다.

즉, (자식의 서브트리에 골라진 노드가 있는 복도의 개수) * 2 - (가장 depth가 높은 노드에서 루트까지 있는 복도의 개수)가 총 걸리는 시간입니다. 이를 복도를 기준으로 더블 카운팅할 수 있습니다.

먼저 앞에 있는 항을 구해 봅시다. 자식의 서브트리에 골라진 노드가 있는 경우의 수는 서브트리의 크기를 $sz$라 하면 $\binom{N-1}{K} - \binom{N-sz-1}{K}$이고, 각 경우를 총합한 뒤 $2$를 곱해야 합니다.

다음으로 뒤에 있는 항을 구해 봅시다. depth가 증가하는 순서로 모든 방을 정렬한 뒤, 정렬된 순서에서 자기 이전의 방들만이 선택되었을 때, 본인의 depth만큼 총합에서 빠지게 됩니다. 즉, 현재 방이 $i$번째일 때 $depth \times \binom{i - 1}{K - 1}$만큼 총합에서 빠집니다. 

이 두 항을 이용해 답을 구할 수 있습니다.

$\binom{n}{r}$을 $\mathcal{O}(N^2)$에 전처리해서 계산하면 서브태스크 2, 이를 모듈로 역원과 팩토리얼을 이용하여 $\mathcal{O}(N)$에 계산하여 출력하면 서브태스크 3을 풀 수 있습니다. 

SciOI 2023 Open Contest - B-1 - Editorial

## Subtask 2 (37점)

모든 $i$에 대해, $S_{L_i} = A_i$이고 $S_{R_i} = B_i$이거나, $S_{L_i}=B_i$이고 $S_{R_i} = A_i$이어야 함이 자명합니다. 이때 전자의 경우 Type 1이라고 하고, 후자의 경우를 Type 2라고 합시다.

Type을 모두 정하는 방법의 수는 $2^K$가지입니다. 각각의 경우에 대해 답을 빠르게 찾는 방법을 알아봅시다. 이때, 자식이 둘 이상인 모든 정점 $x$에 대해, 각각의 자식을 순회하는 순서를 골라야 합니다. Subtask 2에서는 트리의 루트를 1번 정점으로 두었을 때 각 노드의 자식이 2개 이하입니다. 따라서 $x$번 노드의 자식이 정확히 2개라고 가정해도 좋습니다.

$x$번 노드에서 자식을 방문하는 순서를 골랐을 때 영향을 받는 $(A_i, B_i)$ 쌍은 다음 조건을 만족합니다.

* 정점 $A_i$는 정점 $x$의 조상 $(A_i \neq x)$
* 정점 $B_i$는 정점 $x$의 자손 $(B_i \neq x)$

이제부터는 위 조건을 만족하는 $i$에 대해서만 생각합시다. 이들 중 $x$의 두 자식을 $y$와 $z$라고 하고, $B_i$가 $y$의 서브트리 안에 있는 $i$ 중 Type 1인 것의 개수를 $a_1$, Type 2인 것의 개수를 $a_2$라고 합시다. 마찬가지로, $B_i$가 $z$의 서브트리 안에 있는 $i$ 중 Type 1인 것을 $b_1$, Type 2인 것을 $b_2$라고 합시다.

정점 $x$의 자식 순서 선택에 따라 추가되는 이동 거리 합은

* $y$를 $z$보다 먼저 방문할 때: $b_1\times len[y] + a_2 \times len[z]$
* $z$를 $y$보다 먼저 방문할 때: $a_1 \times len[z] + b_2 \times len[y]$

단, $len[x]$는 $x$의 서브트리를 순회하는 데 걸리는 시간입니다.

위 둘 중 하나의 순서를 고르는 것은 모든 노드 $x$에 대해 독립적이므로, $\mathcal{O}(2^K \times N)$ 시간에 문제를 해결할 수 있습니다.

### Subtask 3 (84점)

정점 $x$의 자식이 여러 개일 수 있습니다. 각 자식을 $c_1, \cdots, c_l$이라고 하고, $i$번째 자식에 대해 앞의 조건을 만족하는 $j$ 중 Type 1인 것의 개수를 $d_i$, Type 2인 것의 개수를 $u_i$라고 합시다.

만약 $u_i \ge 1$이고 $d_i \ge 1$이라면, $u_i$와 $d_i$ 하나씩을 함께 제거하는 것이 가능합니다. $c_i$를 어느 순서에 배치해도, $c_i$보다 앞에 있는 자식의 서브트리를 한 번 순회하고, $c_i$보다 뒤에 있는 자식의 서브트리도 한 번 순회하기 때문입니다. 이때 비용에는 $sz[x] - sz[c_i]$가 더해져야 합니다.

따라서 $u_i = 0$ 또는 $d_i = 0$인 경우만 생각해도 됩니다. 다음과 같은 세 가지 경우로 자식을 나눌 수 있습니다.

* $u_i = d_i = 0$: 어떤 순서에 배치해도 직접적으로 비용에 더해지는 값이 없습니다.
* $u_i \neq 0$: $c_i$보다 나중에 방문하는 자식의 서브트리를 모두 방문하게 됩니다. 따라서 이러한 노드를 최대한 뒤에 방문하는 것이 좋습니다.
* $d_i \neq 0$: $c_i$보다 먼저 방문하는 자식의 서브트리를 모두 방문하게 됩니다. 따라서 이러한 노드를 최대한 먼저 방문하는 것이 좋습니다.

따라서, $d_i \neq 0$인 자식을 먼저 방문하고, $u_i = d_i = 0$인 자식을 방문한 뒤, $u_i \neq 0$인 자식을 방문하는 것이 최적입니다.

이제 $d_i \neq 0$인 자식끼리, $u_i \neq 0$인 자식끼리 방문 순서를 정해야 합니다. $d_i \neq 0$인 자식 두 개가 $c_1$과 $c_2$라고 합시다. 이때, $c_1$을 먼저 방문하는 것이 더 이득일 조건은

$$
sz[c_1] \times d_{c_2} \le sz[c_2] \times d_{c_1}
$$

임을 알 수 있습니다. 이 조건은 결합 법칙이 성립합니다. 따라서 이 조건으로 $c_i$를 정렬한 뒤, 정렬 순서대로 방문하면 $d_i \neq 0$인 자식끼리의 순서를 정할 수 있습니다. $u_i \neq 0$인 자식에 대해서도 마찬가지의 방법으로 해결할 수 있습니다.

시간 복잡도는 $\mathcal{O}(2^K \times N \log N)$입니다.

### Subtask 4 (100점)

사실 원래 트리에서 의미 있는 정점은 그렇게 많지 않습니다. 문제의 답이 기존과 똑같도록 트리 정점의 개수를 $8K$개 이하로 줄이는 것이 가능합니다. 필요한 정점은 다음과 같습니다.

* $A_i$와 $B_i$ (최대 $2K$개)
* 앞 $2K$개 정점을 기준으로 트리 압축할 때 추가되는 정점 (최대 $2K-1$개)
* 앞 $4K-1$개 정점으로 트리를 구성했을 때, 각 간선의 구간 사이에서 뻗어나오는 가지가 있다면, 해당 가지를 표현하는 정점 (최대 $4K-2$개)
  * 트리 압축 이후 같은 간선 구간에서 뻗어나오는 가지들은 해당 간선을 따라 내려오는 시점이나, 간선을 따라 올라오는 시점에서 방문될 것입니다. 그런데 이 두 시점 중 브루가 데리고 다니는 친구가 더 적은 시점이 항상 최적입니다. 따라서 이 모든 가지들은 같은 시점에 방문하는 것이 이득입니다.
  * 이 과정에서 포함되지 않은 모든 곁가지들은 답에 영향을 주지 않습니다.

위 정점만 만들면 트리 정점의 개수가 $\mathcal{O}(K)$가 되고, 문제를 $\mathcal{O}(2^K \times K \log K)$에 해결할 수 있습니다.

SciOI 2023 Open Contest - B-2 - Editorial

다음과 같이 트리를 변형하여 새로운 트리 $T'_{1}$을 만듭니다.

$i=1$부터 $N$까지에 대해, 현재 $T_{1}$에서 $i$에 인접한 노드 중 값이 $i$보다 작은 노드들을 $i$와 합칩니다. 합쳐진 노드들을 $s_1, s_2, ..., s_k$라 하면, 이들을 $T_{1}'$에서 조상이 $i$가 되도록 $i$와 잇습니다. 

위 과정을 반복하면 트리 $T_1$엔 노드 $N$만 남게 되며, 루트가 $N$인 트리 $T'_{1}$을 얻을 수 있습니다. 위 과정은 Union-Find를 통해 쉽게 구현 가능합니다. 마찬가지로 트리 $T_2$에 대해서도 변형하여, $T'_{2}$를 만듭니다.

닌자부 부원 집합 $S$에 대해, 트리 $T_1$에서의 파티가 열리는 노드는 트리 $T'_1$에서 $S$에 속하는 노드들의 LCA(Lowest Common Ancestor)입니다. 위 성질을 이용하여 문제를 풀 수 있습니다.

파티가 열리는 방의 번호를 고정하고 생각해봅시다. 파티가 열리는 방의 노드가 $c$일 때, 트리 $T'_1$에서 $c$의 자손들의 서브트리 집합을 $A_1, A_2, ..., A_s$, 트리 $T'_2$에서 $c$의 자손들의 서브트리 집합을 $B_1, B_2, ..., B_t$라고 합시다. (서브트리 크기의 내림차순으로 정렬되어 있다고 생각합시다.) 또한 $A$를 $A_1, A_2, ..., A_s$의 합집합, $B$를 $B_1, B_2, ..., B_t$의 합집합이라고 합시다. 

$c$에서 파티가 열리게 되는 경우는 다음 두 가지로 나뉠 수 있습니다. 편의상 닌자부 부원 집합을 $S$으로 표기합시다.

1. $c$가 $S$의 원소인 경우. 이 경우, $S$의 나머지 원소들은 $T'_1$와 $T'_2$에서 모두 $c$의 서브트리 내에 존재해야 합니다. (그래야 LCA가 $c$가 됩니다.) 이 경우 원소로 가능한 것의 수는 $|A \cap B|$개이므로, 가능한 $S$의 개수는 $2^{|A \cap B|}$개 입니다.

2. $c$가 $S$의 원소가 아닌 경우. 일단 $S$의 나머지 원소들은 $T'_1$와 $T'_2$에서 모두 $c$의 서브트리 내에 존재해야 하므로 $S \subset |A \cap B|$이어야 합니다. 또한 $S \cap A_i \ne \empty$인 $i$의 개수가 2개 이상이어야 $T'_1$에서의 LCA가 $c$가 됩니다. $T'_2$에서도 마찬가지로 $S \cap B_i \ne \empty$인 $i$의 개수가 2개 이상이어야 합니다. 위를 바탕으로 포함 배제의 원리를 이용하면, 답이 다음과 같음을 알 수 있습니다. $(2^{|A \cap B|} - 1) -\sum_{i}^{} (2^{|A_i \cap B|} - 1) -\sum_{j}^{} (2^{|A \cap B_j|} - 1) + \sum_{i, j}^{} (2^{|A_i \cap B_j|} - 1)$

즉, 답을 구하기 위해선 모든 $i, j$에 대해 $|A_i \cap B_j|$를 구할 수 있으면 됩니다. 이를 위해, Small-To-Large의 논리를 이용합니다. Small-To-Large Merging을 통해 현재 집합들이 set으로 관리된 상태를 가정합니다. ($O(N\log^2 N)$에 가능함이 알려져 있습니다.)

$(i, j)$에 대해, 
1. $i \ne 1, j \ne 1$일 때, 즉 둘 모두 Small일 때. 이 때는, 먼저 배열 $D$를 만들어 임의의 원소 $x$가 $A_2, A_3, ..., A_s$ 중 어디에 속하는지를 기록합니다. 속하지 않으면 기록하지 않습니다. 이는 $O(|A_2| + |A_3| + ... + |A_s|)$에 가능합니다. 이후 $B_2, B_3, ..., B_t$의 원소들을 순회하면서 배열 $D$의 기록을 바탕으로 |A_i \cap B_j| 값을 구할 수 있습니다. 이 과정을 map이나 hash map 등으로 기록하여 $i \ne 1, j \ne 1$일 때의 |A_i \cap B_j| 값을 모두 구할 수 있습니다. hash map을 사용할 경우 시간복잡도는 $O(|B_2| + |B_3| + ... + |B_t|)$에 가능합니다. 전체 시간복잡도는 $O(|A_2|+ ... + |A_s| + |B_2| + ... + |B_t|)$이며, 모든 $c$에 대해 이를 처리할 경우 $O(N\log N)$임이 알려져 있습니다.
2. $i = 1, j \ne 1$일 때. $B_2, B_3, ..., B_t$를 순회하면서 관리된 집합 $A_1$에 속하는지를 set에서의 find연산을 통해 확인해주면 됩니다. $O((|B|-|B_1|) \log |A_1|)$ 시간이 걸리며, 모든 $c$에 대해 처리할 경우 $O(N\log^2 N)$ 시간이 소요됩니다.
3. $i \ne 1, j = 1$일 때. 2와 마찬가지로 처리해주면 됩니다.

$i = 1, j = 1$일 때만 처리해주면 문제를 풀 수 있습니다. $X_c$, $Y_c$를 각각 $A_1, B_1$이라 합시다. $N$개의 쌍 $(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)$에 대해 값을 구해주면 됩니다. Euler Tour, Segment Tree, Small-To-Large를 이용해 쉽게 해결할 수 있습니다. 

SciOI 2023 Open Contest - B-3 - Editorial

괄호 문자열 $S$의 부분 문자열 $S[l], S[l+1], \cdots, S[r]$를 $S[l:r]$로 표기합니다.

## Subtask 2 (38점)
$N$이 짝수이면 준희가 승리합니다. 올바른 괄호 문자열의 길이는 항상 짝수이고, $N$이 짝수이면 준희가 문자를 지울 때 $S$의 길이가 짝수가 됩니다. 따라서 지민이가 이기려면 $S$의 홀수 길이 부분 문자열 $P$의 맨 앞의 문자를 지운 문자열과 맨 뒤의 문자를 지운 문자열 모두가 올바른 괄호 문자열이 되어야 하지만, 그런 괄호 문자열은 존재하지 않음을 보일 수 있습니다.

$N$이 홀수일 때 어떤 정수 $x\ \left(0\le x < \left\lfloor\frac N 2\right\rfloor\right)$에 대해서 $S[x+1:N-x-1]$ 또는 $S[x+2:N-x]$가 올바른 괄호 문자열이 된다면 지민이가 승리하고, 그런 $x$가 존재하지 않는다면 준희가 승리합니다.

전자의 경우에서 $S[x+1:N-x-1]$이 올바른 괄호 문자열이라면, 지민이는 처음에 $S[N]$을 지우고, 이후에는 바로 전에 준희가 지운 곳의 반대쪽에 있는 문자를 지우면 $S[x+1:N-x-1]$을 만들 수 있어 지민이가 이깁니다. $S[x+2:N-x]$가 올바른 괄호 문자열인 경우에는 처음에 $S[1]$을 지운 후 위 전략을 통해 이길 수 있습니다.

후자의 경우에는 준희가 직전 차례에서 지민이가 문자를 지운 곳의 반대쪽에 있는 문자를 지우는 전략을 쓰면 준희가 이길 수 있습니다. 지민이의 차례에는 문자열의 길이가 홀수이므로 올바른 괄호 문자열이 만들어지지 않으며, 준희의 차례에는 문자열이 어떤 정수 $x$에 대해 $S[x+1:N-x-1]$이거나 $S[x+2:N-x]$이기 때문에 조건에 의해 올바른 괄호 문자열이 만들어지지 않습니다.

즉, 모든 $x$에 대해서 $S[x+1:N-x-1]$과 $S[x+2:N-x]$가 올바른 괄호 문자열인지 판별하면 되므로 $N\le 1000$일 때에는 $\mathcal{O}(|T|)$로 위 괄호 문자열들이 올바른지 판단하면 $\mathcal{O}(N^2)$에 해결할 수 있습니다. 비슷한 방법으로 Dynamic Programming을 통해서도 해결할 수 있습니다.

## Subtask 3 (100점)
$N$이 홀수일 때 모든 $x$에 대해 $S[x+1:N-x-1]$이 올바른 괄호 문자열인지 시간 내에 판단할 수 있으면, 대칭적으로 $S[x+2:N-x]$도 판단할 수 있기 때문에 전자의 경우에 대해서만 서술합니다.

어떤 문자열 $T$가 올바른 괄호 문자열이라는 것은 $T[i]$가 `(`일 때 $A[i]=1$, $T[i]$가 `)`일 때 $A[i]=-1$인 수열 $A$의 모든 prefix sum이 0 이상이고 prefix sum의 마지막 원소가 0인 것과 동치임을 이용합니다.

위와 같이 괄호 문자열 $S$에 대해서 만든 수열을 $A$, $A$의 prefix sum을 저장한 배열을 $\Sigma$라고 하겠습니다. $S[x+2:N-x-2]$를 판정한 결과를 통해서 $S[x+1:N-x-1]$이 올바른 괄호 문자열인지 판정합니다. 앞선 판정에서 $M=\min_{x+2\le i\le N-x-2}\Sigma[i]$를 저장했다면, $M:=\min\{\Sigma[x+1], M, \Sigma[N-x-1]\}$을 통해 $M$을 갱신할 수 있고, $S[x+1:N-x-1]$가 올바른 괄호 문자열인지 판별하기 위해서는 $M\ge \Sigma[x]$와 $\Sigma[N-x-1]=\Sigma[x]$를 만족는지 판별하면 됩니다. 이 과정은 $\mathcal{O}(1)$에 할 수 있으므로 전체 과정을 $\mathcal{O}(N)$에 할 수 있습니다.

SciOI 2023 Open Contest - C-1 - Editorial

## $Q_{max}=N$ (10점)

모든 $i$에 대해 `diff 1 i`를 질의하고, 인접한 질의의 차이가 1이라면 그 사이에서 숫자가 바뀌었다는 정보를 얻을 수 있고, 따라서 모든 $i$에 대해 $S_i$의 값을 알 수 있습니다.

## $Q_{max}=3\lceil\log_2 N\rceil+8$ (42점)

### 개수 찾기

$S_1=1$임을 이용하여 `count 1 N`과 `count 2 N`을 비교했을 때 1만큼 차이나는 값이 하나 있을 것이므로 이를 통해 $1$의 개수를 알 수 있습니다. 같은 방식으로 $2$, $3$, $4$가 처음 등장하는 위치를 찾으면 개수를 알 수 있습니다.

### 위치 탐색
$2$가 처음 등장하는 위치를 $B$라 하면, $1\le i < B$인 $i$는 `diff 1 i` 질의의 값이 0이고, $B\le i\le N$인 $i$에 대해서는 1 이상입니다. 따라서 이분탐색을 통해 $B$의 값을 알 수 있고, 이 과정은 질의를 $\lceil\log_2 N\rceil$번 사용합니다.

비슷한 방식으로 첫 $3$과 $4$의 위치도 찾을 수 있습니다.

따라서 위치 탐색 $3\lceil\log_2 N\rceil$번, 개수 찾기 $8$번으로 문제를 해결할 수 있으며, 최대 $38$번의 질의를 사용하므로 42점을 얻을 수 있습니다.

## $Q_{max}=2\lceil\log_2 N\rceil+6$ (56점)

위의 과정에서 $4$의 개수는 $1$, $2$, $3$의 개수의 합을 $N$에서 뺀 값이기에 구할 필요 없으며, 따라서 $4$의 위치도 구할 필요가 없습니다. 이는 위치 탐색으로 $2\lceil\log_2 N\rceil$번, 개수 찾기로 $6$번을 사용하므로 최대 $26$번의 질의를 해 56점을 얻을 수 있습니다.

## $Q_{max}=\lceil\log_2 N\rceil+6$ (90점)

만일 $4$가 $S$에 나오지 않는다면 `diff 1 N`의 값이 2 이하임을 알 수 있습니다. 즉 `count 1 N`, `count 2 N`, `count 1 N-1`을 통해 $1$의 개수와 $3$(또는 $3$이 $S$에 나오지 않는다면, $2$)의 개수를 알 수 있고, 따라서 $2$의 개수를 알 수 있으므로 이 경우는 $3$번의 질의만으로 답을 구할 수 있습니다. 이후에 나오는 모든 서술은 $1$, $2$, $3$, $4$가 $S$에 하나 이상 있음을 가정합니다.

편의를 위해 아래와 같은 문자들을 사용합니다.
* $1$, $2$, $3$, $4$의 개수 $a$, $b$, $c$, $d$
* $3$이 처음으로 $S$에서 등장하는 위치 $C$
* $i\ge C$인 부분에서 $1$, $2$의 개수 $a'$, $b'$ $(a'<a, b'<b)$

위와 같은 이분탐색 과정을 거치되, 이번에는 처음으로 나오는 $3$의 위치 $C$만 찾습니다. 사용한 쿼리는 $\lceil\log_2 N\rceil$번입니다.

다음과 같은 6번의 질의를 합니다. 각각의 질의에서 얻어지는 중복집합을 질의 오른쪽에 표기하겠습니다.

1. `count 1 N`: $P_1=\{a, b, c, d\}$
2. `count 2 N`: $P_2=\{a-1, b, c, d\}$
3. `count C N`: $P_3=\{a', b', c, d\}$
4. `count C+1 N`: $P_4=\{a', b', c-1, d\}$
5. `count 1 C-1`: $P_5=\{a-a', b-b', 0, 0\}$
6. `count 1 C-2`: $P_6=\{a-a', b-b'-1, 0, 0\}$

이 질의들과 다음과 같은 과정을 통해 $a$, $b$, $c$, $d$를 구합니다.

1. $P_1$, $P_2$ $\Longrightarrow$ $a$
2. $P_3$, $P_4$ $\Longrightarrow$ $c$
3. $P_5$, $P_6$ $\Longrightarrow$ $a-a'$, $b-b'$
4. $a$, $a-a'$ $\Longrightarrow$ $a'$
5. $a$, $a'$, $c$, $P_1$, $P_3$ $\Longrightarrow$ $Q_1=\{b, d\}$, $Q_2=\{b', d\}$

만일 $b=d$이면 $a$, $b$, $c$, $d$를 모두 알 수 있으므로 정답을 반환합니다. 이후 과정은 $b\ne d$일 경우 진행합니다.

6. $Q_2$, $b-b'$ $\Longrightarrow$ $Q_3=\{b, d+(b-b')\}$
7. $Q_1$, $Q_3$ $\Longrightarrow$ $Q_1\cap Q_3 = \{b\}$

$d=N-a-b-c$이므로 $a$, $b$, $c$, $d$를 모두 구할 수 있습니다.

이분탐색에서 $\lceil\log_2 N\rceil$번을 사용했고, 이후 추가 질의를 $6$번 했으므로 최대 $16$번의 질의로 답을 구할 수 있고 이는 90점을 받습니다.

## $Q_{max}=\lceil\log_2 N\rceil+5$ (100점)

위의 이분탐색 과정은 `count` 쿼리로도 할 수 있습니다. $C$를 찾는 과정은 `count 1 k`에서 나오는 집합에 $0$이 두 개 이상 등장하는지를 통해 알 수 있습니다. 여기에서는 똑같이 $\lceil\log_2 N\rceil$번의 질의를 사용합니다.

이 이분탐색은 $C-1$의 값을 반환합니다. 따라서 적절한 이분탐색을 하면 이분탐색의 마지막 쿼리는 `count 1 C-1` 또는 `count 1 C-2`가 됩니다. 이는 90점 풀이의 5번 또는 6번 질의와 같으므로 $1$번의 쿼리를 덜 사용할 수 있습니다.

이 풀이는 $Q_{max}=\lceil\log_2 N\rceil+5 \le 15$번 이하의 쿼리를 사용하므로 100점을 받을 수 있습니다.

SciOI 2023 Open Contest - C-2 - Editorial

## 피봇 찾기

$N$개의 수 중 하나를 이용해 피봇 $p$를 찾을 수 있습니다. $N$을 수열 $A$의 맨 앞에 배치했을 때, 피봇 $p$의 값에 따라 수열 $A'$에서 다음과 같은 특징이 나타납니다.

* $1 \le p < N$: 수열 $A$에서 $N$은 $p$보다 큰 수 중 가장 왼쪽에 있습니다. 따라서 수열 $A'$에서 $N$ 직전에 나오는 수가 $p$입니다.
* $p=N$: $N$은 $A'$의 마지막 원소입니다.

$A'$에서 위 두 가지 경우를 뚜렷하게 구분할 수는 없습니다. 그러나 수 $N$의 초기 위치는 배열 상에서 아무런 정보를 추가하지 못합니다. 따라서 실제로 피봇이 $N$이었을 경우, 수열 $A'$ 상에서 그 직전의 수를 피봇이라고 가정해도 정보 손실은 $p \neq N$인 경우와 같습니다. 따라서 항상 $N$ 직전의 수가 피봇이라고 생각해도 좋습니다.

## 비트스트링 전달하기

이제부터는 앞 단계에서 피봇을 찾기 위해 사용한 $N$을 무시하고, $N$이 $1$ 감소한 대신 피봇 $p$를 아는 상태로 문제를 푼다고 생각합시다.

다음을 관찰할 수 있습니다. 증명은 문제 상황에 의해 자명합니다.

* $1 < a < b < p$이거나, $p < a < b < N$이라면, 수열 $A$에서 $a$와 $b$의 순서는 수열 $A'$에서 $a$와 $b$의 순서와 일치한다.

다음과 같은 구조로 수열을 인코딩하는 것을 생각해 봅시다.

* 먼저 구간 $[1, N]$을 절반씩 쪼개는 것을 재귀적으로 반복해 세그먼트 트리 형태를 만듭니다. 이때 각 구간 $[l, r]$의 깊이는 $[1, N]$에서 시작해 해당 구간을 만들기 위해 구간을 쪼갠 횟수로 정의합니다. **깊이가 같은 구간들은 서로 겹치지 않습니다.**
* 깊이가 큰 구간부터 시작해 해당 구간의 수를 섞습니다. 길이가 $2$ 이상인 구간 $[l, r]$에 대해, $m=\lfloor \frac{l+r}{2} \rfloor$ 로 정의한다면, $[l, m]$ 사이의 값끼리의 순서, 그리고 $[m+1, r]$ 사이의 값의 순서는 이미 앞에서 정했습니다. 이 두 구간의 수들을 섞는 경우의 수는 $\binom{r-l+1}{m-l+1}$입니다.
  * 만약 수열 $A$를 섞지 않는다면, 즉 피봇이 존재하지 않는다면, 위 방식으로 $N!$개의 순열을 모두 만들 수 있습니다.
* 피봇 $p$의 존재로 인해 $p \in [l, r]$인 모든 구간 $[l, r]$에서 정한 순서는 변하게 됩니다. 이러한 구간은 각 깊이에 최대 하나뿐입니다. 따라서 깊이별로 하나의 구간 정보가 파괴되어도 복구할 수 있도록 해야 합니다.
  * 어떤 구간 $[l, r]$에 대해, 해당 구간의 **순서값**을 구간 $[l, r]$에서 섞는 방법 중 실제 해에 적용된 것의 사전순 인덱스라고 정의합니다.
  * 각 깊이별로 가장 길이가 긴 구간 $[s, e]$를 잡고, 그 구간의 길이를 $len$이라고 합시다. $[s, e]$의 순서값은 경우의 수를 늘리는 데 사용하지 말고, 해당 깊이의 모든 구간의 순서 값을 더했을 때 $len!$으로 나누어떨어지도록 설정합니다.
  * 이렇게 하면 깊이별로 가장 긴 구간에 대한 경우의 수만 희생하고 정보를 얻어낼 수 있습니다.

위 방식대로 만들 수 있는 경우의 수는 다음과 같습니다.

$$
59! \times \left( \binom{59}{30} \times \binom{30}{15} \times \binom{15}{8} \times \binom {8}{4} \times \binom{4}{2} \times \binom{2}{1} \right) ^{-1}
$$

위 식을 계산하면 $2^{160}$보다 큽니다. 따라서 $L=160$인 경우를 해결해 75점을 얻을 수 있습니다.

100점을 얻기 위해서는 구조를 조금 변경해야 합니다. 다음과 같이 변경하면 됩니다.

* 구간을 $[1, 20]$, $[21, 40]$, $[41, 59]$ 세 개로 나누고, 각각에 대해 $L=160$ 풀이와 같은 방식으로 압축합니다. 
* $[2, 20]$의 수와 $[21, 30]$의 수를 서로 섞고, $[41, 59]$의 수와 $[31, 40]$의 수를 서로 섞습니다. 이때 두 개의 순서값이 일치하도록 섞습니다. 이 부분에서 $\binom{29}{10}$가지 경우를 얻을 수 있습니다.

위 풀이로 만들 수 있는 경우의 수는 다음과 같습니다.

$$
\left(19! \times 20! \times 20! \right) \times \left( \binom{20}{10} \times \binom{10}{5} \times \binom{5}{3} \times \binom{3}{2} \times \binom{2}{1} \right)^{-1}
$$

위 식을 계산하면 $2^{171}$보다 큽니다. 따라서 $L=171$인 경우를 해결해 100점을 얻을 수 있습니다.

C나 C++의 경우 `__int128`이나 큰 수 자료형을 사용하지 않고 문제를 해결할 수 있으나, 큰 수 자료형을 이용할 경우 구현이 더 쉽습니다.

$L =175$인 풀이 역시 발견하였으나 대회에 출제하기 부적절하다고 판단하여 출제하지 않았습니다. $L$이 더 큰 풀이도 충분히 존재할 수 있습니다.