Scenery

ICPC 유명 문제 Scenery 에 대한 풀이 정리

문제 링크: https://www.acmicpc.net/problem/14640
koosaga님의 Unit Scheduling 설명: PDF 다운로드
위 글에 나온 논문: PDF 다운로드

아래 글은 koosaga 글을 내가 이해한 부분만 정리한 것이다. (증명만 빠지고 거의 그대로다)

Forbidden Regions

Scenery 문제 풀이의 핵심이 되는 개념. $T = 1$ 일 경우에는 항상 데드라인이 작은 일을 할당하는 것이 최적이다.

Exchange Argument를 사용하면 쉽게 보일 수 있다.
어떤 시점에서 일을 하겠다고 했을 때 데드라인이 큰 일을 선택하는 것은 작은 일을 수행하는 것과 바꿀 수 있기 때문.

$T$ 가 그보다 큰 경우에는 오히려 할당하지 않는 것이 유리해지는 경우가 존재한다. 이를 제어하기 위해 도입된 것이 Forbidden Regions 라고 보면 된다.

Scenery 문제와 달리 논문에 나온 Forbidden Regions는 딱히 정수 구간으로 제한되지 않았다…

Naiiiive한 구현

임의의 (모든) $[r_i, d_i]$ 와 $[r_j, d_j]$ 를 고른다. (단, $r_i \lt d_j$ )
고른 구간 $[r_i, d_j]$ $[r_{i}, d_{j}]$ 안에 속하는 모든 작업을 찾아, 아래를 수행한다.
1. $d_j$ 부터(뒤쪽부터) 스케쥴링을 시도한다. 이 때, 이미 구해진 Forbidden Regions이 있다면 피해간다.
2. 스케쥴링을 한 결과는 아래 3가지 Case가 있다.
  1. 할당을 시도하다가 실패. 모든 케이스에 대해서 적어도 하나 이상 할당이 안되는 것을 발견한 것이므로 종료한다.
  2. (중요) 마지막에 할당한 $r_{last}$ 가 $r_{last} \lt T + r_i$ 를 만족하면, $(r_{last} - T, r_i)$ (개구간)을 Forbidden Regions에 추가한다.
  3. $r_{last} \ge T + r_i$ 를 만족하는 경우에는 Forbidden Regions에 추가할 필요가 없다. (쉬지 않고 할당해도 된다)

위 방법은 1번과 2번 과정부터 이미 $O(2^N)$ 가 되어 글러먹었다(모든 부분집합을 찾고 있는 것이므로). 다행히, 개선할 수 있다.

Polynomial Algorithm

우선, Forbidden Regions은 최대 $O(N)$ 개의 구간을 가진다. 왜냐면, 추가한 구간의 형태는 $(r_{last} - T, r_i)$ 였기 때문에, 끝점의 개수는 $O(N)$ 개로 고정되고, 그들 중 최대 길이를 가지는 녀석은 1개가 되므로 전체 구간 수가 $O(N)$ 이 되는 것. 이 기본 사실을 바탕으로 연산을 아래와 같이 줄일 수 있다.

간단한 관찰을 하면, 어떤 구간 $[r_i, *]$ 을 잡았을 때 Forbidden Region는 항상 그 구간의 왼쪽에 형성된다. 다시 말하자면, 선택한 구간 $[r_i, *]$ 로 생성되는 Forbidden Region은 $r_i \lt r_j$ 인 구간만 만들 수 있다는 것이다. 따라서 위의 Naive한 구현의 1번에서 임의의 구간을 선택하는 것이 아니라, 뒤쪽부터 선택하면서 보면 한번 처리한 후보를 다시 처리할 필요가 없어진다. 여기까지 하면 하나의 구간을 처리하는데 $O(N)$ , 많아야 $O(N^2)$ 번 과정을 수행하면 되므로 시간복잡도는 이 둘을 곱해서 $O(N^3)$ 이다.

여기서, 구간을 $r_i$ 가 증가하는 순으로 미리 정렬하면, 중복 계산을 제거하여 $O(N^2)$ 으로 만들 수 있다. $f(i, j)$ 를 $[r_i, d_j]$ 구간에서의 Forbidden Regions 생성 결과라고 하면, $f(i + 1, j)$ 를 알면, 마치 Mo's 알고리즘 처럼 $O(1)$ 시간만에 추가되는 녀석을 고려한 새로운 Forbidden Regions를 구할 수 있게 된다.

Deep dive Algorithm

서두에 소개된 논문에서 $O(N \log N)$ 으로 줄일 수 있는 방법에 대해서 소개하고 있다. 아직 완전히 이해하지 못해서 적지 못하지만, 논문에서 핵심은 아래라고 한다.

The key to obtaining a speed-up from $O(N^2)$ to $O(N \log N)$ involves a basic shift in the way we deal with critical times. Instead of keeping track of each $c_i$ individually, so that the current value of any $c_i$ can be found in constant time (the approach of Algorithm A), we shall keep track of a smaller amount of information, which will be sufficient for determining the current value of any $c_i$ in time $O(\log n)$ . This will permit us to use more efficient procedures for organizing and updating the data structures neded for computing the $c_i$ values.