SCPC 2016 본선 4번 풀이. 반물질

문제 설명

www.codeground.org 참조

제약 조건: 1 <= N <= 10,000, 1 <= M <= 10,000, 1 <= P <= M

실행 조건: 전체 테스트 케이스는 12개 이하, 실행시간 총합 4초 이하, 메모리 총합 256MB 이하

* 직사각형의 모든 부분은 x좌표가 0 이상 100,000 이하인 부분에 포함된다는 조건을 편하게 쓰기 위해 C = 100,000이라고 하자.

부분문제 1,2,3 풀이: O(NM lg C) Solution

일단, (직사각형, 트랙, x좌표) 조합이 주어졌다면 해당 조합으로 얻는 반물질의 양을 O(1)에 계산할 수 있다.

따라서 이진 탐색을 수행하면 각 수거기에 대해 lg C회를 계산하면 된다. 이때 하나의 수거기에 대해 특정 x좌표에서의 값을 계산하려면 가능한 모든 (직사각형, 트랙) 조합에 대해 해당 x좌표에서의 값을 계산해 더해야 하므로, 해당 수거기에 대한 연산횟수는 O(N * (해당 수거기에 할당된 트랙 수) * lg C)이다. 모든 수거기에 대해 더하면 전체 트랙 수는 M이므로 O(NM lg C)이 된다. 부분문제 1,2,3은 N,M <= 500이므로 4초 내에 충분히 해결할 수 있다.

하지만 전체 문제를 해결하기에는 당연히 부족하다. 참고로, N=M=10,000인 데이터를 생성해 넣어본 결과 이 데이터 하나를 처리하는 데 58초가 걸렸다.

부분문제 4 시도 1: O(NM) Solution (실패)

시간복잡도를 줄이려면 무엇을 중복 계산하고 있는지 생각해봐야 한다. 잘 생각해보면, 이진 탐색에서 수거기의 수거량을 계산할 때마다 모든 (직사각형, 트랙) 조합을 불필요하게 다시 처리하고 있다. 이것을 미리 처리해놓으면 어떨까? 어떤 수거기의 특정 x좌표에서의 수거량을 f(x)라고 하면, f(x)는 이차함수 조각이 연결된(piecewise quadratic) 연속함수이다. 그리고 이 조각은 직사각형의 세로 경계가 있는 x좌표에서만 발생하므로, 조각의 개수는 기껏해야 O(N)개이다.

따라서 조각을 모두 계산해 놓는다면, 이진 탐색 시 f(x)를 한 번 계산하는 시간복잡도는 O(1)이다. 조각들을 이진 탐색하기 위해서는 조각들의 경계에서의 f(x)값을 이용해 1차 이진탐색을 하고, 다시 해당 조각 내에서 2차 이진탐색을 하면 된다. 이렇게 되면 이진탐색 자체에 걸리는 시간은 O(P lg C)이다.

전처리에 걸리는 시간은 어떤가? 일단 Event point는 직사각형의 왼쪽, 가운데, 오른쪽의 세 곳이고, 이는 수거기별로 차이가 없다. 따라서 Event point를 정렬하는 데 O(N lg N)이 1회 소요된다. 나머지는 1D Sweeping을 P번 하는 것이다. 이때 각 수거기에서 매 Event point마다 (해당 수거기에 할당된 트랙 수)만큼을 처리하므로, 해당 수거기의 전처리 시간은 O(N * (해당 수거기에 할당된 트랙 수))이고, 전체 수거기에 대해 더하면 O(NM)의 전처리 시간을 갖는다.

앞선 Solution에 비해 lg C라는 인수를 떼어냈으므로 시간복잡도는 획기적으로 개선되지만, 아직 문제 해결에는 부족하다. 이전 Solution에서 58초가 걸리던 데이터로 다시 벤치마크를 해 보면 7초 정도로 줄어들긴 하지만, 여전히 4초 제한에 걸려 통과하지 못한다.

