SCPC 2017 2차예선 5번 풀이. 자석

문제 설명

\(N\)개의 폐구간에 대해, 각 구간 \(i\) (\(1 \le i \le N\))의 끝점 \(L[i]\), \(R[i]\)가 주어진다. 또한, 각 구간의 활성화 비용 \(W[i]\)가 주어진다.

하나의 구간 \(i\)를 비용 \(W[i]\)를 들여 활성화하면, 이 구간은 '활성구간'이 되고, 구간 \(i\) 및 구간 \(i\)와 한 점이라도 겹치는 모든 구간이 '커버'된다. 각 구간은 하나 이상의 구간에 의해 커버될 수 있다.

 

모든 구간을 커버하기 위한 최소 비용을 구하면?

 

제한조건: \(N \le 100,000\),   \(0 \le L[i], R[i] \le 10^9\),   \(1 \le W[i] \le 10^5\)

실행조건: 90개 이하 테스트 케이스에 대한 실행시간 총합 3초 이내

 

(자세한 설명은 www.codeground.org 참조)

풀이

1. 개요

DP 문제이다. 우선 주어진 \(N\)개의 구간을 왼쪽 점에 대한 오름차순으로, 왼쪽 점이 같을 때는 오른쪽 점에 대한 오름차순으로 정렬하고 시작하자. (참고: 구간의 활성화 비용은 정렬할 때 고려할 필요 없음.)

 

한편, 주어진 문제의 구간은 실수 구간이지만 모두 폐구간이고 끝점은 항상 정수이므로, 각각을 '정수' 구간으로 생각해도 Topology가 변하지 않는다. 즉, 구간 [3, 5]는 정수 3, 4, 5로 생각해도 된다. 이렇게 사고하는 편이 실수식 사고보다 편리하다.

 

이제 DP 상태를 정의한다. 구하는 목적값은 \(\min\lbrace P[N], Q[N]\rbrace\)이다.

 

• \(P[i]\) = (구간 1..i만 있을 때, i번째 구간을 활성화하는 경우, 1..i를 커버하는 최소 비용)
• \(Q[i]\) = (구간 1..i만 있을 때, i번째 구간을 활성화하지 않는 경우, 1..i를 커버하는 최소 비용)

초기조건은 자명히 P[1] = W[1], Q[1] = INF이다. 한편, 0개의 구간을 덮는 비용은 0이므로 Q[0] = 0이다. 다만, P[0]은 결정할 필요가 없으며, INF로 두어도 된다.

점화식을 살펴보기 전에, 몇 가지 보조정리를 관찰하자.

 

보조정리 1. 구간 i가 활성화되었을 때, 구간 i가 오른쪽으로 커버하는 구간들은 i를 포함한 폐구간을 이룬다. 즉, 구간 i는 어떤 F = F(i)에 대해 구간 i, i+1, i+2, ..., F와 겹치고, 구간 F+1, F+2, ..., N과는 겹치지 않는다.

 

증명) 구간을 정렬한 기준에 의해, 구간 \(k\) (\(i < k\))가 구간 \(i\)와 겹친다는 것은 구간 \(k\)의 왼쪽 끝점 좌표가 구간 \(i\)의 오른쪽 끝점 좌표보다 작거나 같은 것과 동치이다(\(L[k] \le R[i]\)). 그런데 구간의 왼쪽 끝점은 \(k\)가 증가할수록 단조증가하므로, 어느 시점까지는 R[i] 이하이고 어느 시점부터는 R[i]를 초과하게 된다. 혹은 끝까지 R[i] 이하로 유지된다. 따라서, \(R[k] \le R[i]\)인 최대의 \(k (\ge i)\)를 잡으면 그것이 F[i]의 정의에 부합한다.

 

노트. 각 구간 \(i\)는 스스로를 커버하므로 \(i \le F[i] \le N\).

경고. F[i]는 단조증가가 아닐 수 있다. 

 

