RUN@KAIST 8/23 방학 연습 풀이

1. 공간을 만들어 봅시다

미팅 공간을 잡는다는 것은, 미팅 공간의 왼쪽과 오른쪽 경계 파티션을 잡는다는 것이다. 0과 W를 포함한 모든 파티션의 쌍을 돌면서, 해당 파티션 쌍 사이에 생기는 공간의 크기는, 가능한 미팅 공간 크기라고 체크하면 된다.

2. Unique Encryption Keys

어떠한 구간에 대해서 수들이 다 unique하다는 것은, 그 수와 같은 값을 가지는 수들이 (자신을 제외하고는) 해당 구간에 존재하지 않는다는 것을 뜻한다. 구간 $[S, E]$에 있는 수가 unique한지를 보려면, 그 수와 가장 가까운 두 수 (왼쪽 / 오른쪽) 을 본 후, 이것이 $[S, E]$ 구간 안에 있는지를 보면 된다.

이 풀이를 조금 더 정리하면 다음과 같다. $prev[i]$ 를 $i$의 왼쪽에 있으며, $A_i = A_{prev[i]}$ 이고, 가장 가까운 수라고 하자 (없으면 -inf). 구간 $[S, E]$ 에 대해서 $prev[i] < S$를 모두 만족해야 함을 알 수 있다. $next[i]$ 도 유사하게 정의하면, 구간 $[S, E]$ 에 대해서 $next[i] > E$를 모두 만족해야 한다. 즉, $prev[S], prev[S+1], \cdots, prev[E]$ 중 최댓값이 $S$ 이상이면 안되며, $next[S], next[S+1], \cdots, next[E]$ 중 최솟값이 $E$ 이하면 안된다. 이는 구간 최대 / 최솟값 문제이니 세그먼트 트리를 사용하면 된다.

Unique하지 않을 때는 그러한 수를 하나 찍어야 한다. 최솟값이나 최댓값이 위 조건 중 하나를 만족하지 않았다는 것이니, 세그먼트 트리에서 최대 / 최솟값을 가지는 원소가 무엇인지를 알면 그러한 수를 찍을 수 있다.

3. 두 수열

첫번째로, 식이 $(S1 - K1)(S2 - K2)$와 같은 복잡한 꼴을 띄고 있는데, 먼저 이를 $S1 * S2$의 형태로 간단화시킬 수 있다. 주어지는 모든 수에서 1을 빼면 그것의 합이 $(S1 - K1)(S2 - K2)$가 될 것이기 때문이다. 고로 우리는 $S1 * S2$의 합을 최소화해야 한다.

이제 간단한 동적 계획법을 세울 수 있다. $DP[i][j] = $ (첫번째 수열의 $[1, i]$ 구간이 남아있고 두번째 수열의 $[1, j]$ 구간이 남았을 때의 최소 비용) 이라고 하면, $DP[n][m]$ 이 우리가 구하는 답이다. 각 수열의 부분합을 구해두면 이는 간단히 $O(N^2M^2)$ 에 구할 수 있으나, 시간 복잡도가 문제이다.

여기서 한가지 관찰을 할 수가 있는데, 바로 각 스텝에서 수열의 suffix를 제거할 때, 두 suffix 중 최소 하나는 길이가 1일 것이라는 게 관찰이다. 만약에 두 suffix S1, S2가 모두 길이가 2 이상이라고 하자. 그렇다면, 두 suffix를 모두 두개의 연속 구간으로 쪼갤 수 있다. ($S1 = A + B, S2 = C + D$). 자명히 $(A+B)(C+D) \geq AC + BD$ 이기 때문에, 이런 식으로 계속 suffix를 쪼개가다 보면 결국 제거하는 suffix 중 둘 중 하나가 길이 1이 되도록 할 수 있다. 이렇게 되면 한 쪽의 길이를 1로 고정시켰을 때, 나머지 하나의 길이를 바꿔가면서 문제를 해결할 수 있다. 시간 복잡도가 $O(NM(N+M))$으로 줄었다.

이를 $O(NM)$에 줄이는 것은 prefix minimum을 관리하는 방식이다. 편의 상 첫번째 수열의 길이를 1로 고정하자 (반대는 똑같이 하면 된다.) 주어진 수열이 $A, B$이고 그의 부분합이 $SA, SB$라면, $DP[i][j] = min(DP[i-1][k] + A_i * (SB_j - SB_k))$ 의 형태를 띈다. 모든 $k < j$ 중, $DP[i-1][k] - A_i * SB_k$의 최솟값을 가지고 있어야 하는데, 이는 $i, j$에만 영향을 받으니, $pref[i][j]$를 모든 $k < j$ 중 $DP[i-1][k] - A_i * SB_k$의 최솟값으로 저장하면 된다. $pref[i][j]$ 하나를 계산하는 데 $O(1)$ 이니 전체 문제가 $O(NM)$에 해결된다.

4. Rubik's Rectangle

준비중