CCO23 day1

CCO는 캐나다 국대 선발전으로 퀄리티가 좋고 다른 국대 선발전보다 덜 매워서 재미있게 돌기에 좋은 셋이다.

 

1. Binaria

문제 요약: 정수 $K$가 주어진다. 길이 $N$의 binary string의 SMS(sub-message sum)을 다음과 같이 정의하자.

• SMS는 길이 $N-K+1$의 수열이다.
• SMS의 $i$번째 값은 binary string의 $i$번째부터 $i+K-1$번째 문자의 합이다.

$N$, $K$, 그리고 SMS가 주어졌을 때 가능한 binary string의 가짓수를 구하라. 가능한 binary string이 존재함이 보장된다.

Full task (25 points)

Binary string을 A, SMS를 B라고 하자.

SMS가 우리에게 주는 정보는 다음과 같다.

• $1 \leq i \leq N-K+1$인 $i$에 대해서 $A_i + A_{i+1} + \cdots + A_{i+K-1} = B_i$

우리는 이 정보를 다음과 같이 변형할 수 있다.

• $A_1 + A_2 + \cdots +A_K = B_1$
• $1 \leq i \leq N-K$인 $i$에 대해서 $A_{i+K}-A_i = B_{i+1}-B_i$

2번째 조건만을 사용해서 정리를 해보자. $A_i$가 정해진다면 $i \equiv j \pmod{K}$인 모든 $j$에 대해서도 $A_j$가 정해진다. 따라서 $1 \leq i \leq K$의 $i$에 대해서 $A_i$가 정해진다면 $A$ 전체가 정해진다. 그리고 $B_{i+1}-B{i} \neq 0$인 경우에는 $A_{i+K}$와 $A_i$가 정해지고, $A_{i mod K}$도 정해진다. (인덱스가 1에서 시작하기 때문에 정확히는 $(i-1) mod K +1$이다)

2번째 조건으로 알 수 있는 값들을 알아냈다고 하자. $1 \leq i \leq K$ 중에 $A_i$의 값을 알아낸 경우가 $p$개이고 그 중에 $A_i=1$인 $i$ 개수가 $q$개라고 하자. 1번 조건은 $K-p$개의 $0$ 또는 $1$인 값들의 합이 $B_1 - q$인 식과 같아진다. 따라서 정답은 $\binom{K-p}{B_1-q}$ 가 된다.

 

이와 같이 여러 식을 주고 가능한 해를 구하는 문제는 OI에 여러 번 출제되었으며, 예시로는 2021 KOI 고등 2번, https://www.acmicpc.net/problem/27492 , https://www.acmicpc.net/problem/28439가 있다.

 

2. Real mountains

문제 요약: 길이 $N$의 수열 $h$가 주어진다. 산 수열이란, 어떤 $p$가 존재해서 $h_1 < h_2 < \cdots < h_p > h_{p+1} > \cdots > h_N $를 만족하는 수열을 의미한다. 우리는 $i < j < k$이고 $h_i > h_j < h_k$를 만족하는 $(i, j, k)$ 쌍에 대해서 $h_j$를 $1$ 증가시키는 비용 $h_i+h_j+h_k$의 시행을 할 수 있다. 산 수열을 만들기 위한 최소 비용을 mod $10^6+3$으로 구하시오.

Full task (25 points)

Claim 1) 최종적인 산 수열은 정해져 있다.

pf) 임의의 위치 $i$에 대해서 $i$의 왼쪽에 있는 수열 값의 최대 높이 ($max(h_1, h_2, \cdots, h_{i-1}$)는 변하지 않는다. $j<i$인 $j$의 높이를 시행 $(k_1, j, k_2)$를 통해 1 증가시켰다고 생각해보자. $k_1 < j < i$이고 $h_{k_1} \geq h_j + 1$이기 때문에 $h_j$가 $1$ 늘어나도 $i$의 왼쪽에 있는 수열 값의 최대 높이는 안 변하지 않는다.

마찬가지로 $i$의 오른쪽에 있는 수열 값의 최대 높이도 변하지 않는다. 따라서 시행을 통해서 $i$번째 값을 최대 $max(h_i, min(max(h_1, \cdots, h_{i-1}), max(h_{i+1}, \cdots, h_N)))$까지 증가시킬 수 있고, 이는 산 수열을 만들기 위해서 필요한 최소 값이므로 최종 산 수열은 정해져 있다.

 

이를 통해서 $h_i + h_j + h_k$에서 $h_j$ 부분의 합은 항상 동일함을 알 수 있다. 이를 미리 계산해두고 $h_i + h_k$의 합을 최소화 해보자.

 

Claim 2) 시행을 할 때에는 가장 작은 원소부터 먼저 증가시키는 것이 좋다.

pf) 시행을 한 순서를 $(i_1, j_1, k_1), (i_2, j_2, k_2), \cdots, (i_p, j_p, k_p)$ 라고 하자. $j_q \neq j_{q+1}$이고 $h_{j_q} > h_{j_{q+1}}$이라고 가정하자. 높이 조건에 의해 두 시행의 순서를 바꿔도 되고, 이러한 경우에 시행의 비용의 총합이 감소하거나 같다. (자세한 설명 생략)

 

따라서 가장 크기가 작은 수부터 차례대로 올리면 된다. 이제 같은 값을 가지는 원소 여러 개를 증가시키는 경우에 대해서 생각해보자.

 

값이 $p$인 원소 $i_1, i_2, \cdots i_d$를 모두 $p+1$로 증가시킨다고 생각하자. $d=1$인 경우에는 최소 비용이 자명하다.