보조정리 2. 구간 i < j < k에 대해, 구간 k가 구간 i와 겹치면 구간 j도 구간 i와 겹친다.

 

증명) 구간 k가 구간 i와 겹치므로, \(R[i] \ge L[k]\). 그런데, j < k이므로 \(L[j] \le L[k]\). 따라서 \(R[i] \ge L[k] \ge L[j]\)이므로 구간 i와 j는 서로 겹친다.

 

보조정리 3. 구간 i < j에 대해, \(R[i] \ge R[j]\)이고 구간 j가 커버되었다면 구간 i도 커버되었다.

 

증명) 구간을 정렬한 기준에 의해 \(L[i] \le L[j]\)이다. 이것과 주어진 조건을 합치면 \(L[i] \le L[j] \le R[j] \le R[i]\)이므로 구간 j는 구간 i 내부에 완전히 포함된다. 이제 구간 j가 커버되었으므로 구간 j 내에 활성화된 어떤 구간의 한 점이 있고, 이는 구간 i에도 포함되므로 구간 i도 커버되었다.

 

이제 필요한 보조정리를 기술했으므로 DP 점화식을 살펴보자.

 

2. Q[i]에 대한 점화식

구간 i를 활성화하지 않고 구간 i가 커버되어야 하므로, 어떤 \(1 \le a < i\)에 대해 구간 \(a\)가 구간 i를 커버한다. 그렇게 할 수 있는 \(a\)일 필요충분조건은 \(F[a] \ge i\)이다. 그러한 \(a\)를 활성화했다고 하자. 그러면 보조정리 1에 의해 \(a < j < i\)인 모든 구간 \(j\) 역시 구간 \(a\)에 의해 커버된다.

 

그런데 어떤 \(a < j < i\)에 대해서도 구간 \(j\)를 활성화하지 않는 최적해가 존재한다. 이는 보조정리 2 때문으로, 각 \(1 \le k < a\)에 대해 \(k < a < j\)이므로, 구간 \(j\)가 커버하는 모든 구간 \(k\)는 구간 \(a\)에 의해서도 커버되기 때문이다.

 

따라서 구간 \(a < j < i\)들은 커버도 문제가 없고, 스스로 활성화되어 다른 것을 커버하여 기여할 수도 없으므로, 고려대상에서 완전히 배제할 수 있다. 즉, 구간 \(a\)를 반드시 활성화할 때 구간 \(1..a\) 내부에서만 활성화를 하여 \(1..a\)를 커버하는 최소 비용과 같으며, 이는 \(P[a]\)와 일치한다.

 

결론적으로 가능한 각 \(a\)에 대해 최소 비용을 구하면 되므로 점화식은 다음과 같다.

$$ Q[i] = \min_{1 \le a < i \text{ and } F[a] \ge i} P[a] $$

만약 가능한 \(a\)가 없으면 구간 \(i\)를 활성화하지 않고 구간 \(1..i\)를 커버하는 것이 불가능한 것이므로 \(Q[i] = \text{INF}\)로 한다.

 

 

3. P[i]에 대한 점화식

P[i]는 점화식이 좀 더 복잡하다.

 

점화식을 이끌어내기 위해, 구간 i를 활성화하면서 구간 1..i를 커버하는 어떤 솔루션이 주어져 있다고 하고, 그 솔루션에서 구간 i를 도로 비활성화했을 경우, 커버된 채로 남아있는 구간이 무엇 무엇인지 조사해보자. 우선, \(R[j] < L[i]\)인 구간 \(j\)는 반드시 커버된 채로 남아있어야 한다. 왜냐면 구간 i에 의해 커버될 수 없기 때문이다.

 

따라서, 그러한 \(j\)를 모은 집합을 정의하자.

$$ S := \lbrace 1 \le j < i \,\,|\,\, R[j] < L[i] \rbrace $$

\(E := \max_{j\in S} j\)라고 정의하면, 다음 보조정리가 성립한다.

 

