IOI 2018 Problem 6. 모임들 (Meetings)

IOI 2018 Day 2 풀이를 작성할 당시 Meetings 문제를 해결하지 못해서, "36점 초과의 풀이는 작성 중입니다" 라고 하고 풀이를 비워두었다. IOI 2024 참관을 위해 알렉산드리아로 가는 비행기에서 드디어 100점 풀이 작성을 완성했다. 원래 글을 끌어올리기에는 시간순 정렬을 너무 깨는 것 같아서 개별 글에 작성한다.

Problem

길이 $N$의 양의 정수 배열 $A_0, A_1, \cdots A_{N-1}$ 이 있다. $0 \leq L \leq v \leq R < N$ 를 만족하는 세 정수 $L, R, v$에 대해서, 당신은 $Cost(L, R, v)$ 를 다음과 같이 정의한다.

• $Cost(L, R, v) = \sum_{i = L}^{v-1}{(Max_{j=i}^{v}(A_j))} + \sum_{i = v}^{R}{(Max_{j=v}^{i}(A_j))}$

$Q$ 개의 질의가 주어진다. 질의로 $L, R$이 주어질 때, 당신은 $f(L, R) = Min_{v=L}^{R}(Cost(L, R, v))$ 를 반환해야 한다. 질의는 하나의 함수로 각각 주어지는 것이 아니고, 한꺼번에 주어진다. 즉, 오프라인 풀이가 가능하다.

Solution

$O(QN^2)$ (4점)

$v$를 기준으로 왼쪽으로 가면서 지금까지 만난 최댓값을 기록해놓고, 오른쪽도 비슷하게 훑으면 $Cost(L, R, v)$ 를 $O(N)$에 계산할 수 있다. 이를 모든 $L \leq v \leq R$ 에 대해서 계산하면 쿼리당 $O(N^2)$ 이 된다.

$O(N^2 + NQ)$ (19점)

쿼리 당 $O(N)$ 의 시간을 쓸 수 있으니 $v$를 다 순회할 수는 있다. 고로, 왼쪽 / 오른쪽의 Max 합들을 $O(1)$ 정도에 알아내면 된다.

이는 간단한 전처리로 가능하다. $DL_{i, j} = (i$ 에서 $j$까지의 왼쪽으로 갔을 때의 최댓값 합) 이라고 정의하고, $DR_{i, j}$ 도 반대로 비슷하게 정의하자. 그렇다면, 답은 $DL_{v, L} + DR_{v, R}$ 의 최솟값이 될 것이다. $DL$ 을 $N^2$ 에 계산하는 것은 간단하다. $i$ 를 고정하고, 현재까지의 최댓값을 기록하면서 $j = i, i - 1, \ldots$ 순서대로 채워주면 된다. $DR$ 도 동일하게 가능하다.

시간 복잡도는 전처리 $O(N^2)$, 쿼리당 $O(N)$ 으로 $O(N^2 + NQ)$ 이다.

$H = 2$ (36점)

$H = 2$ 이기 때문에 특수한 케이스에 대해서만 효율적으로 처리해 주면 된다. 구간 $[L,R]$이 주어졌을 때, 어떠한 위치에 모임을 잡았을 때의 cost의 경우는 다음과 같이 나뉜다.

• Case 1. $A_i = 2$ 인 곳에서 만남: 답은 $2(R-L+1)$이다.
• Case 2. $A_i = 1$ 인 곳에서 만남: $i$를 포함하는, 1로만 이루어진 연속한 구간의 길이를 $X$라고 하자. 이 구간에 있는 위치만 비용 1로 움직일 수 있고 나머지는 전부 비용 2가 필요하다. 답은 $2(R-L+1) - X$이다.

최대 $X$를 알면 답을 알 수 있으니. 문제는 다음과 같은 구간 쿼리 문제로 환원된다.

• 구간 $[L, R]$이 주어졌을 때, 해당 구간 안에 포함되는 1로만 이루어진 연속한 구간의 최대 길이를 계산하라.

이는 Segment Tree로 해결할 수 있다. 각 노드에 대해서 다음 값을 저장하면 된다:

• 구간의 길이
• 1로만 이루어진 최대 길이 prefix
• 1로만 이루어진 최대 길이 suffix
• 해당 구간에 대한 답

시간 복잡도는 $O(N + Q\log N)$ 이다.

$H \le 20$ (60점)

쿼리 구간 $[L, R]$ 에 대해서 구간의 최댓값이 $m \in [L, R]$ 에 위치한다고 하자. 배정한 모임 장소와 $m$ 의 대소관계에 따라 답은 다음과 같이 결정된다:

• 모임 장소의 위치가 $m$ 미만일 경우, 답은 $f(L, m - 1) +A[m] (R-m+1)$ 이다.
• 모임 장소의 위치가 $m$ 이라고 할 경우 답은 $A[m](R-L+1)$ 이다.
• 모임 장소의 위치가 $m$ 초과일 경우, 답은 $A[m](m-L+1) + f(m+1, R)$ 이다.

이 재귀적 관계를 단순히 구현하면 재귀 호출이 쿼리당 $O(N)$ 번 일어나기 때문에 기존 알고리즘에 비해서 특별히 효율적이지 않다. 60점 풀이에서는 $H \le 20$ 인 점을 사용하여, 쿼리당 $O(H)$ 번의 재귀 호출만을 사용하여 문제를 해결하려고 해보자.

쿼리 구간 $[L, R]$ 에 대해서 구간의 최댓값을 $H$ 라 하고, 이 최댓값의 등장 위치를 ${m_1, m_2, \ldots, m_k}$ 로 표시하자. 배정한 모임 장소와 $m_i$ 의 대소관계에 따라 답은 다음과 같이 결정된다:

• 모임 장소의 위치가 $m_1$ 미만일 경우, 답은 $f(L, m_1 - 1) +H(R-m_1+1)$ 이다.
• 모임 장소의 위치가 $m_i$ 이상 $m_{i+1}$ 이하일 경우, 답은 $H(m_i - L) + f(m_i, m_{i+1}) + H(R - m_{i+1})$ 이다.
• 모임 장소의 위치가 $m_k$ 초과일 경우, 답은 $H(m-L+1) + f(m_k+1, R)$ 이다.

모든 $[m_i, m_{i+1}]$ 쿼리 구간에 대한 답 $f(m_i, m_{i+1})$ 을 모두 빠르게 전처리할 수 있다고 하고 (실제로 그렇다) 이 부분문제만 해결해 보자. 이 부분문제는 $O(\log N)$ 내지는 $O(\log N + H)$ 정도에 해결할 수 있다. $H \le 20$ 이니, $occL(H, pos) = (A[i] = h, i \le pos$ 인 최대 $i)$, $occR(H, pos) = (A[i] = h, i \geq pos$ 인 최소 $i)$ 와 같은 전처리를 하면 $H, m_1, m_k$ 를 모두 계산할 수 있다. 또한, $f(m_i, m_{i+1}) + H(m_i - m_{i+1})$ 을 구간 최솟값 자료구조에 전처리해두면, 모임 장소의 위치가 $m_1$ 이상 $m_k$ 이하인 케이스의 최솟값을 한번의 구간 최솟값 쿼리로 계산할 수 있다.

아쉽게도 이것으로는 문제를 해결하는 데 부족하다. 각 높이에서 분기가 $2$ 개씩 이루어져 재귀 호출이 쿼리당 $O(2^H)$ 번 일어나기 때문이다. 조금 전처리를 더 하면 더 낮은 재귀 호출에서는 분기를 단 $1$ 개만 만들어도 됨을 알 수 있다. 모임 장소의 위치가 $m_k$ 초과인 분기 $f(m_k + 1, R)$ 를 호출하였고, 그 분기에서의 최댓값이 $l_1, l_2, \ldots$ 였다고 하자. 그 안에서 호출되게 될 분기 중 하나는 $f(m_k+1, l_1 - 1)$ 이 될 텐데, 이는 $f(m_k, l_1)$ 을 전처리하면 호출할 필요가 없어진다. $m_1$ 미만에 대해서도 대칭적으로 동일하게 전처리해주면 된다. 이렇게 하면 첫 높이 외에는 분기가 $1$ 개만 이루어지기 때문에 $O(H)$ 번의 재귀 호출을 사용하고, 쿼리 시간 복잡도는 $O(H \log N)$ 이 된다.

이제 전처리해야 할 함수들이 무엇인지를 확인해 보자:

• $A[i] = A[j]$ 이고, $i+1, \ldots, j-1$ 사이 높이가 모두 $A[i] (=A[j])$ 미만인 케이스에 대해서 $f(i, j)$
• $A[i] > A[j]$ 이고, $i+1, \ldots, j-1$ 사이 높이가 모두 $A[j]$ 미만인 케이스에 대해서 $f(i, j)$
• $A[i] < A[j]$ 이고, $i+1, \ldots, j-1$ 사이 높이가 모두 $A[i]$ 미만인 케이스에 대해서 $f(i, j)$

다시 말해:

• $i + 1, \ldots, j-1$ 사이 높이가 모두 $\min(A[i], A[j])$ 미만인 케이스에 대해서 $f(i, j)$

