티스토리 뷰

IOI/IOI2020

IOI2020 Day1 plants 풀이

전명우 2020. 9. 22. 22:50

문제 및 채점: oj.uz

 

서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다.

 

풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시로 들어 설명하겠다.

 

이 때, 최대 크기를 가질 수 있는 식물을 찾을 건데, $i$ 번 식물이 아래 두 조건을 만족하면 최대 크기를 가질 수 있다:

 1) $R[i] = 0$: 시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$ 번 식물보다 큰 식물이 없음

 2) $R[j] = 0$ ($j$는 $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 식물 번호): 반시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$번 식물보다 큰 식물이 없음

 

$2K > N$인 경우(서브태스크 2, 3), 위 조건을 만족하는 $i$는 유일하며 전체 중 가장 큰 크기를 가지는 식물이다.

 

예시에서 두 조건을 만족하는 $i$는 5로 유일하다. 예를 들어, 6의 경우 $R[6] = 0$으로 1)번 조건을 만족하지만, $R[5] = 0$이기 때문에 2)번 조건을 만족하지 못한다.

 

만약 조건을 만족하는 $i$가 여러 개인 경우 그중 아무거나 하나를 찾고, $i$번 식물의 크기가 가장 크다고 가정한다. 그리고 $R[i]$의 값을 없애고, $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 $R$ 배열 값을 1 감소시킨다.

 

그러면 $R[3]$의 값이 1 감소하여 0이 되었고, $R[4]$의 값이 1 감소하여 1이 되었다. 그리고 위의 과정을 반복한다.

 

지금 상황에서 두 조건을 만족하는 $i$는 3과 7로 유일하지 않다. 즉, 3번 식물과 7번 식물의 크기 비교가 불가능한 상황임을 알 수 있다. 앞서 말했던 것처럼, $i$가 여러 개인 경우 그중 아무거나 하나를 찾자. 편의상 번호가 제일 작은 3번 식물로 과정을 진행하겠다.

 

이 방법으로 가능한 여러 식물들의 크기 구성 중 하나를 배열 $H$에 기록했다.

 

서브태스크 2 (14 점)

$N \leq 5000, 2K > N$. 위의 방법을 naive하게 구현하면 시간복잡도는 $O(NK)$가 되며, $2K > N$을 만족하는 경우 매 순간 최대 크기를 가지는 식물 후보 $i$가 유일하므로, 가능한 식물 크기 구성이 유일하다. 따라서 구한 배열 $H$로 모든 질문을 해결할 수 있다.

 

서브태스크 3, 4 (13, 17 점)

위의 방법을 lazy propagation을 이용한 segment tree와, 집합에서 lower bound와 left, right iteration이 가능한 set 같은 자료구조를 사용하면 $O(N \lg N)$ 시간에 해결할 수 있다. 배열 $H$의 내용만 가지고는 크기를 비교할 수 없는 식물 쌍을 확인할 수 없다. 서브태스크 3, 4는 식물 크기를 비교할 수 없는 쌍에 대한 고려를 하지 않아도 해결할 수 있다.

 

다음 서브태스크들을 풀기 위해 필요한 관찰

식물 $i$에 대해 시계방향과 반시계방향으로 $K-1$ 이내에 있는 식물들은 배열 $H$에 있는 값의 대소 비교를 통해 식물 크기를 비교할 수 있다.

 

서브태스크 5 (11 점)

$N \leq 300$. 위의 사실을 이용하여, $a$ 번 식물과 $b$ 번 식물의 크기 비교를 할 수 있고, $a$ 번 식물의 크기가 $b$번 식물보다 큰 경우 정점 $a$에서 정점 $b$로 가는 방향성 간선을 만들어, 간선의 개수가 $O(NK)$가 되는 DAG(Directed Acyclic Graph)를 만들 수 있다. Bellman-Ford 알고리즘을 사용하여 모든 쌍 $(i, j)$에 대해 DAG에서 경로가 있는지 미리 계산할 수 있다. DAG에서 $i$에서 $j$로 가는 경로가 있으면 $i$ 번 식물의 크기가 $j$ 번 식물의 크기보다 큰 것이고, 반대로 $j$에서 $i$로 가는 경로가 있으면 $j$ 번 식물의 크기가 $i$ 번 식물의 크기보다 큰 것이다. 둘다 경로가 없으면 두 식물의 크기를 비교할 수 없음을 의미한다.

 

다음 서브태스크들을 풀기 위해 필요한 관찰

위는 설명을 위한 다른 예시다. $K = 3$이며, $R[i]$에 적힌 값들은 처음 들어온 배열 $R$의 값이고, $H[i]$에 적힌 값들은 앞에 설명한 방법으로 구한 배열 $H$의 값이다.

 

이 예시에서 3번 식물과 9번 식물의 크기를 비교할 수 있는데, 왜냐하면 3번 식물의 크기는 5번 식물의 크기보다 크고, 5번 식물의 크기는 7번 식물의 크기보다 크고, 7번 식물의 크기는 9번 식물의 크기보다 크기 때문이다. 반면, 3번 식물과 10번 식물은 크기 비교를 할 수 없다.

 

3번 식물을 기준으로 오른쪽(원형에서는 시계방향)으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 5번 식물이 나온다. 5번 식물을 기준으로 오른쪽으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 7번 식물이 나온다. 이때, 7번 식물은 자명히 3번 식물보다 크기가 작으며, 7번 식물은 9번 식물과 충분히 거리가 인접하므로 크기 비교를 할 수 있고, 9번 식물은 7번 식물보다 크기가 작다. 이처럼 모든 식물에 대해 오른쪽 방향으로 자기와 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾는다. 마찬가지로 왼쪽 방향에 대해서도 진행한다. 이 과정은 set을 이용하여 $O(N \lg N)$에 구현할 수 있다.

 

서브태스크 6 (15 점)

항상 1번 식물과 다른 식물 $j$를 비교하는 질문만 들어오는 서브태스크다. 1번 식물에 대해 오른쪽으로 갈 때 나타나는 식물들의 순서와, 왼쪽으로 갈 때 나타나는 식물들의 순서를 미리 구한다. 주어지는 $j$에 대해 $j$보다 왼쪽에 있으면서 1번 식물에서 오른쪽으로 갈 때 나타나는 식물들 중 가장 $j$와 가까운 식물의 번호를 이분탐색으로 구한다. 그리고 그 식물과 $j$번 식물의 크기를 비교하여 $j$번 식물의 크기가 더 작다면 1번 식물의 크기가 더 크다는 뜻이다. 마찬가지의 확인을 왼쪽 방향에 대해서도 해준다. 이는 주어지는 질문을 $O(\lg N)$에 해결한다.

 

서브태스크 7 (25 점)

마지막 서브태스크다. 서브태스크 6에서 1번 식물에 대해 한 방향에 대해 나타나는 식물 순서를 미리 구하고 이분탐색한 과정을 sparse table을 이용해 공간복잡도 $O(N \lg N)$에 질문마다 시간복잡도 $O(\lg N)$에 해결할 수 있다.

 

더보기

'IOI > IOI2020' 카테고리의 다른 글

IOI2020 Day2 mushrooms 풀이  (0) 2020.09.24
IOI2020 Day2 biscuits 풀이  (0) 2020.09.23
IOI2020 Day2 stations 풀이  (0) 2020.09.23
IOI2020 Day1 plants 풀이  (0) 2020.09.22
IOI2020 Day1 tickets 풀이  (0) 2020.09.22
IOI2020 Day1 supertrees 풀이  (0) 2020.09.22
댓글
댓글쓰기 폼