보조정리 4. 구간 i를 활성구간으로 가지면서 구간 1..i를 커버하는 임의의 솔루션에 대해, 구간 i를 들어내더라도 모든 구간 \(1 \le j \le E\)가 커버된 상태로 남아있다. (* 지금은 구간 i+1..N은 고려하지 않음)

 

증명) 만약 \(j \in S\)라면 앞선 논의에 의해 자명하다. 따라서 \(j \notin S\)라고 하자. 그러면 \(j < E\)이고 \(R[j] \ge L[i] > R[E]\)이므로 보조정리 3에 의해 구간 j도 커버되었다.

 

한편, 보조정리 4에 의해서 커버되지 않은 구간들은 어떨까? 그런 구간들은 오른쪽 끝점이 \(L[i]\) 이상인데, 왼쪽 끝점도 \(L[i]\) 이상인지에 따라 \(U\)와 \(V\) 두 집합으로 나누어 생각할 수 있다.

$$ U := \lbrace E < j < i \,\,|\,\, L[j] < L[i] \le R[j] \rbrace $$

$$ V := \lbrace E < j < i \,\,|\,\, L[i] \le L[j] \rbrace $$

즉, \(U\)는 구간 \(i\)에 걸치기는 하지만 완전히 포함되지는 않은 구간들의 집합이고, \(V\)는 구간 \(i\) 내부에 완전히 포함된 구간들의 집합이다. 한편, 구간을 정렬한 기준에 의해 \(U = \lbrace j\,\,|\,\, E < j \le H \rbrace \), \(V = \lbrace j\,\,|\,\, H < j < i \rbrace \)를 만족하는 \(E \le H < i\)가 존재한다.

 

그런데 \(V\)의 임의의 구간 \(j\)는 어차피 구간 \(i\)에 의해 커버될 영역 내부만 전부 또는 일부를 커버하므로, 어차피 구간 \(i\)를 활성화할 상황에 굳이 고려할 필요가 없다. 즉, 없다고 봐도 된다. --- (진술 1)

 

따라서 \(U\)의 구간의 커버에 대해 생각해보자. 만약 어떤 \(j, k \in U\) (\(j < k\))에 대해 구간 j는 커버되지 않고 구간 k는 커버되었다면 이는 어떤 상황일까? 구간 k를 커버한 활성화점을 \(L[k] \le x \le R[k]\)라고 할 때, 만약 \(x < L[i]\)라면 \(L[j] \le L[k] \le x < L[i] \le R[j]\)이므로 구간 j도 커버된다. 따라서 \(x \ge L[i]\)이다. 이때 구간 j가 커버되지 않았으므로, 점 \(L[i]-1\)은 커버되지 않았다. 따라서 활성화점 \(x\)은 왼쪽 끝점이 \(L[i]\) 이상인 어떤 활성구간 \(\ell\) (\(\ell < i\))에서 온다. 구간을 정렬한 기준에 의해 \(L[k] = L[i]\), \(R[k] \le R[i]\)이므로 구간 \(\ell\)은 구간 \(i\)에 완전히 포함된, 즉 \(\ell \in V\)인 구간이다. 그런데 구간 \(\ell \in V\)가 활성구간이라는 것은, 고려하고 있는 솔루션이 최적이 아니라는 뜻이다(진술 1). 즉, 불연속성이 발생하는 구간 커버 상황은 고려할 필요가 없다.

 

따라서 최적해를 구하기 위해서는, 구간 \(i\)를 껐을 때, 커버된 구간은 \(1\)부터 \(k\)까지 연속적이고 (\(E \le k \le H\)), 그 이후로는 모두 커버되지 않고 남는 경우만 고려해도 충분하다. 따라서 점화식은 다음과 같이 주어진다.

$$ P[i] = W[i] + \min_{E \le k \le H} \min \left\lbrace P[k], Q[k] \right\rbrace $$