이러한 $(i, j)$ 쌍은 많아야 $O(N)$ 개이다. 일반성을 잃지 않고 $A[i] \le A[j]$ 라고 할 때 $i$ 에 대해서 대응될 수 있는 $j$ 가 단 1개이기 때문이다. 식의 계산은 동적 계획법으로 할 수 있다. $i+1, \ldots, j-1$ 사이 높이 중 최댓값들을 $m_1, \ldots, m_k$라고 하면, 위와 비슷한 점화식을 얻을 수 있는데, 이 때의 subproblem들이 모두 전처리해야 할 함수에 속하기 때문에 단순히 호출해 주면 된다. subproblem의 dependency가 트리 구조를 이루기 때문에, 구간 쿼리 없이 단순 호출로 $O(N)$ 시간에 필요한 값을 모두 계산해 줄 수 있다.

만점 풀이

만점을 받기 위해서는 전체 문제를 $O((N + Q) \log N)$ 에 해결해야 한다. 내 접근 방향은 정해와는 조금 다르다. 정해는 공식 해설이나 다음 사이트 에서 찾을 수 있고, 이 글에서는 내가 찾은 접근 방향을 설명한다.

편의상 모든 $A[i]$ 가 서로 다르다고 가정하자. 또한, 60점 풀이와 동일하게, $i + 1, \ldots, j-1$ 사이 높이가 모두 $\min(A[i], A[j])$ 미만인 케이스에 대해서 $f(i, j)$ 를 모두 전처리하자. 60점 풀이와 동일한 점화식을 사용하여 계산할 수 있으며, 구간 최댓값을 세그먼트 트리로 구하는 식으로 $O(n \log n)$ 시간에 계산하거나 혹은 스택을 사용하여 Cartesian Tree를 구성하는 식으로 $O(n)$ 시간에 계산할 수 있다.

$maxpos(L, R)$ 을 구간 $[L, R]$ 의 최댓값의 위치 로 정의하자 (즉 $L \le maxpos(L, R) \le R$). 또한, 구간 $[L, R]$ 에 대해 배정할 모임 장소가 $x \in [m, R]$ 구간에 위치한다고 가정하자. ($[L, m]$ 구간에 위치하는 경우는 대칭적이니 똑같이 처리하면 된다). 위에서 사용한 점화식을 단계적으로 풀면 다음과 같은 식을 얻는다:

• 모임 장소의 위치가 $m_0 = m$ 이라고 할 경우 답은 $A[m](R-L+1)$ 이다.
• 모임 장소의 위치가 $m_0 = m$ 초과이고, $m_1 = maxpos(m+1, R)$ 이하일 경우 답은 $A[m](m-L+1) + f(m_0, m_1) - A[m_0] + A[m_1](R-m_1)$ 이다.
• 모임 장소의 위치가 $m_1$ 초과이고, $m_2 = maxpos(m_1+1, R)$ 이하일 경우 답은 $A[m_0](m_0-L+1) + A[m_1] (m_1 - m_0) + f(m_1, m_2) - A[m_1] + A[m_2](R-m_2)$ 이다.
• 모임 장소의 위치가 $m_2$ 초과이고, $m_3 = maxpos(m_2+1, R)$ 이하일 경우 답은 $A[m_0](m_0-L+1) + A[m_1] (m_1 - m_0) + A[m_2] (m_2 - m_1) + f(m_2, m_3) - A[m_2] + A[m_3](R-m_3)$ 이다.
• ...

$l(i)$ 를, $j < i, A[j] > A[i]$ 를 만족하는 최대 $j$ 라고 정의하면, $l(m_i) = m_{i-1}$ 을 만족한다. ${m_0 = m, m_1, \ldots, m_k = R}$ 이라고 하자. 위 식에 따라서 우리는 다음 값을 구해야 한다:
$A[m_0] (m_0 - L + 1) + \min_{i = 0}^{k-1} (f(m_i, m_{i+1}) - A[m_i] + A[m_{i+1}](R - m_{i+1})) + \sum_{j = 1}^{i} A[m_j](m_j - m_{j-1}))$
$i$ 의 부모를 $l(i)$ 로 하는 트리를 만들고, 다음과 같은 함수를 정의한다:

• $g(x) = g(l(x)) + A[x](x - l(x))$
• $h(x) = f(l(x), x) - A[l(x)]$

우리는 이 트리에서 $R \rightarrow m$ 으로 가는 경로 ($R$ 포함, $m$ 제외) 에서 다음 값의 최소를 계산하고 싶다:
$A[m](m-L+1) + \min_{v \in Path[R, m)} (h(v) + A[v](R - v) + g(v) - g(m))$

이는 트리 상에서 일차함수의 최솟값을 계산하는 것과 동일하다.

