x축 위에 $N$개의 점이 있다. 각 점은 좌표 $x_i$와 가중치 $w_i$를 갖는다. 두 점의 가중치의 합이 두 점 사이의 거리 이하일 때 간선으로 연결한 그래프에서 maximum clique의 크기를 구하시오.

  • $1 \le N \le 200,000$
  • $1 \le x_i, w_i \le 10^9$

관찰

일단 $w_i + w_j \le |x_i - x_j|$라는 식으로는 뭔가를 하기가 어렵기 때문에 점을 좌표가 증가하는 순으로 정렬하고 번호를 다시 매긴다. 그러면 $i < j$에 대해 $w_i + w_j \le x_j - x_i$라는 식을 얻는다. 이를 조금 바꾸면 $x_i + w_i \le x_j - w_j$가 된다.

점들의 집합에 점을 번호가 증가하는 순으로 넣는다고 생각해보자. 점 $j$를 현재 집합에 넣으려면, 집합에 속한 모든 점 $i$에 대해 위의 식을 만족해야 한다. 이를 수식 하나로 요약하면 $\max_i{x_i + w_i} \le x_j - w_j$가 된다. 그런데 이 조건을 만족하여 점 $j$를 집합에 넣게 되면, $\max_i{x_i + w_i} \le x_j - w_j < x_j + w_j$이므로 새로운 $x_i + w_i$의 최댓값은 반드시 $x_j + w_j$가 된다. 따라서 점 $j$를 넣을 수 있는 상황이 여러 가지라면 그 중에서 집합에 이미 점이 가장 많이 있는 것이 항상 이득이다.

점 $j$를 현재 집합에 넣지 못한다면 현재 집합의 가장 오른쪽 점을 교체하여 더 나은 상황을 만들 수 있는지 확인해야 한다. 여기서 더 나은 상황은 현재 집합의 가장 오른쪽 점이 $j’$일 때 $x_{j’} + w_{j’} > x_j + w_j$인 상황이다. $x_{j’} < x_j$이므로 $w_{j’} > w_j$이고, 따라서 $x_{j’} - w_{j’} < x_j - w_j$가 되어 마지막 점을 무조건 교체할 수 있다.

결과적으로 회의실 배정 그리디와 비슷하게 생긴 코드를 짜서 맞을 수 있다.

다른 풀이

위의 풀이를 정리하면서 기여에 자주 등장한 1931. 회의실 배정과의 연관성을 계속 생각하다 보니 간단한 변환이 된다는 것을 깨닫게 되었다.

$x_i + w_i \le x_j - w_j$라는 식을 다시 생각해 보자. 각각의 점을 $[x_i - w_i, x_i + w_i]$의 구간으로 바꾸면 앞의 조건은 두 구간이 겹치지 않는다(한 점에서 만나는 것은 허용)는 것과 동치이다. 그러면 그냥 회의실 배정 문제와 같은 문제가 되어 버린다. 어?…