그런데 잘 생각해보면, 이 중 반드시 최적해가 존재하므로, 여기에 추가로 \(H < k < i\)인 \(k\)를 고려해도 문제가 없다. 필요한 것보다 많이 커버하는 것이 최적은 아니어도 하나의 올바른 방법이기는 하기 때문이다. 따라서 (더 계산하기 쉬운) 최종적인 점화식은 다음과 같다.

$$ P[i] = W[i] + \min_{E \le k < i} \min \left\lbrace P[k], Q[k] \right\rbrace $$

 

* UPDATE (20/08/29): 위 논의를 보다 간략화할 수 있다. 집합 \(T\)를 다음과 같이 정의하자.

$$ T = \lbrace j \,\,| \,\, E < j < i \rbrace $$

만약 어떤 \(j, k \in T\) (\(j < k\))가 \(j\notin T\), \(k\in T\), 즉 구간 j는 커버되지 않고 구간 k는 커버되었다면 이는 어떤 상황일까? 구간 k를 커버한 활성화점을 \(L[k] \le x \le R[k]\)라고 할 때, 만약 \(x \le L[i]\)라면 \(L[j] \le L[k] \le x \le L[i] \le R[j]\)이므로 구간 j도 커버된다. 따라서 \(x > L[i]\)이다. 그런데 우리가 활성화 후보로 고려할 수 있는 모든 구간의 왼쪽 끝점은, 구간을 정렬한 기준에 의해 \(L[i]\) 이하이다. 따라서 \(y = L[i]\) 역시 현재 활성화점이다. 이는 구간 j가 커버되지 않았다는 가정에 모순이다. 따라서, 어떤 구간 \(k\) (\(E \le k < i\))까지는 커버된 상태로 남고, 그 이후부터는 아예 커버되지 않는다. 즉, 불연속성이 발생하는 구간 커버 상황은 고려할 필요가 없다.

 

따라서 최적해를 구하기 위해서는, 구간 \(i\)를 껐을 때, 커버된 구간은 \(1\)부터 \(k\)까지 연속적이고 (\(E \le k < i\)), 그 이후로는 모두 커버되지 않고 남는 경우만 고려해도 충분하다. 따라서 점화식은 다음과 같이 주어진다.

$$ P[i] = W[i] + \min_{E \le k < i} \min \left\lbrace P[k], Q[k] \right\rbrace $$

 

4. 구현 (Naive)

1. 우선 각 \(i\)에 대해 \(F[i]\) 및 \(E[i]\)를 계산해 놓을 수 있다. 각 \(i\)에 대해 \(F[i]\)는 이분 탐색으로 \(O(\lg N)\), \(E[i]\)는 전체 탐색으로 \(O(N)\)이 가능하다. 전처리 총 시간복잡도는 \(O(N^2)\).
2. 각 점화식을 계산하는 데 \(O(N)\)이면 충분하다. 따라서 전체 DP표를 채우기 위해서는 시간복잡도가 \(O(N^2)\).

이렇게 하면 \(N \le 5,000\)인 부분문제 2까지 해결할 수 있다.

\(N \le 100,000\)인 부분문제 3을 해결하려면 DP식을 최적화하여야 한다.

 

5. 최적화 1: E[i] 구하기

\(E[i]\) 계산은 세그먼트 트리를 사용해 \(O(N \lg N)\)까지 줄일 수 있다. \(1 \le i \le N\)을 \(R[i]\) 오름차순, 같을 경우 \(i\) 내림차순으로 정렬하고, \(i\)에 부여된 새 인덱스를 \(A[i]\)라고 하자. 그런 다음, \(A[i]\) 좌표를 이분 탐색하여 \(L[i]\)와 같거나 커지는 가장 왼쪽 지점을 찾아 \(p\)라고 하자. 1부터 \(i-1\)까지 중 \(R[j]\)가 \(L[i]\)보다 작은 것은 \(p\) 왼쪽에, 나머지는 \(p\)와 같거나 오른쪽에 있다. (* 같을 경우 \(i\) 오름차순으로 하게 되면 \(R[j]\) 값이 \(L[i]\)와 같은데 먼저 나온 항목이 왼쪽에 놓이므로, 왼쪽 범위가 불순물을 포함하는 꼴이다.) 매 단계에서 세그먼트 트리를 1) 쿼리 2) 갱신한다. 1) 쿼리는 1부터 \(p - 1\)까지 구간 최댓값 쿼리를 하고, 2) 갱신은 A[i] 위치에 i를 값으로 삽입한다.

 