가장 단순한 방법은 $O(N \log N)$ 초기화 후 쿼리 당 $O(\log^3 N)$ 시간이 걸린다. 직선에서 이 문제를 해결하는 방법은 세그먼트 트리에 CHT를 사용하는 것이다. 세그먼트 트리의 각 노드에 대해, 구간에 있는 일차함수들의 CHT를 저장한다. 이후 각 쿼리에 대해서 대응되는 $O(\log N)$ 개의 노드들에 대해서 최솟값을 CHT 상 이분 탐색으로 계산하면 문제가 쿼리당 $O(\log^2 N)$ 시간에 해결된다. 이 문제는 직선이 아니라 트리이지만, HLD를 사용하여 트리를 $O(\log N)$ 개의 체인으로 분해하면 같은 방법을 사용하여 쿼리 당 $O(\log^3 N)$ 시간에 해결할 수 있다.

$O(\log N)$ 을 줄이는 관찰 하나는, HLD를 사용하여 쿼리를 할 경우 하나의 체인을 제외한 모든 체인에서 prefix query를 한다는 점이다. 경로를 $O(\log N)$ 개의 체인 상 구간으로 분해할 경우, 가장 루트에 가까운 체인 상 구간을 제외한 모든 구간은 체인의 가장 높은 점을 포함한다. 고로 각 쿼리는 1개의 체인에 대해서 range query, 그 외 $O(\log N)$ 개의 체인에 대해서 prefix query를 하는 것이 된다.

Range query는 앞과 동일하게 세그먼트 트리에 CHT를 저장하는 방식으로 쿼리당 $O(\log^2 N)$ 에 할 수 있다. Prefix query를 할 때 관찰할 것은, 체인을 위에서부터 아래로 읽을 경우 우리가 보는 직선의 기울기가 감소한다 ($l(v)$ 의 높이가 $v$ 보다 크기 때문). 고로 이 CHT에 삽입하는 것은 단순 스택을 사용하여 할 수 있다. 이렇게 되면 각 체인에서 스위핑을 할 수 있다. 체인에 일차 함수를 삽입하면서 모든 prefix를 한번씩 구성해 보고, 현재 prefix에 대한 쿼리가 있을 경우 이를 CHT에 대해서 이분탐색 해서 찾으면 된다. 이렇게 하면 각 체인 당 이분 탐색의 $O(\log N)$ 시간이 들기 때문에 $O(N \log N)$ 초기화 후 쿼리 당 $O(\log^2 N)$ 시간이 걸린다. 아마 이걸로도 통과하기 충분할 것이라고 생각된다.

$O((N + Q) \log N)$ 복잡도를 얻기 위해서는 Range Query와 Prefix Query의 $O(\log N)$ 을 각각 떼어야 한다. Range Query의 $O(\log N)$ 은 떼기 어렵지 않다. 쿼리들을 모두 $x$ 좌표가 증가하는 순으로 정렬하면, 세그먼트 트리에서 이분탐색 없이 amortized $O(1)$ 시간에 각 CHT를 쿼리할 수 있다. 고로 Range Query 하나가 amortized $O(\log N)$ 시간에 해결된다. Prefix Query가 $O(\log^2 N)$ 시간을 필요로 하여 전체 복잡도는 $O(N \log N + Q \log^2 N)$ 이지만, 이 정도 최적화로도 이미 대부분의 온라인 저지에서 정해보다 빠르게 작동한다.

Prefix Query의 $O(\log N)$ 을 떼려면 조금 더 세심한 관찰과 구현이 필요하다. $R \rightarrow m$ 으로 가는 경로에 대한 CHT 쿼리의 $x$ 좌표는 $R$ 이 된다. 한 CHT 체인을 위에서부터 아래로 읽을 경우, 쿼리 중 해당 체인 아래 ($x$ 좌표 작은 쪽) 에 있는 쿼리들은 묻는 $x$ 좌표가 단조 증가하게 배치되고, 위 ($x$ 좌표 큰 쪽) 에 있는 쿼리들은 묻는 $x$ 좌표가 단조 감소하게 배치된다. 단조 증가하게 배치되는 쿼리들만 존재할 경우 Queue를 사용하여 앞의 중요하지 않은 직선들을 제거하는 식으로 amortized $O(1)$ 시간에 해결할 수 있듯이, 단조 증가와 감소가 번갈아서 배치되는 쿼리들은 Deque를 사용하여 앞과 뒤의 중요하지 않은 직선들을 제거하는 식으로 amortized $O(1)$ 시간에 해결할 수 있다. 고로 문제를 총 $O((N + Q) \log N)$ 시간에 문제를 해결할 수 있으며, 실제 수행 시간은 위에서 설명한 $O(N \log N + Q \log^2 N)$ 와 차이가 나지 않거나 오히려 더 느리다.

나의 소스 코드