JOISC 2020 연습 (8/3~8/15)

IOI 국가대표 선발고사에서 폭사한 이후, 기말고사 기간 동안 PS를 전혀 잡지 않았다.

APIO 준비를 위해 재활훈련을 필요로 했기에, 기말이 끝난 이후인 8/3부터 BOJ에 1인그룹을 만들어 JOISC 2020의 여섯 문제를 따와 연습을 했다.

 

 

그룹 이름과는 달리, 막 열심히는 하지 말고, 그냥 시간 나는대로 몇문제 풀려고 풀었다.

 

처음에 6문제를 연습에 넣었고, 2주간 위의 4문제와 추가적으로 IOI19의 Rectangles를 풀었다. (솔직히 Ruins 3에 시간을 좀 많이 갈았는데, 좀 아깝다는 생각도 든다)

 

시간투자도 많이 안하고, 중간에 1달 정도의 공백기가 있던 것을 감안하면 어느정도 감을 되찾았다고 생각한다.

 

JOISC 2020 Day 4 Capital City

 

최종적으로 도시들을 합병했을 때 문제의 조건을 만족하는 도시에 x번 마을이 포함된다고 하자.

그러면 x번 마을을 포함하면서 문제의 조건에 맞도록 최소 횟수로 합병한 도시는 $O(N)$에 구할 수 있다. x번 마을이 포함된 도시의 마을들 사이에 위치한 마을들의 도시를 합병해주고, 새로 합병해준 도시의 마을들에 마찬가지로 위 동작을 반복하고... 하다보면 자명하게 x번 마을이 포함되며 최소 횟수의 합병을 진행한 도시를 구할 수 있다.

 

모든 마을에 대해 위 작업을 반복하면 당연히 $O({N}^{2})$가 걸릴 것이다.

여기에 센트로이드 분할을 적용하면 이를 줄일 수 있다.

처음에 전체 트리의 센트로이드에 대하여 위 작업을 시행하고, 센트로이드를 기준으로 트리를 분할하여, 각각의 서브트리에 대해서도 마찬가지로 센트로이드를 잡아서 위 작업을 시행하는 것을 반복하면 된다.

 

$f(x) = 2f(x/2) + O(x)$이므로, 마스터 정리에 의해 최종 시간복잡도는 $O(NlgN)$이다.

 

 

JOISC 2020 Day 4 Treatment Project

 

영역이 맞닿아 있거나 겹치는 두 계획에 대해, i번 계획에서 j번 계획으로 C[j]의 비용을 사용하여 '이동'한다고 하자.

그렇다면, 이 문제는 1번 시민을 포함하는 계획에서 N번 시민을 포함하는 계획으로 '최소 비용을 사용하여 이동'하는 최단 경로 문제로 바뀐다.

 

계획들을 노드로 놓으면, 영역이 맞닿아 있거나 겹치는 계획들 사이에 간선이 생긴다.

간선은 최대 $O({M}^{2})$개 이므로, 처음에 간선을 전부 다 구해놓으려고 한다면 당연히 TLE가 뜰 것이다.

이 때, 다익스트라에서는 한 번 방문한 노드는 다시 방문할 필요가 없으므로, 좌표압축과 세그먼트 트리 등 적절한 자료구조를 사용하여 간선을 $O(M)$개만 보게 할 수 있다.

 

나는 좌표압축과 펜윅 트리를 사용하여 $O(MlgM)$의 시간복잡도로 구현하였다.

 

 

IOI 2019 Day 1 Rectangles

 

두 가지 관찰이 필요하다.

1. ${x}_{1}<i<{x}_{2}$인 $i$에 대해 $a[i][y] < min(a[{x}_{1}][y], a[{x}_{2}][y])$인 $({x}_{1}, {x}_2, y)$, 또는 ${y}_{1}<i<{y}_{2}$인 $i$에 대해 $a[x][i] < min(a[x][{y}_{1}], a[x][{y}_{2}])$인 $({y}_{1}, {y}_{2}, x)$를 페어라고 하자. 행과 열 각각에 대하여 전체 페어의 수는 $2NM$을 넘지 않는다.

열에 대해서 보자. 페어에서 ${x}_{1}$, ${x}_{2}$중 작은 쪽을 고정해서 보면, 큰 쪽은 '자신보다 작지 않은 원소 중 좌우로 각각 가장 가까운 원소'로 좌우로 각각 유일하게 정해진다. 따라서, 한 행에서는 최대 $2M$개의 페어가 발생한다.

행에 대해서도 마찬가지로 최대 $2N$개의 페어가 발생한다.

 

2. 문제에서 구하는 유효한 영역은 $NM$개를 넘지 않는다.

유효한 영역에서 가장 큰 원소를 고정하자. 이 때의 유효한 영역은 최대 한 개이다.

이 원소의 위치를 $(x, y)$라고 하자. $a[x][y]$보다 크면서, 상하좌우로 가장 가까운 원소를 각각 $({x}_{1}, y)$, $({x}_{2}, y)$, $(x, {y}_{1})$, $(x, {y}_{2})$라고 하자. 이 때, ${x}_{1} < i < {x}_{2}$, ${y}_{1} < j < {y}_{2}$인 영역이 유일하게 유효한 영역이 될 수 있는 후보이다.

위의 영역보다 넓다면, $a[x][y]$보다 큰 원소가 영역 안에 존재하므로 $a[x][y]$가 영역에서 가장 큰 원소라는 가정이 무너진다. 위의 영역보다 좁다면, 영역 내부의 원소들은 영역 경계의 원소들보다 작다는 문제 조건에 어긋나므로 유효한 영역이 될 수 있다.

 

$O(NM)$의 전처리를 통해, 1의 모든 페어와, 2의 모든 원소에 대한 상하좌우로 가장 가까운 원소를 각각 구해줄 수 있다. 적절한 정렬과 이분탐색을 통해 $O(lgNM)$에 각각의 원소에 대하여 2의 방식으로 구한 영역이 유효한 영역인지를 확인할 수 있다.

 

최종 시간복잡도는 $O(NMlgNM)$이다. 시간제한이 빡빡하므로, 상수 최적화에 주의하여야 한다.