하지만 굳이 이렇게 하지 않고, 더 빠른 기법인 단조 큐(monotone queue)를 활용할 수 있다. 이 기법은 왼쪽 끝이 정지 혹은 증가, 오른쪽 끝도 정지 혹은 증가하는 이동구간에서 구간의 최댓값/최솟값을 구할 때 사용하는 기법이다. 지금의 경우 왼쪽 끝은 1로 고정, 오른쪽 끝은 매 스텝마다 1씩 증가이다. 다만 목적함수가 'R[j]가 특정 값보다 작은 j 중 가장 큰 j'이므로 조금 다르긴 하지만, 동일하게 적용할 수 있다. 왜냐면 \(E[i]\)를 구할 때 기준이 되는 \(L[i]\)값이 \(i\)에 대한 단조증가이므로 어떤 \(j < i\)가 \(R[j] < L[i]\)를 만족한 경우 \(i\) 이후의 모든 구간에 대해서도 같은 부등식을 만족하고, 따라서 구간 안에 계속 남아있을 수 있기 때문이다.

  따라서 만약 \(j < k\)이고 \(R[j] \ge R[k]\)라면 \(k\)를 발견한 이후에는 \(j\)를 유지할 필요가 없다는, 단조 큐의 핵심 조건이 그대로 성립한다. 기법의 자세한 설명은 HKOI 2017 Training Camp 자료 등을 참고할 수 있다. 시간복잡도는 \(O(N)\)이다.

 

(* 단조 큐를 구현할 때, std::deque는 느리므로 그냥 plain 배열을 사용해야 한다.)

 

6. 최적화 2: P[i] 및 Q[i] 구하기

P[i]의 점화식은 연속된 구간을 쿼리하므로 세그먼트 트리로 쉽게 구현할 수 있다.

 

한편, Q[i]의 경우는 \(1 \le j < i\) 중 \(F[j] \ge i\)를 만족하는 각 \(j\)가 연속된 구간으로 나타나지 않을 수 있으므로, 5절에서 E[i]에 대해 설명한 것처럼 \(F[j]\)를 기준으로 정렬하여 새 인덱스를 부여한 뒤 쿼리와 갱신을 반복하면 된다. (* F[j]가 같은 경우 \(j\)에 대한 내림차순으로 정렬한다.)

 

여기까지 하면 시간복잡도가 \(O(N \lg N)\)이 되므로, 적절히 구현하면 3초 내에 통과할 수 있다. 단, 구현이 효율적이지 못하면 실패한다. 특히 입력이 최대 300,000개 가량의 정수로 구성되는 만큼, Fast I/O가 도움이 된다.

 

7. 최적화 3: P[i]에 단조 큐 적용하기

P[i]의 점화식에 들어있는 구간을 보면, 상한은 \(i - 1\)이고 하한은 \(E\)인데, \(E = E[i]\) 역시 \(i\)에 대한 단조증가이므로 P[i]를 구할 때도 단조 큐를 적용할 수 있다. 이때의 목적함수는 이동구간의 최솟값으로, 5절에서보다는 더 canonical한 사용이다. 결국, 단조 큐에서 나온 값을 다시 다른 단조 큐의 하한으로 삼는, 단조 큐를 연쇄적으로 적용한 꼴이 된다. 이 부분의 시간복잡도는 \(O(N)\)으로 줄어든다. 다만, Q[i]는 줄일 수 없으므로 전체 시간복잡도는 여전히 \(O(N \lg N)\)이다.