2023 건국대학교 프로그래밍 경진대회 (KUPC) - Open Contest

$1$ 이후에 $0$ 이 등장한다면, 검은 줄의 구간이 끝나는 것을 의미합니다.

주어진 문자열을 훑으면서, $s_i = 1$이면서 $s_{i+1} = 0$인 $i$의 개수를 셉시다.

구현의 편의를 위해, 주어진 문자열에 $0$을 추가해도 답은 같습니다.

시간복잡도는 $\mathcal{O}(N)$ 입니다.  

건덕이와 건구스는 자신의 차례에 **반드시** 움직여야 합니다.

건덕이와 건구스가 한 턴동안 움직이는 경우의 수는 네 가지입니다.
- 건덕이가 왼쪽으로, 건구스가 왼쪽으로
- 건덕이가 왼쪽으로, 건구스가 오른쪽으로
- 건덕이가 오른쪽으로, 건구스가 왼쪽으로
- 건덕이가 오른쪽으로, 건구스가 오른쪽으로

어떻게 움직이더라도 두 플레이어 사이 간격의 **홀짝성**<sup>parity</sup>은 변하지 않습니다.

간격을 짝수로 만드는 사람은 결국 두 플레이어 사이의 거리를 $0$으로 만듭니다.

플레이어 사이의 거리가 $0$이 되는 순간, 다음 차례의 플레이어는 공격할 수 있습니다.

전장을 벗어나도록 이동할 수 없으므로, **두 플레이어간 간격은 단조감소**합니다.

따라서 전장의 길이가 짝수인 경우, 건덕이가 승리합니다.

주어진 전장의 길이의 홀짝성을 판단하므로 시간복잡도는 $\mathcal{O}(1)$입니다.

바닥수 $N$이 주어졌을 때, 바닥수가 $N$인 길이 $L$의 원래 수를 구해야 합니다.

길이 $L$의 모든 수에 대해서 바닥수가 되는지 확인하는 것은 오래 걸립니다.

곱셈의 항등원을 이용합시다. $1$은 여러 번 곱해도 $1$입니다.

$1$을 $L-1$번 적은 뒤, $N$를 뒤에 덧붙인 수의 바닥수는 $N$입니다.

원래 수는 $0$으로 시작하지 않음에 주의합시다.

학생의 키가 같은 쌍이 존재하지 않는다면, 모든 학생이 참여할 수 있습니다.

모두가 한 쪽을 바라보고, 바라보는 방향으로 키가 작아지도록 줄세우면 됩니다.

학생의 키가 같은 쌍이 존재하는 경우에는 몇 명까지 참여할 수 있을까요?

- 두 명의 키가 서로 같다면, 서로 반대 방향을 보고 서면 됩니다.
- 세 명의 키가 서로 같다면, 한 명은 어느 쪽을 보든 점프할 타이밍을 놓칠 수 있습니다.

따라서 키가 같은 사람은 **최대 두 명**까지만 참여할 수 있습니다.

키의 범위가 최대 $1\,000$이므로, 각 키에 해당하는 학생 수를 세어주면서 해결할 수 있습니다.

시간복잡도는 $\mathcal{O}(N)$입니다.

왼쪽 절반의 문자와 오른쪽 절반의 문자의 교환을 통해 팰린드롬을 만들어 봅시다.

연산을 통해 임의의 위치에 존재하는 두 문자를 교환할 수 있다면, 모든 문자를 원하는 곳에 배치할 수 있습니다.

편의상 배열의 길이가 짝수라고 가정합시다. 교환하는 경우의 수는 두 가지입니다.
- 두 문자가 서로 다른 절반에 속하는 경우
- 두 문자가 같은 절반에 속하는 경우

두 문자가 서로 다른 절반에 속하는 경우, 두 원소를 직접 교환할 수 있습니다.

두 문자가 서로 같은 절반에 속하는 경우에는 두 원소를 직접 교환할 수 없습니다.

이때, 반대쪽 절반에 속하는 원소 한 개를 임시로 사용해 교환할 수 있습니다.

