BOJ 4317 Advanced Causal Measurements (ACM)

문제 링크:

문제 내용

시간 $t$ 에 위치 $x$ 에서 일어난 사건을 $e = (t, x)$ 라고 합시다. 빛의 속도에는 한계가 있기 때문에, $t_1 \le t_2$ 일 때 $e_1 = (t_1, x_1)$ 이 $e_2 = (t_2, x_2)$ 의 원인일 가능성이 있으려면 $t_2 - t_1 \ge |x_2 - x_1|$ 이어야 합니다.

$n$ 개의 사건이 주어집니다. 이 $n$ 개의 사건의 원인이 될 수 있는 $m$ 개의 사건의 집합 중에서 가장 이른 사건이 발생한 시간의 최댓값을 구하세요.

입력

첫 줄에 $n$ 과 $m$ 이 주어집니다. ( $1 \le n, m \le 100\;000$ )

다음 $n$ 줄에 각 사건의 정보가 $t$ , $x$ 순서로 주어집니다. ( $-1\;000\;000 \le t, x \le 1\;000\;000$ )

출력

문제의 정답을 출력합니다.

문제 풀이

스포일러

문제를 뒤집어서 원인 사건들의 가장 이른 시간 $T$ 가 주어졌을 때 그러한 사건의 개수의 최솟값을 구해 봅시다.

먼저, 원인 중에 $T$ 보다 늦게 발생한 사건이 있다면, 그 사건을 시간 $T$ 로 옮겨도 됩니다. 따라서 모든 원인 사건의 발생 시간을 $T$ 로 고정할 수 있습니다. 그리고 $T$ 보다 일찍 발생한 결과 사건이 있다면 원인 사건의 가장 이른 시간은 $T$ 일 수 없습니다.

이제 원인 사건의 $x$ 가 증가하는 순으로 필요한 사건을 추가해주면 되는데, 다음과 같이 하면 됩니다.

추가할 원인 사건의 $x$ 가 감소하는 일이 절대 없게 하려면, 주어진 결과 사건들을 $t + x$ 의 오름차순으로 정렬해야 합니다. 아직 커버되지 않은 $(t, x)$ 를 커버하는 최대의 $x$ 좌표는 $t + x - T$ 입니다.
일단 $(T, X)$ 를 추가했으면, 이후의 모든 점에 대해 $T + X \le t + x$ 는 이미 성립하므로, $x - t \le X - T$ 인 모든 점이 커버됩니다.

따라서 이 방법으로 최적의 원인 사건의 개수를 구할 수 있으므로, 이것을 기준으로 매개변수 탐색을 진행해주면 됩니다.

Last updated on 2026년 1월 14일 13:40:32

BOJ 4124 Secret Polynomial BOJ 4408 Election