BOJ 19933 Comparing Plants

Comparing Plants (IOI 2020 Day 1 #1)

 

서브태스크를 통해 순차적인 접근이 가능한, 풀면서 즐거웠던 문제이다.

 

 

 

문제 설명

 

$n$개의 식물이 원형으로 배치되어 있다. 각 식물의 높이는 전부 다르다.

식물의 정확한 키는 알 수 없지만, 다른 식물들과의 상대적 높이는 알 수 있다. 구체적으로, 모든 식물에 대해서 자신과 시계방향으로 $k-1$개의 식물 중 자신보다 큰 식물의 개수 $r_i$가 주어진다.

쿼리로 두 개의 식물이 주어졌을 때, 두 식물의 키를 비교하여라. 만약 비교할 수 없다면 0을 리턴한다.

 

 

 

Subtask #1

 

$k=2$인 경우, 모든 식물에 대하여 양옆의 식물과 직접적으로 키를 비교한 결과가 주어진다.

쿼리 $(x, y)$에 대해서, $x, x+1, ... , y$ 또는 $x, x-1, ... , 0, n-1, ... , y$의 크기관계가 전부 같은지 확인하면 된다.

 

 

Subtask #2, 3

 

$2k > n$이라는 조건에 주목하자.

이 경우, 모든 식물의 크기 관계를 파악할 수 있다.

우선, 최대 키를 가지는 식물 $i$에 대해 $r_i = 0$임을 관찰할 수 있다.

또한, $r_i = 0$인 모든 $i$에 대하여 키를 비교할 수 있다.

• $r_x = r_y = 0$인 $x, y$에 대해, $y-x$나 $x-y$중 하나는 $k$를 넘지 않는다.
• 이 때, 둘 중 시계 반대 방향에 있는 식물이 최대 키를 가지는 식물이다.

 

이렇게 최대 키를 가진 식물 $x$를 찾았다면, 이 식물을 가장 작은 크기로 바꾼다.

$i ∈ [x-k+1, x-1]$인 $i$에 대하여, $r_i$에 $1$씩 빼준다.

이렇게 귀납적으로 모든 식물의 키를 순서대로 구할 수 있다.

 

 

Subtask #4

 

이제 최대 크기를 가질 수 있는 식물이 많아진다.

최대 크기를 가질 수 있는 식물의 조건은 식물 $x$에 대해

• $r_x = 0$이고
• $i ∈ [x-k+1, x-1]$인 모든 $i$에 대하여 $r_i \neq 0$이다.

 

이렇게 최대 크기를 가질 수 있는 식물들을 모두 구하고, Subtask #2, 3에서와 같이 이를 최소 크기로 바꾸는 것을 모든 식물을 확인할 때 까지 반복한다.

i번째 반복에서 최대 크기를 가질 수 있는 식물들을 그룹 i라고 하자.

Subtask 4에서는 항상 비교가 가능하므로, 쿼리 (x, y)에 대하여 x와 y 중 그룹이 작은 쪽을 리턴하면 된다.

 

 

Full Solution

 

$|x-y| < k$인 식물 $x$, $y$에 대하여, $x$와 $y$는 항상 비교가 가능하다.

$|x-y| \geq k$인 경우, 어떤 경우에 비교가 가능할까? (일반성을 잃지 않고 x < y라고 하자.)

• $x < i < x+k$이며 식물 $x$보다 키가 작은 $i$ 중 제일 큰 것을 $R_x$라고 하자.
• $x+k-1 < y$일 동안 $x := R_x$를 반복한다.
• 이렇게 이동한 후, $x$의 그룹이 $y$의 그룹보다 작으면 $x$는 $y$보다 크다.
• 식물의 배치가 원형이기 때문에, 시계 반대 방향으로도 마찬가지로 비교해주어야한다.

 

모든 식물의 그룹은 세그먼트 트리 등을 이용하여 $O(NlogN)$에 구할 수 있다.

$R_x$(와 시계 반대방향으로의 $R_x$)는 전처리를 통해 모든 $x$에 대하여 $O(NlogN)$에 구할 수 있다.

이를 Naive하게 비교해준다면 $O(NlogN+NQ)$의 시간복잡도로 Subtask #5를 맞을 수 있다.

$R_x$를 Sparse Table 등을 이용하여 비교해준다면, $O((N+Q)logN)$의 시간복잡도로 AC를 받을 수 있다.