Movatterモバイル変換

안녕하세요. 이 글에서는 IOI 2016에 출제된Aliens 문제 풀이를 설명해보려고 합니다. 하나의 글 안에서 풀이 전체를 설명하는 것이 목표입니다.

풀이에 앞서 먼저 이 문제를 요약해보겠습니다. 왼쪽 그림과 같이 한 변의 길이가 m인 정사각형 격자가 주어지고, 그 안에 있는 n개의 점이 주어집니다. 정사각형으로 n개의 점을 모두 덮는 게 목표입니다. 이때, 정사각형은 가운데 그림에서 보는 것과 같이 왼쪽 위와 오른쪽 아래가 모두 대각선 위에 있어야 합니다. 정사각형은 서로 겹칠 수 있으며, 겹치는 영역은 한 번만 덮은 것으로 간주합니다. 같은 칸에 2개 이상의 점이 있다고 해도 한 번만 덮으면 충분합니다. 정사각형은 최대 k개만 사용할 수 있습니다. 우리는 덮은 칸의 개수를 최소화하고 그 개수를 출력해야 합니다.

풀이는 두 가지 부분으로 나눠서 설명하겠습니다.

• 첫 번째 부분에서는 사용할 수 있는 정사각형의 개수 상한 k가 없을 때에 한해 문제를 해결합니다.
• 두 번째 부분에서는 첫 번째 부분의 결과를 이용해 어떻게 k를 반영한 답을 구할 수 있는지 설명합니다.

• 정사각형의 두 꼭짓점이 대각선 위에 있어야 하므로, 그 좌표를 각각 (a, a)와 (b, b)라고 합시다(a <= b). 그러면 이 정사각형은 두 좌표가 모두 a 이상 b 이하인 모든 점을 덮고, 그 이외의 점은 덮지 않습니다. 이를 앞으로 "정사각형 (a, a) - (b, b)"라고 쓰겠습니다.
• 만약 좌표 (r, c)에 점이 있다면, 일반성을 잃지 않고 r <= c라고 가정할 수 있습니다. 왜냐면 (r, c)를 덮는 정사각형은 항상 (c, r)도 덮고, 반대로 (c, r)을 덮는 정사각형은 (r, c)도 덮으므로 이 가정이 문제의 답을 바꾸지 않기 때문입니다.
• 정사각형 (a, a) - (b, b)가 점 (r, c)를 덮는다면, a <= r <= c <= b가 성립합니다. 따라서, 어떤 점 (r', c')이 존재하여 r <= r' <= c' <= c를 만족한다면, 점 (r, c)를 덮는 모든 정사각형이 (r', c')를 덮습니다. 따라서, (r', c')를 제거해도 문제의 답이 바뀌지 않습니다.
• 이상의 논의로부터, 주어진 점을 답을 바꾸지 않으면서 전처리하고 정렬하여 r과 c가 모두 증가(strictly increasing)하도록 할 수 있음을 알 수 있습니다. 이를 순서대로 (r_1, c_1), ..., (r_n, c_n)이라고 하겠습니다. (단, 여기서 n은 전처리 이후의 점의 개수를 의미하며, 입력으로 주어진 n과 다를 수 있습니다.)

• 만약 어떤 i < j < k에 대해 정사각형 (a, a) - (b, b)가 (r_i, c_i)와 (r_k, c_k)를 모두 커버한다면, a <= r_i <= r_j <= r_k <= b 및 a <= c_i <= c_j <= c_k <= b로부터 해당 정사각형이 (r_j, c_j)도 커버합니다. 따라서 각 정사각형이 n개의 점을 커버하는 형태는 "i부터 j까지"의 연속된 구간을 커버하는 형태임을 알 수 있습니다.
• 각 정사각형의 커버리지는 서로 겹치지 않는 경우만 고려해도 충분함을 보일 수 있습니다.
• 이는 DP 상태정의를 어떻게 할지에 대한 힌트가 됩니다. "점 i"는 "점 (r_i, c_i)"를 의미한다고 할 때, "DP[i, j] = (가장 마지막 정사각형이 점 i부터 점 j까지를 커버할 때, 점 1부터 점 j까지 커버하는 최소 비용"이라고 정의할 수 있습니다.