$d \geq 2$인 경우에 대해서 생각해보자. $i_1$을 증가시킬 때는 반드시 $i_1$의 왼쪽에 자신보다 큰 원소를 골라서 시행을 해야 한다. $(i, j=i_1, k)$ 시행을 하는 경우 $h_i+h_k$ 만큼의 비용을 내야 하는데, $h_i$ 부분에서 $i_1$의 왼쪽에 있고 $p$ 초과의 원소들 중 최솟값 만큼의 비용이 든다. 그 원소의 위치를 $x$라고 하자. $i_d$의 경우에도 $h_k$ 부분에서 $i_d$의 오른쪽에 있고 $p$ 초과의 원소들 중 최솟값 만큼의 비용이 들고, 이 원소의 위치를 $y$라고 하자. 그리고 $p$ 초과의 원소들 중 최솟값의 위치를 $z$라고 하자.

편의상 $z$가 $i_1$의 오른쪽에 있다고 가정하자. $i_1$의 왼쪽에 있는 경우에는 좌우반전을 시켜서 똑같은 방법으로 해주면 된다. 첫 시행으로는 $(x, i_1, z)$를 선택해서 $i_1$의 값을 1 증가시킨다. 이 때 비용은 $h_x+h_z$ 만큼 든다. 그 다음에는 $(i_1, i_d, y)$를 선택해서 $i_d$의 값을 1 증가시킨다. 이 때 비용은 $p+1+h_y$이다. $i_1$과 $i_d$ 사이에 있는 원소 $i_j$는 $(i_1, i_j, i_d)$의 선택으로 비용이 $2p+2$가 된다. 이를 모두 합쳐주면 된다.

 

$i_1, i_2, \cdots i_d$를 std::set으로 관리하고 $x, y, z$를 segment tree로 구해주면 $O(NlogN)$에 문제를 해결할 수 있다.

3. Line town

문제 요약: 이웃한 두 원소에 $-1$을 곱한 후에 swap을 하는 시행을 할 수 있다. 최소 횟수의 시행을 통해서 주어진 수열을 정렬하시오. 수열을 정렬하지 못하는 경우에는 $-1$을 출력한다.

 

정렬이 된 최종 상태를 구한 뒤에 inversion의 개수를 최소화하는 방향으로 생각을 해보자. inversion이란, 기존 수열과 순서가 바뀐 쌍의 개수이며, 정렬을 위해 필요한 swap의 개수는 inversion의 개수와 동일하다는 것은 잘 알려져 있다. 

Subtask 5, 6 (7 points)

이 서브태스크는 모든 원소의 절댓값의 크기가 다르다는 것이다. 

 

주어진 수열을 절댓값 순서대로 정렬했을 때 $A_1, A_2, \cdots A_n$이 된다고 하자. 함수 $f(x, y) = $ $x$와 $y$가 inversion을 이루는 경우에 $1$, 아닌 경우에는 $0$으로 정의했을 때 총 inversion의 개수는 $\sum_{i=1}^{n} \sum_{j=1}^{i-1} f(A_i, A_j)$로 정리할 수 있다.

 

절댓값이 가장 큰 원소 $A_n$ 부터 보자. 절댓값이 가장 큰 원소는 가장 오른쪽이나 가장 왼쪽에 가게 된다. 절댓값이 가장 큰 원소를 오른쪽 / 왼쪽으로 보낼 수 있는지를 알아보고 ($-1$이 곱해져서 가장 오른쪽으로 갔는데 음수인 경우는 제외해야 한다) 각 경우에 대해서 $A_n$과 다른 수 사이의 inversion의 개수 ($\sum_{j=1}^{n-1} f(A_n, A_j)$)를 구할 수 있다. 

 

절댓값이 일정 값 이하인 원소들은 최종 정렬된 수열에서 구간을 이루게 된다. 구간의 시작의 홀짝성만 같다면 $A_1, A_2, \cdots A_i$를 같은 순서로 정렬했을 때 같은 최종 결과를 보이게 된다. 따라서 구간의 시작의 홀짝성만 중요하다. 따라서 $dp[i][j] = A_1, A_2, \cdots A_i$를 시작이 $j mod 2$인 구간에 배열할 경우에 필요한 inversion의 최소 개수로 생각하자. $dp[i][j] = min(A_i$를 오른쪽으로 보내는 경우의 inversion 개수 $ + dp[i-1][j], A_i$를 왼쪽으로 보내는 경우의 inversion 개수 $+ dp[i-1][j \oplus 1]$가 된다. 위에서 말했듯이 오른쪽 / 왼쪽으로 보내지 않는 경우에는 케이스를 제외해주어야 한다. $dp$를 통해서 시간복잡도 $O(nlogn)$에 문제를 해결할 수 있다.

Full task (25 points)

이번에는 절댓값이 같은 원소가 여러 개 있을 수 있다. 절댓값이 $X$로 가장 큰 원소가 $p$개 있다고 하자. 절댓값이 가장 큰 원소 중에 몇 개는 왼쪽으로, 몇 개는 오른쪽으로 보내게 된다. 왼쪽으로 $k$개 보내고 오른쪽으로 $p-k$개 보내는 경우에는 절댓값이 $X$인 원소 사이의 inversion과 절댓값이 $X$인 원소와 절댓값이 $X$보다 작은 원소 사이의 inversion을 세어주어야 한다. sweeping과 segment tree를 사용한 inversion counting을 한다면 모든 $k$에 대해서 $O(logn)$에 inversion의 개수를 구할 수 있다. 위와 똑같은 형식의 dp를 사용해준다면 시간복잡도 $O(nlogn)$에 문제를 해결할 수 있다. inversion을 세어주는 것의 구현이 상당히 까다롭다.

 

참고할만한 에디토리얼은 다음이 있다.

https://dmoj.ca/problem/cco23p3/editorial