SCPC 2017 본선 3번 풀이. Colony

문제 설명

www.codeground.org 참조

부분문제 1 풀이

만약 어떤 연도 Y에 캡슐이 도달 가능하다면, 캡슐은 Galaxy1이 어떤 연도 i에 건설한 Colony1[i]에서 출발하여 Galaxy2이 어떤 연도 j에 건설한 Colony2[j]에 도달했을 것이다. Colony1[i]에서 출발한 캡슐이 방문 가능한 지점은 택시거리가 Y-i 이하인 모든 지점이다. 따라서 Colony1[i]와 Colony2[j]의 택시거리가 Y-i 이하인지 확인하면 된다.

전체 시간복잡도는 O(N³)으로 N <= 200인 부분문제 1을 해결할 수 있다. 

부분문제 2 풀이

규칙을 잘 생각해보면, 어떤 연도 Y에 메시지가 도달 가능했다면 Y+1, Y+2, ...의 이후 연도에도 모두 도달 가능하다. 따라서 이진탐색을 할 수 있다.

전체 시간복잡도는 O(N² lg N)으로 N <= 1,000인 부분문제 2를 해결할 수 있다.

부분문제 3 풀이

어떤 연도 Y에 캡슐이 도달 가능한지는 Colony1[i] (1<=i<=Y)들이 만드는 영역 안에 Colony2[j] (1<=j<=Y)의 점들이 하나라도 포함되었는지와 동일한 문제다. 따라서 원 문제는 어떤 집합의 점들 중 어떤 정사각형들의 합집합에 포함되는 것이 하나라도 있는지를 판정하는 문제로 환원된다. 이때 모든 정사각형의 좌표축이 동일하므로, Plane Sweeping 알고리즘을 써서 쉽게 해결할 수 있다.

정사각형이 45도 기울어져 있으므로, (x, y) -> (x+y, x-y)로 바꾸어 좌표축을 돌려주는 전처리를 해 준다. 그러면 좌표축을 표준좌표로 바꿀 수 있다. 

y축에 평행한 직선 L을 하나 잡고, 이를 왼쪽에서 오른쪽으로 움직이면서 정사각형을 휩쓸며(Sweeping) 지나간다. 그러면서 L 위의 점들 중 정사각형들의 합집합에 포함되는 y좌표의 구간(들) S를 갱신한다. S는 정사각형의 세로 경계에서만 바뀔 수 있으므로, 고려해야 할 경계는 고작 O(N)개 뿐이다. 이제 Colony2의 점들을 미리 x좌표에 따라 정렬해 놓고, 각 x좌표 구간 내에서 y좌표가 S에 포함되는지를 조사하면 된다.

이때 y좌표의 범위는 -1,000,000,000 이상 1,000,000,000 이하이므로 모든 좌표에 대해 처리하는 방식을 쓸 수 없다. 따라서 정사각형의 가로 경계를 이루는 O(N)개의 좌표를 이용해 y좌표 구간을 O(N)개로 분할하여야 한다. S에는 각 구간을 점유하고 있는 정사각형의 수를 기록하고, 세로 경계에서는 해당 정사각형이 커버하는 y좌표 구간에 대해 점유 수를 +1 또는 -1 해 주면 된다. 그러면 하나의 세로 경계 처리에 시간이 O(N) 걸리고, 전체 경계 처리에는 O(N²)이 걸린다. 이는 이전과 다를 바 없다.

어떻게 해야 할까? 현재는 Range Update가 O(N), Point Query가 O(1)이다. 이를 각각 O(lg N) 내에 지원하는 자료구조를 사용하면 전체 경계 처리시간을 O(N lg N)으로 줄일 수 있다. 바이너리 인덱스 트리(Binary Indexed Tree, BIT) 자료구조를 사용하면 된다.

전체 시간복잡도는 O(N lg N lg N)으로, N <= 100,000인 부분문제 3(즉, 전체 문제)을 해결할 수 있다.

보충 설명

* 좌표축을 돌릴 때 도형의 스케일이 루트2만큼 확대되므로 주의하여야 한다.

* Plane Sweeping의 Event Point들을 정렬할 때, x좌표가 같다면 반드시 정사각형을 시작하는 Event가 먼저 오도록 정렬해야 한다. 시작하는 Event를 모두 처리하고 끝내는 Event 처리를 시작하기 직전에 해당 x좌표의 Colony2 점들을 처리해야 한다. x좌표가 어떤 Event Point와도 일치하지 않는 Colony2 점들은 x좌표가 그보다 큰 Event Point 중 x좌표가 최소인 지점의 Event 처리를 시작하기 직전에 처리해야 한다.

* 바이너리 인덱스 트리는 보통 Prefix Sum(배열 A[1..N]에 대해 S[i]=A[1]+A[2]+...+A[i])을 구하는 데 많이 사용된다. 임의의 원소 A[i]를 갱신하는 작업과 임의의 Prefix Sum S[i]를 계산하는 작업이 각각 O(lg N)이다. 어떤 배열 B[1..N]의 Range Update, Point Query를 하기 위해서는 A[i] = B[i] - B[i-1]로 놓으면 된다(단, B[0]=0). Range Update 작업 B[L..R] += D는 A[L] += D, A[R+1] -= D와 같으며, Point Query 작업은 B[i] = A[1] + A[2] + ... + A[i]이므로 Prefix Sum으로 계산할 수 있다. 따라서 Range Update, Point Query가 모두 O(lg N)이다.

* 바이너리 인덱스 트리 대신 '세그먼트 트리 + 지연전파 (Segment Tree with Lazy Propagation)'를 사용할 수도 있지만, 구현이 더 복잡하고 성능은 오히려 느리므로 추천하지 않는다. 바이너리 인덱스 트리로 해결할 수 없는 형태일 때만 세그먼트 트리를 사용하자.