![Alt text](https://static.solved.ac/arena/editorial/10/image-1.png)

문자열의 길이가 홀수인 경우에는 가운데 글자를 교환할 수 없음에 유의합시다.

해당 문자를 세지 않고, 짝수 길이의 문자열이라고 생각하면 됩니다.

팰린드롬이 되기 위해서는 양 쪽에 같은 수의 문자가 존재해야 합니다.

알파벳이 문자열에 짝수번 등장한다면 양 쪽에 골고루 분배할 수 있습니다.

시간복잡도는 $\mathcal{O}(N)$입니다.

두 개의 말뚝과 깃대 하나를 골라 만들 수 있는 삼각형 넓이 중 최댓값을 구합시다. 단, 넓이가 $R$ 이하여야 합니다.

만약 밑변을 고정한다면, 주어진 깃대를 정렬한 뒤 이분탐색을 사용할 수 있습니다.

가능한 모든 밑변을 구하는 데에는 $\mathcal{O}(N^2)$입니다.

이분 탐색에 깃대를 활용하기 위해 깃대를 정렬하는 데 $\mathcal{O}(M \log M)$입니다.

하나의 밑변 길이에 대해서, $R$ 이하인 최대 넓이를 구하는 데 $\mathcal{O}(\log M)$이 듭니다.

$\mathcal{O}(M \log M + N^2 \log M)$의 시간복잡도로 해결할 수 있습니다.

스위치를 누르면 $3$초동안 두 배의 점수를 얻을 수 있습니다.

음수의 점수도 두 배로 계산됨에 유의해야 합니다.

그리디하게 스위치를 누르는 전략은 오답을 받습니다.

현재 시각이 $i$초일 때, 스위치의 효과가 $j$초 남았다는 것을 활용해 아래와 같이 DP 테이블을 정의할 수 있습니다.
$$
\begin{align*}
d_{i,0} &= \max(d_{i-1, 0}, d_{i-1, 1}) + arr_i \\
d_{i,1} &= d_{i-1,2} + 2 \times arr_i \\
d_{i,2} &= d_{i-1,3} + 2 \times arr_i \\
d_{i,3} &= \max(d_{i-1, 0}, d_{i-1, 1}) + 2 \times arr_i
\end{align*}
$$

모든 테이블을 계산한 뒤, $d_{N}$ 중 가장 큰 값을 정답으로 취하면 됩니다.

시간복잡도는 $\mathcal{O}(N)$입니다.

![Alt text](https://static.solved.ac/arena/editorial/10/image-2.png)

일감호입니다.

무게가 $3$인 무게추를 달아 $3$의 힘으로 낚싯대를 휘두르면 회색 칸에 찌가 도달합니다.

빨간 색 테두리에 해당하는 칸에 존재하는 $8$마리의 물고기가 사로잡힙니다.

![Alt text](https://static.solved.ac/arena/editorial/10/image-3.png)

낚싯줄을 한 바퀴 감아올리면 찌의 위치가 바뀝니다.

바뀐 칸에서 물고기 4마리가 사로잡힙니다.

이를 미끼가 일감호를 벗어날 때까지 반복합니다.

![Alt text](https://static.solved.ac/arena/editorial/10/image-4.png)

쿼리가 주어질 때마다 다음과 같은 계단 모양에 칠해진 수의 합을 구하는 문제입니다.

매 쿼리마다 계산하는 $\mathcal{O}(NMQ)$ 풀이가 있으나, 시간 초과입니다.

![Alt text](https://static.solved.ac/arena/editorial/10/image-6.png)

조금 더 빠르게 해결하는 방법을 알아 봅시다. 아래쪽으로 누적합을 구해준 뒤, 오른쪽 아래 대각선 방향으로 누적합을 구해나가면
정답을 구할 수 있습니다.

시간복잡도는 $\mathcal{O}(NM+Q)$입니다.

주어진 등굣길을 그래프로 모델링해 봅시다. 각 칸에 쓰인 수만큼 양쪽 방향으로 떨어진 칸으로 향하는 간선을 만들 수 있습니다.

최대 두 번 방향을 반전할 수 있으므로, 같은 칸이라도 $0$번 반전했을 때와 $2$번 반전했을 때는 다르게 생각해야 합니다.

하나의 칸을 세 개의 정점으로 나누어 아래와 같은 그래프 모형을 생각할 수 있습니다.

![Alt text](https://static.solved.ac/arena/editorial/10/time.png)

문제의 정답은 $1$번 정점에서 학교에 해당하는 정점들까지의 최장거리와 같습니다.

구축한 그래프는 사이클 없는 방향 그래프이므로 $1$번 정점에서 위상정렬을 시행한 뒤, 정렬한 순서대로 정답을 갱신해나갈 수 있습니다.

학교에 **처음 도착한 시간**을 늦추는 것에 유의합시다. 학교에서 되돌아가는 간선은 존재할 수 없습니다.

시간복잡도는 $\mathcal{O}(N)$입니다.

더 간단한 풀이로, 단순하게 오른쪽으로 한 번, 왼쪽으로 한 번, 다시 오른쪽으로 한 번 DP를 훑어도 해결할 수 있습니다.

아직 나에게 오는 경로가 없거나 이미 학교에 도착한 경우, 칸에 $0$이 쓰인 경우 등을 잘 처리해야 합니다.

시간복잡도는 위와 같은 $\mathcal{O}(N)$이지만, 상수가 작아 더 빠르게 통과합니다.

주어진 문자열을 하나의 집합으로 생각합니다. 예를 들어 문자열이 `0011223344`라면 대응되는 집합은 $\left\{0, 1, 2, 3, 4\right\}$입니다.

숫자는 $10$개이므로 만들어질 수 있는 집합의 개수는 $2^{10} = 1\,024$개입니다.

이제 집합 두 개를 합쳐 크기가 $K$인 집합의 개수를 세면 됩니다.

만들어질 수 있는 $1\,024$개의 집합 중 $A\cup B$의 원소의 개수가 $K$개인 두 집합 $A$, $B$를 순서를 고려하지 않고 뽑습니다.

- $A=B$일 때는 정답에  $\mathrm{cnt}(A)\times \frac{\mathrm{cnt}(A)−1}{2}$를 더합니다.
- $A\neq B$일 때는 정답에 $\mathrm{cnt}(A) \times \mathrm{cnt}(B)$를 더합니다.

시간복잡도는 $\mathcal{O}(N + 1\,024^2 \times 10)$입니다.

우선 언제 `NO` 를 출력해야할 지 생각해봅니다. 아래 두 가지 규칙을 지키지 않는다면 `NO`를 출력해야 합니다.

- $\mathop{\mathrm{MEX}}$의 정의에 의해, 길이가 $N$인 순열의 $\mathop{\mathrm{MEX}}$는 $N+1$보다 클 수 없습니다. $A$는 순열이기 때문에 $B_N = N+1$입니다.
- $S_i = \left\{A_1, A_2, \cdots, A_i\right\}$라고 할 때, $S_i \subset S_{i+1}$이므로 $B_i > B_{i+1} \left(1 \leq i \leq N-1\right)$일 수 없습니다. 즉 $B$는 **단조증가**합니다.


몇 가지 관찰을 해 봅시다.

만약 $A_i = K$라면, $i\leq j$일 때 $B_j = K$일 수 없습니다. $K$를 포함하는 집합의 $\mathop{\mathrm{MEX}}$는 정의상 $K$일 수 없기 때문입니다.

결국 $B_j = K$일 때, $A_i = K (j<i)$입니다.

$B_i \neq B_{i+1} (1 \leq i \leq N-1)$인 경우에 주목합니다.

$\mathop{\mathrm{MEX}}$값이 $B_{i+1}$이기 위해서는 해당 집합이 $B_i$를 가지고 있어야 합니다.

이전 관찰과 종합하면 $B_i \neq B_{i+1}$일 때, $A_{i+1} = B_i$가 됨을 알 수 있습니다.

이제 남은 값을 배치하는 방법은 여러 가지가 있습니다. 그 중 하나는 작은 수부터 빈 곳에 채워 넣는 것입니다.

채워야 하는 곳은 $B_{i-1} = B_i$인 $A_i$입니다. 해당 방법으로 빈 곳을 배치하면 $B_i < A_i$입니다.

$\mathop{\mathrm{MEX}}$ 값이 $B_i$인 배열에 $B_i$보다 큰 값을 배치하더라도 $\mathop{\mathrm{MEX}}$ 값은 변하지 않습니다.

그리고 $B_{k-1} \neq B_k$인 $k$에 대해 총 $k$개의 공간에 $B_k$보다 작은 $B_k - 1 (\leq k)$개의 수를 배치하므로 작은 수부터 배치하면 원하는 결과를 얻을 수 있습니다.

시간복잡도는 $\mathcal{O}(N)$입니다.

상대적으로 오른쪽의 등불이 상승하는 정도가 더 크면, 왼쪽의 등불을 앞지르는 순간이 존재합니다.

길이가 $S$인 구간에서 $i<j$ 이면서 $A_i < A_j$인 $(i, j)$ 쌍의 개수를 구해야 합니다.

구간 내 원소에 대해서 모든 쌍을 찾는 방법을 먼저 생각해 봅시다. 하나의 구간에 대해 $\mathcal{O}(N^2)$이 걸리므로, 모든 구간에서 계산한다면 $\mathcal{O}(N^3)$으로 제한시간 내에 풀 수 없습니다.

문제의 특성을 파악해서 빠르게 풀어 봅시다.

$k$번 등불부터 $S$개 고른 구간을 $T_k$라고 합시다.

$T_k$ 구간과 $T_{k+1}$ 구간의 공통된 구간은 $[k+1, k+S-1]$입니다.

공통된 구간에서 발생하는 앞지르는 쌍의 개수는 $k$번째 등불과 $k+S$번째 등불에 영향받지 않습니다.

해당 구간의 연산을 매 구간마다 반복하지 않으면 효율적으로 풀 수 있습니다.

$T_k $구간에서 다음 구간으로 넘어갈 때 아래의 값들을 빼고 더해줘야 합니다.

- $k$ 번째 등불을 제거했을 때 감소하는 앞지르는 쌍의 개수
- $k+S$ 번째 등불을 추가할 때 증가하는 앞지르는 쌍의 개수

세그먼트 트리를 활용하면 앞지르는 쌍의 개수를 빠르게 구할 수 있습니다.

- $k$번째 등불을 제거할 때, $A_k$보다 상승하는 정도가 큰 등불의 개수
- $k+S$번째 등불을 추가할 때, $A_{k+S}$보다 상승하는 정도가 작은 등불의 개수

등불이 상승하는 정도는 최대 $10^9$이므로, 좌표 압축을 먼저 진행해야 합니다.

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

순회 후보가 여럿일 경우 작은 번호가 매겨진 정점부터 방문하므로, 우선 BFS의 순회 순서대로 정점에 번호를 매기겠습니다. 정점을 적절히 배치해서 두 순회에서의 방문 순서의 차의 합을 최대화해야 합니다.

루트 정점 바로 아래에 $k$개의 정점이 존재한다고 하고, 트리의 $i\left(1 \leq i \leq N\right)$번 정점을 루트로 하는 서브트리의 크기를 $S_i$라고 합시다.

$\sum_{i=2}^{k+1}$은 루트 노드를 제외한 트리의 크기이므로 $N-1$입니다.

$d_2=b_2=2$이고, $2<i\leq k+1$인 $i$에 대한 $d_i$와 $b_i$는 아래와 같습니다.
$$
\begin{aligned}
&d_i=\sum_{j=2}^{i-1}S_j+2\\
&b_i=i
\end{aligned}
$$

$$
\begin{aligned}
\sum_{i=2}^{k+1}|d_i-b_i|&= |2-2|+|S_2+2-3|+S_2+S_3+2-4|+\cdots \\
&+\left|\sum_{j=2}^{k}S_j+2-\left(k+1\right)\right|\\
&=|S_2-1|+|S_2+S+3-2|+\cdots+\left|\sum_{j=2}^{k}S_j-\left(k-1\right)\right|
\end{aligned}
$$

여기에서 서브트리의 크기는 $1$ 이상이므로, 절댓값 안쪽 식을 그대로 빼내 정리할 수 있습니다.

$$
\begin{aligned}
\sum_{i=2}^{k+1}|d_i-b_i|&=\left(S_2-1\right)+\left(S_2+S_3-2\right)+\cdots+\left(\sum_{j=2}^{k}S_j-\left(k-1\right)\right)\\
&=\left(k-1\right)S_2+\left(k-2\right)S_3+\cdots +S_k - \sum_{i=1}^{k-1}i
\end{aligned}
$$

위 식이 최대가 되도록 루트 아래의 정점의 크기를 배분하는 것은, $S_2=N-k$, 나머지는 모두 $1$이 되도록 하는 것입니다. $2$번 정점을 루트로 하는 서브트리에서 노드를 배치하는 형태는 정답에 영향을 미치지 않습니다.

이제 문제의 정답을 최대화하는 $k$값을 찾아 봅시다.

![Alt text](https://static.solved.ac/arena/editorial/10/bfsdfs.png)

순회 순서를 보면, $N-k-1$개에 해당하는 정점의 BFS 순서는 $k+1$씩 밀려납니다.

반대로, $k-1$개 정점의 DFS 순서는 $N-k+1$씩 밀려납니다.

따라서 $\left(k-1\right)\times\left(N-k+1\right)+\left(k+1\right)\times\left(N-k-1\right)$의 최댓값을 구해야 합니다.

문제에서 $N$이 주어지므로, 해당 식은 $k$에 대한 이차식입니다. 식을 전개하면 $-2k^2+2kN-2$이고 $k=\frac{N}{2}$인 경우 최대입니다.

직접 트리를 만든 뒤 $d_i$와 $b_i$를 순회를 통해 구할 수도 있고, 바로 답을 구한 뒤 위에서 언급한 대로 간선으로 연결된 두 정점을 출력해도 됩니다.

E번 〈팰린드롬 애너그램〉에서 보였듯, $N$이 짝수인 경우에는 항상 가능합니다.

홀수인 경우에는 중앙의 원소가 자신의 자리에 있을 때에만 가능합니다.

이제 각 수가 자신의 자리로 찾아가기 위한 최소 연산 횟수를 구해야 합니다.

![Alt text](https://static.solved.ac/arena/editorial/10/image-7.png)

다음과 같은 배열에서, 각 원소가 자신의 자리에 돌아가기 위해서 현재 칸으로부터 자신의 수 번째에 해당하는 칸으로 간선을 그어 봅시다.

이때, 배열에서 사이클을 분리해낼 수 있습니다. 사이클의 종류는 총 세 가지입니다.
- 왼쪽 절반의 원소로만 이루어진 사이클
- 오른쪽 절반의 원소로만 이루어진 사이클
- 양쪽 원소가 모두 포함된 사이클

각 사이클을 $L$, $R$, $M$ 사이클이라고 정의하겠습니다.

$L$ 사이클과 $R$ 사이클은 그 자체로 교환할 수 없습니다.

$M$ 사이클로 만든 뒤 정렬해야 합니다. 이때 $1$회 교환을 통해 원소가 한 개 늘어난 $M$ 사이클을 만들 수 있습니다.

하지만, $L$ 사이클과 $R$ 사이클이 모두 존재한다면, 두 사이클의 원소를 교환해 하나의 $M$ 사이클을 만들 수 있습니다. 이 경우, 각 사이클을 $M$ 사이클로 만들었을 때보다 교환을 $1$회 덜 하므로, 가능하다면 $L$, $R$ 사이클 간 교환을 통해 $M$ 사이클을 만드는 것이 이득입니다.

이제 $M$ 사이클을 올바르게 배치하는 데 필요한 연산의 횟수를 구해 봅시다.

크기가 $2$인 $M$ 사이클을 올바르게 배치하는 데에는 $1$번의 연산이 필요합니다.

크기가 $i$인 $M$ 사이클을 올바르게 배치하는 데 걸리는 연산 횟수가 $k$라고 합시다.

크기가 $i+1$인 $M$ 사이클을 올바르게 배치할 때, 세 가지의 원소를 동시에 교환할 수 없으므로, $1$번의 교환을 통해 크기가 $i$인 $M$ 사이클을 만드는 것이 최선입니다.

따라서 $i+1$개의 원소를 가지는 $M$ 사이클은 $k+1$번 연산을 통해 올바르게 배치할 수 있습니다.

$L$, $R$, $M$ 사이클의 개수를 각각 구해준 뒤, $L$, $R$ 사이클을 짝지어 $M$ 사이클로 만들어야 합니다.

남은 $L$ 또는 $R$ 사이클은 크기가 $1$ 증가한 $M$ 사이클이 됩니다.

기존 $M$ 사이클은 각 사이클의 원소 개수보다 $1$ 작은 횟수로 올바르게 배치할 수 있습니다.

$M$ 사이클을 구성하는 왼쪽/오른쪽 원소의 개수가 같은 쪽으로 가도록 교환하면 $M$
사이클을 유지하면서 크기를 $1$씩 줄여나갈 수 있습니다.

사이클의 개수, 종류, 구성하는 원소 등을 조합해 위에서 설명한 대로 답을 도출할 수 있습니다.

시간복잡도는 $\mathcal{O}(N)$입니다.