부분문제 4 시도 2: O({(11N+M) lg (M+3N) + P lg P} lg C) Solution (성공)

O(NM)으로도 해결이 되지 않으니, 무언가 특단의 조치가 필요해 보인다. 지금의 문제는 (직사각형, 트랙) 조합이 각각 한 번씩 무조건 고려되어야 한다는 점이다. 하지만 잘 생각해보면, 하나의 직사각형은 세로로 서로 붙어있는(연속된) 트랙들을 커버한다. 이 트랙들에 대한 Range Update를 할 수는 없을까? 지금 상황은 마치 Range Update가 O(M), Point Query가 O(1)인 것과 비슷하다. 우리는 각각을 O(lg M)으로 줄여야 한다.

하지만 효율적인 Range Update를 가로막는 장애물들이 있다. 하나는 반물질 양 공식에 들어있는 절댓값 기호이고, 다른 하나는 하나의 직사각형의 어떤 트랙을 커버할 때 일부만 커버할 수도 있다는 사실이다. 이로 인해 효율적인 Range Update가 어려워지게 된다.

이를 해결하기 위해, 입력을 변환하여 단순화해보자. 직사각형에서 얻어지는 반물질 양 공식에 들어있는 절댓값 기호를 없애기 위해, 각 직사각형을 그 중심을 기준으로 4개의 직사각형으로 나누어 그 내부에서 얻어지는 반물질 양 공식이 선형적으로 표현되게 하자. 직사각형의 개수는 4N개로 증가하지만, 큰 증가는 아니다.

또한, 직사각형이 하나의 트랙을 일부만 덮는 경우를 없애기 위하여, 트랙 경계가 아닌 어떤 y좌표를 위 4N개의 직사각형 중 하나 이상이 경계로 갖는 경우 해당 y좌표를 트랙 경계로 추가하고, 트랙 번호를 리넘버링하자. 이 연산에서 y좌표는 최대 3N개 추가되므로, 트랙 y좌표는 최대 M' + 3N개로 늘어나지만, 역시 큰 증가는 아니다. 이렇게 하고 나면 각 트랙은 그 y좌표 범위 전체가 하나의 직사각형과 만나거나, 아예 만나지 않거나 둘 중에 하나이다.

이제 귀찮은 문제들을 해결했으므로, 본론으로 돌아와서 공식을 만들어보자. Range Update가 가능하려면, 하나의 직사각형이 커버하는 여러 트랙에 대해 각 트랙에 대해 동일한 공식을 적용하여 계산할 수 있어야 한다. 이때 우리는 위 변환의 결과로 반물질 양 공식의 선형성을 보장해 놓았으므로, 해당 트랙의 아래 y좌표 y_lo와 위 y좌표 y_hi, 그리고 현재 x좌표 이 세 가지 변수에만 의존하는 식을 세울 수 있다. 만약 해당 직사각형의 왼쪽 아래 좌표를 (X, Y)라고 한다면, 해당 트랙과의 영역 교집합인 (X, y_lo) ~ (x, y_hi)에 포함되는 반물질의 양은 다음과 같이 구할 수 있다.

(반물질의 양) = f(x, y_hi) - f(x, y_lo)

여기서 f(x, y)는 직사각형 영역의 일부인 (X, Y) ~ (x, y)에 포함되는 반물질의 양이다. 해당 직사각형의 왼쪽 아래 단위 정사각형의 반물질 양을 A, x좌표가 1 증가할 때 단위 정사각형의 반물질 양의 변화량을 B_x, y좌표가 1 증가할 때 단위 정사각형의 반물질 양의 변화량을 B_y라고 하면

