RUN@KAIST 2018 겨울 3주차 연습 문제

1. POI

디스크립션을 차근차근 읽으면서, 문제의 점수, 참가자의 점수, 참가자의 등수를 문제에 적혀있는 그대로 계산하면 됩니다. 

2. 내일 할 거야

문제를 쉽게 변형해서, 과제 리스트가 주어졌을 때 모든 과제를 마칠 수 있는지를 yes / no로 판별하는 문제를 생각해 봅시다. 이 경우 과제를 데드라인 순으로 정렬한 후 처리하는 그리디 알고리즘이 최선임을 증명할 수 있습니다. (데드라인이 큰 것을, 데드라인이 작은 것보다 먼저 처리할 이유가 없음) 

한편, T일 쉰다는 것은, 사실 모든 데드라인을 T일 앞당긴 후 과제를 시작한다는 것과 동치입니다. 고로 과제를 하는 순서가 바뀌지 않습니다. 실제 T를 구하는 것은 과제를 역순으로 보면서 할 수 있습니다.

3. Archery Tournament

원은 빠르게 다루기 극히 힘든 구조 중 하나입니다. 고로, 다른 단순한 구조를 생각하는 것이 좋습니다. 이 문제에서는, 원을 감싸고 좌표축에 평행한, 변의 길이가 $2y_i$이고 중심이 $(x_i,y_i)$ 인 정사각형을 생각해 볼 수 있습니다. 물론, 정사각형은 원보다 더 넓은 면적을 덮으니, 어떠한 점을 덮는 정사각형이 여러 개일 수 있고. 정사각형이 점을 포함한다고 실제 원이 정사각형을 포함하는 것도 아닙니다. 

다행히 이러한 문제를 해결할 수 있는 좋은 성질이 있습니다. y축에 평행한 선을 그었을 때, 이 선이 관통하는 정사각형이 많지 않다는 것입니다.

어떠한 y축에 평행한 선 ($x = 0$이라 합시다.) 을 지나는 원을 모두 생각해 봅시다. 우리는 이 중 중심이 $x \geq 0$에 있는 원의 개수를 세 볼 것입니다. 원들은 모두 겹치지 않기 때문에, 임의의 두 원 $(x_1,y_1)$ / $(x_2,y_2)$ 에 대해 $(x_2-x_1 )^2+(y_2-y_1 )^2 \geq (y_2+y_1 )^2$ 를 만족합니다. 이 때 $x_2 \leq y_2,x_1 \leq y_1$ 이니, 이와 함께 식을 전개하면 $y_2 \geq 3y_1$ 이나 $y_1 \geq 3y_2$  중 하나가 성립한다는 결론이 나옵니다. 즉, 넉넉히 잡아 $2 log_3(10^9)$ 이 겹치는 원의 개수의 상한입니다. (물론 실제로는 이보다 작습니다.)

결론에 의해, 대략 40개의 원만 보면 되고, 정사각형이 된다고 x좌표 범위가 달라지지 않으니 40개의 정사각형만 보면 됩니다. 그 40개는 어떻게 빠르게 찾을까요? 이제 y좌표를 무시하고 x좌표 기준으로 문제를 다시 해석해 봅시다. 

* $[x_i-y_i,x_i+y_i]$ 를 덮는 구간이 삽입 / 삭제 된다.
* $X = x_i$ 쿼리가 주어졌을 때, 당신은 이 점을 포함하는 구간을 아무거나 찾은 후 지워야 한다.

이는, 구간의 시작점을 key로 하고 끝점을 value로 하는 이진 트리를 만든 후, key $\leq x_i$ 인 구간에서 value를 최대화하는 원소를 찾고, 이 원소가 value $\geq x_i$를 가지면 제거하는 식으로 해결할 수 있습니다. 초기 입력을 받으면 좌표 압축을 통해 key를 $[1,N]$ 사이의 서로 다른 정수로 바꿀 수 있으니, 구간 최솟값을 구할 수 있는 아무 자료구조 (예를 들어 세그먼트 트리) 를 사용해서 문제를 해결하면 됩니다.

4. Broadcast Station

예전에 써 놓은 풀이의 링크를 걸어둡니다.