점화식은 어떻게 될까요? 구간 [i, j]를 커버했으면, 직전의 커버리지는 어떤 k에 대해 [k, i-1]을 커버했을 것입니다. 따라서, 각 k에 대해 DP[k, i-1] + (점 i부터 점 j까지 커버하는 비용)의 최솟값을 구하면 될 것입니다. 이때, 두 가지 경우를 고려해야 합니다.

• $r_i \le c_{i-1}$인 경우: 새로 추가하는 정사각형의 일부분은 직전 정사각형에 의해 이미 커버되어 있습니다. 이 부분을 빼야 새로 추가되는 비용을 정확히 계산할 수 있습니다.
• $r_i > c_{i-1}$인 경우: 새로 추가하는 정사각형은 기존에 커버된 영역과 겹치지 않습니다. 따라서 특별히 빼야 하는 비용이 없습니다.

이로부터 O(n^3)의 DP가 유도됩니다.

• 상태정의를 잘 관찰하면, DP[i, j]에서 i가 중요하지 않다는 것을 알 수 있습니다. 따라서 j만 남겨 DP[j]를 고려해도 충분합니다. 이로부터 O(n^2)의 DP가 유도됩니다.
• DP식을 세우면 Convex Hull Trick이 적용되는 형태라는 것을 알 수 있습니다. 구현에 따라 O(n) 또는 O(n lg n)으로 최적화가 가능합니다.

• 정사각형 개수에 따라 p의 패널티를 주도록 변경할 수 있습니다. 즉, 정사각형 x개를 사용한다면 (해당 솔루션의 최소비용) + x * p를 최소화하도록 계산을 할 수 있다는 의미입니다. 이때, DP 식과 CHT 최적화는 동일하게 유지할 수 있습니다.
• 또한, 해당 최소 비용을 갖는 솔루션이 몇 개의 정사각형을 사용했는지 추적할 수 있습니다(argmin).

이 두 가지 사실은 다음 절에서 중요하게 사용됩니다.

이제부터 Aliens trick이라고 불리는 부분입니다. 지금까지 우리는 k를 고려하지 않고 문제를 해결하였습니다. k를 고려하기 위해서는 어떻게 해야 할까요?

• C[i] = (정확히 i개의 정사각형을 사용할 때의 최소 비용)이라고 정의합시다. C[i]는 i에 대해 단조감소합니다. 그러나 단조감소 자체가 중요한 것은 아닙니다.
• 우리는 C[i-1] + C[i+1] >= 2C[i]라는 것을 증명할 수 있습니다. 즉, C[i]는 i에 대해 아래로 볼록합니다.

이것을 일단 받아들인다면, 매개변수 탐색을 이용하여 문제를 해결할 수 있습니다.

• Case 1: 만약 전역 최솟값이 1 <= i <= k인 어떤 i에서 발생한다면, 그냥 k를 무시하고 전체 문제를 풀면 됩니다.
• Case 2: 만약 전역 최솟값이 i > k인 어떤 i에서만 발생한다면, 구하는 답은 C[1..k] 중 최솟값이 됩니다. 그런데 볼록성에 의해 이는 C[k]와 같습니다.

갑자기 전역 최솟값이 발생하는 위치를 찾는 문제가 중요해졌습니다. 이는 우리가 각 i에 대해 C[i]를 모두 알고 있다면 아주 쉬운 문제입니다. 그렇지만 현재 상황이 그렇지 않으니 대안을 찾아봐야 합니다. 한 가지 방법은 접선을 사용하는 것입니다. 상황을 단순화하기 위해 먼저 인접한 두 값의 차이 C[i] - C[i-1]이 증가(strictly increasing)하는 경우를 생각해봅시다. 이 경우 기울기에 대한 매개변수 탐색을 할 수 있습니다. 만약 기울기 p인 접선이 C[i]와 접하는 위치가 j라면, 이 j는 패널티 -p를 주고 1.4절의 내용에 따라 문제를 풀어서 나온 argmin과 같습니다. 따라서, 이 argmin j가 j <= k를 만족하도록 하는 p 중 최댓값을 구하고 이를 p_max라고 합시다.

• 만약 p_max > 0이라면, C[i]는 i=k에서 증가하고 있습니다. 이는 대략 Case 1에 해당합니다.
• 만약 p_max < 0이라면, C[i]는 i=k에서 감소하고 있습니다. 이는 대략 Case 2에 해당합니다.

그러나 "strictly" increasing이 보장되지 않고 "monotonically" increasing할 수도 있는 경우에는 문제가 생깁니다.다음과 같은 입력을 생각해봅시다.