이때 f(x, y)는 1, x, y, x², xy, y², x²y, xy²의 선형결합으로 표현되며, 선형결합의 계수들은 해당 정사각형이 커버하는 트랙 전체에 대해 동일하게 적용된다. 따라서 이제 1D Sweeping을 하면서 Range Update를 할 수 있다. 그러므로 Range Update, Point Query를 지원하는 적절한 자료구조를 8개 만들어 8개의 계수 값 각각을 Event point에서 갱신해주면 된다. 이제 한 번 1D Sweeping을 하는 데 걸리는 시간은 O(8N lg (M + 3N))이다. 여기에 Parallel Binary Search를 적용하면 1D Sweeping을 O(lg C)번만 하면서 모든 수거기의 답을 얻을 수 있다. 1D Sweeping 연산만 고려하면 최종 시간복잡도는 O(8N lg (M+3N) lg C).

이제 나머지 연산의 시간복잡도도 따져보자. 일단 매번 Binary Search를 할 지점을 계산하고, 이를 정렬하여 1D Sweeping과 Parallel하게 수행해야 한다. 정렬하는 데 매 스텝마다 O(P lg P)가 소요되므로 전체는 O(P lg P lg C)이고, 한 수거기의 값을 한 번 계산하는 데는 O((해당 수거기에 할당된 트랙 수) * lg (M + 3N))이 소요되므로 전체는 O((M + 3N) lg (M + 3N) lg C)이다.

다 더하면 연산횟수는 대략 120,000 lg 40,000 lg 100,000 = 30,470,809회가 된다. 이론적으로는 이제 해결됐다. 하지만 어떻게 구현하느냐에 따라 4초 내에 통과할 수도 있고, 통과하지 못할 수도 있다. Range Update, Point Query 연산이 연산량이 가장 많아 전체 수행시간을 결정하게 되는데, Segment Tree with Lazy Propagation으로 구현하면 N=M=10,000인 위 데이터로 로컬에서 약 4초가 조금 넘는다. 반면 그보다 상수인수가 작은 Fenwick Tree에서 델타량을 이용해 Range Update, Point Query를 구현하면 로컬에서 약 2초가 걸리고, 온라인에서도 통과할 수 있다.

추가 최적화 1: O({(9N+M) lg (M+3N) + P lg P} lg C) Solution

조금만 생각해보면, 4분할된 직사각형에서 가로로 인접한 두 직사각형의 경계는 x좌표가 같고 8성분 벡터가 더해져야 하는 트랙 범위도 같다. 따라서 둘을 합쳐서 고려하면 두 직사각형에서 3개의 8성분 벡터를 고려한다. 원래 직사각형 하나에서는 6개의 8성분 벡터를 고려하므로, 이전의 8N개에서 6N개로 줄어든다. 시간이 가장 많이 걸리는 연산 횟수의 25% reduction은 꽤 큰 시간 단축을 가져온다. 전체 수행시간은 대략 15-20%정도 줄어든다.

추가 최적화 2: O({6N lg (M+3N)}*log_KC + ((M + 3N) lg (M+3N) + P lg P)*(K-1)*log_KC)

지금까지는 병렬 '이진' 탐색(Parallel 'Binary' Search)를 했다. 하지만 1D Sweeping이 90% 이상의 시간을 소모하고 있는 현 상황에서는 이진(binary)이 아닌 '삼진(ternary)', '사진(quaternary)' 탐색을 고려할 수 있다. 매 iteration마다 1회 계산으로 구간을 1/2로 하는 대신 (K-1)회 계산으로 1/K로 하는 것이다. 이렇게 하면 1회마다 계산 횟수는 조금 늘어나지만 그 대신 1D Sweeping의 횟수를 획기적으로 줄일 수 있다. 대략 K = 7 근방이 최적으로 보이며, 이때 시간은 K = 2일 때보다 50% 정도 줄어든다. 최종해의 수행시간은 0.7초 가량이다.

이것으로 SCPC 2016 문제풀이 끝. 이제부터는 2017, 2018 문제를 마저 풀어야겠다.