APIO 2015 Jakarta Skyscrapers 풀이

문제 보기

http://acmicpc.net/problem/10847

http://oj.uz/problem/view/APIO15_skyscraper

---

1. Problem Statement

\(N\) 개의 건물 위에 \(M\)마리의 도게가 있는데, 

각 도게는 한 번의 움직임으로 정확히 \(p_{0},p_{1},...p_{M-1}\)만큼 이동할 수 있다.

이 때 건물 \(s\)에서 시작해서 \(e\)로 릴레이하면서 갈 때, 점프의 최소 횟수를 알고 싶다.

---

2. Subtask2 - 36점 (\(N,M \le 2,000\))

Subtask1은 백트래킹이다. 짠 적도 없고, 설명하기 까다로운 만큼 넘어가자.

기본적으로 이 문제의 풀이는 다익스트라 알고리즘이다.

겨울학교에서 이 문제랑 비슷하게 생긴 문제를 못 푼 기억이 있어서인지 금방 떠올릴 수 있었다.

각각의 건물을 정점, \(i\)번째 도게가 있는 건물 \(b_{i}\)에서

\(b_{i}+p_{i}, b_{i}+2p_{i} ...\)

\(b_{i}-p_{i}, b_{i}-2p_{i} ...\)

의 점을 모두 에지로 이어 주면

정점 \(N\)개, 에지 worst case에 \(NM\) 개이므로

시간복잡도 \(O(NMlg(NM))\)

공간복잡도 \(O(NM)\)

으로 풀 수 있다.

---

3. Subtask3 - 57점 (\(N \le 2,000 , M \le 30,000\))

Subtask2의 풀이를 그대로 사용하면 메모리 초과가 발생한다.

생각해 보면 한 정점 \(v\)에 여러 마리의 도게가 있을 수 있고, \(v\)에서 출발한 두 도게가 다른 정점 \(u\)에 똑같이 도달할 수도 있다. 즉 multi-edge가 생길 수 있으며, 이는 명백한 메모리 낭비이다.

따라서 에지를 인접행렬로 관리해 주면서 정점 \(x\)에서 정점 \(y\)로 가는 가장 적은 cost를 에지 \(x\to y\)의 cost로 배정해 주면

정점 \(N\)개, 에지 worst case에 \(N^2\)개 이므로

시간 복잡도 \(O(NM+N^2lgN)\)

공간 복잡도 \(O(N^2)\)에 문제를 해결할 수 있다.

초기에 \(NM\)번, 즉 약 6000만 번의 에지 배정 연산을 처리해야 하는데, 연산이 복잡하지 않은데다 제한이 널널해서 1초 안에 통과할 수 있다.

---

4. Subtask4 - 100점 (\(N,M \le 30,000\))

시간을 더 줄이는 아이디어가 필요하다.

아이디어는 중복 에지를 최대한 잘라내 주는 것인데, 이게 점근적으로도 효과가 있다는 것을 보일 것이다.

한 번에 \(y\)만큼 뛸 수 있는 도게가 정점 \(v\)에 도착했는데, 정점 \(v\)에 똑같이 \(y\)씩 뛸 수 있는 도게가 있다면 이 둘은 완벽히 클론 관계이므로 두 정점에서 모두 에지 \(O(N)\)개를 만들 이유가 없다.

따라서 이렇게 이동 가능한 위치에 클론(?)이 있는 경우, 그 클론을 넘어서는 더 이상 에지를 뻗어주지 않으면 된다.

에지를 모두 저장해 두는 방식으로는 구현이 까다롭다. 다익스트라 알고리즘 내에서 갈 수 있는 정점을 체크해주면 간단하게 구현할 수 있다.

https://oj.uz/submission/27365

이래도 시간 초과가 발생한다면, 내 코드의 input()함수에서처럼 같은 건물 내에 있는 클론들을 unique()함수를 이용해서 중복 제거 처리를 해 주면 AC가 날 것이다.

\(p\)만큼 뛸 수 있는 도게가 서로 다른 위치에 \(p+1\)마리 이상 있으면, 비둘기집의 원리에 의해 이 도게들 중 서로 도달 가능한 위치에 있는 두 도게가 존재하게 되므로, 최대 \(p\)마리의 도게만 '유효하게' 작용할 수 있다.

이 때 \(x\)만큼 뛸 수 있는 도게의 마리수를 \(c(x)\)라고 하면,

총 에지 개수는

 \(\sum_{k=1}^{N}{\left\lceil\frac{N}{k}\right\rceil\times c(k)} \quad(c(k) \le k)\)

가 됨을 알 수 있는데, 그리디하게 \(k\)가 작은 쪽에 에지를 최대한 배정할 때 에지의 개수가 최대이다. 이 때 \(\sum{c(k)}=n\)의 제한 조건 때문에, \(k=O(\sqrt{N})\)까지만 채울 수 있다는 것을 알 수 있고, 때문에 에지의 개수는 총 \(O(N\sqrt{N})\)개이다.

시간복잡도 \(O(N\sqrt{N}lgN)\)

공간복잡도 \(O(N\sqrt{N})\)에 AC.

---