4 100 30 01 14 45 5

이 경우 C[1] = 36, C[2] = 8, C[3] = 6, C[4] = 4입니다. k=3이므로 구하는 답은 C[3]=6입니다. p_max = -2입니다. 그런데 패널티 -p_max를 주고 구한 결과에서 argmin은 2, 3, 4 중 어느 것이든 될 수 있습니다. 따라서 문제가 발생할 수 있습니다.

이를 해결하기 위해서 기울기를 정수가 아니라 (정수 + 0.5) 형태로 두고 이분탐색을 하는 트릭을 사용할 수 있습니다. 이렇게 정의하면 패널티 -p_max를 주고 구한 결과에서 argmin은 반드시 유일하게 결정되며, argmin <= k가 보장됩니다. 또한, p_max는 절대로 0이 되지 않아 생각하기에 편리합니다.

• 만약 p_max > 0이라면, argmin에 관계없이 C[i]는 i=k에서 증가하고 있습니다. 이는 Case 1에 해당합니다.
• 만약 p_max < 0이고 argmin < k라면, 그래프는 i=argmin에서 꺾이고 i=k까지 직선의 형태를 유지합니다. 이는 Case 2에 해당합니다.
• 만약 p_max < 0이고 argmin = k라면, 그래프는 i=k에서 꺾입니다. 이는 Case 2에 해당합니다.

위에서 예시로 든 입력에서는 p_max = -5/2이고 argmin = 2입니다. 따라서 Case 2에 해당합니다.

마지막 단계를 정리하고 이 절을 맺겠습니다.

• Case 1의 경우 패널티 없이 구하면 충분하다고 위에서 설명했습니다.
• Case 2의 경우 주의가 필요합니다. 매개변수 탐색의 성질에 따르면 i=argmin에서 i=k까지(또는 그보다 더 나갈 수도 있음)의 구간은 기울기 p_max + 1/2를 갖고 있습니다. 따라서 패널티 -p_max - 1/2를 주고 문제를 풀면 해당 구간에서의 답을 구할 수 있습니다. 단, 이때 구한 답의 argmin은 우리가 원하는 값이 아닐 수 있으므로, 이것 대신 k라고 생각하고 답을 구해야 합니다.

이 부분은 매우 기술적(technical)입니다. C[i-1]와 C[i+1]의 최소 비용 솔루션 중 하나를 각각 A, B라고 합시다. 구간 분절점 중 서로 중복되지 않는 것을 모아 각각 P(A), P(B)라고 합시다. 그러면 P(B)는 P(A)보다 정확히 두 개의 분절점을 더 갖고 있습니다. 순서대로 볼 때 P(B)에 연속되는 3개의 분절점이 있다면, 그 중 가운데 분절점을 P(A)로 올려보내면 총합을 증가시키지 않으면서 정사각형을 정확히 i개 사용하는 두 개의 솔루션을 만들 수 있습니다. 만약 그렇지 않다면, |P(B)| = |P(A)| + 2로부터 P(B)에는 연속되는 2개의 분절점이 반드시 존재해야 합니다. 만약 P(A)에 있는 분절점을 a, P(B)에 있는 분절점을 b라고 한다면, abba (만약 시작이나 끝에 존재하는 경우 abb나 bba일 수 있지만, 논리는 동일하게 성립함)가 존재합니다. 이때 abba를 ab와 ba로 분절하고 교차(crossover)시키면 총합은 증가하지 않습니다. 이때, P(B)의 누적 알짜 개수 우위는 0에서 시작하여 2로 끝나야 하는데, bbb의 존재 불가성으로 인해 한 번에 최대로 증가시킬 수 있는 알짜 개수는 1이므로, 어떤 bba가 존재하여 알짜 개수가 0에서 1로 되는 순간이 있어야 합니다. bbba는 불가능하므로 이는 abba였어야 하고, 결과적으로 이 abba의 가운데를 분할하고 교차시키면 총합을 증가시키지 않으면서 정사각형을 정확히 i개 사용하는 두 개의 솔루션을 만들 수 있습니다. 이렇게 구한 두 솔루션의 값을 x, y라고 하면, C[i-1] + C[i+1] >= x + y >= 2C[i]가 성립하여 결론이 증명됩니다.

긴 글 읽어주셔서 감사합니다.