RUN@KAIST 7/16 방학 연습 풀이

1. 텔레점프

아이디어의 큰 틀은 생각보다 간단하다. 다만 이를 실제로 완성하는 건 꽤 까다로운 문제이다.

 * 먼저 처음에 A 에지 하나와 B 에지 모두를 소모해서, 앞 부분의 점을 다 연결 시켜준다. 1 - 2 / 1 - 3 / 2 - 4 / 3 - 5 ...

 * 이제 A 에지와 C 에지만이 남았다. B 에지로 만든 path의 두 끝 점 중 하나는 버리고 (즉 시작점으로 하고), 나머지 하나를 이어나갈 것인데, P / P + 3 / P + 6 ... 이런 식으로 이으면 중간에 공백이 생기니, A 에지를 하나 사용해서 P + 1 - P + 2를 이어주고, P + 1 / P + 4 ... 혹은 P + 2 / P + 5 ... 를 계속 이어준다. C 에지를 전부 소모할 때까지 이를 계속한다.

 * 남은 에지들은 시작점과 연결되어 있는 게 하나. 자기들끼리 연결되어 있는 게 두개가 있다. A 에지를 또 하나 사용해서 시작점과 연결되어 있는 쪽과, 자기들끼리 연결되어 있는 쪽을 붙여준다. 

 * 이 과정까지 정확히 3개의 A 에지를 사용했다. 남는 A 에지가 있다면, 그냥 맨 마지막에 쫘라락 붙여준다.

구현도 좀 까다롭다. 시간이 빡빡한 문제가 아니니까, high level한 방법을 총동원해서 구현하도록 하자.

2. Park

먼저, 방문자 원이 장애물 점을 피해서 움직인다고 생각하는 대신에, 방문자 점이 장애물 원을 피해서 움직인다고 생각하자. 최대 R의 원이 움직일 수 있다는 것은, 각각의 점의 반지름이 최대 R일 때도 움직일 수 있다는 뜻이기 때문이다.

각각의 점의 반지름이 최대 R일 때 방문자 점이 어떠한 위치에서 어떠한 위치로 움직일 수 있다는 것을 풀 때, 점의 관점에서 생각하면 빠른 알고리즘을 생각하기 쉽지 않다. 하지만 문제가 평면이기 때문에 재미있는 성질이 존재하는데, 방문자 점이 어떠한 위치 S에서 어떠한 위치 T로 움직일 수 없다는 것은, S를 포함한 영역과 T를 포함한 영역을 분리시킬 수 있다는 뜻이다. 

직사각형의 한 변에서 시작해서, 원을 타고 움직이고, 한 변에서 끝나는 경로를 생각해 보자. 만약에 이러한 경로가 존재한다면, S에서 T로 움직일 수 없다. 또한, S에서 T로 움직일 수 있다면, 이러한 경로는 존재할 수 없다. 고로, S에서 T로 움직이는 것과 경로가 존재하는 것은 동치이다. (조금 더 엄밀한 증명은 평면 그래프에 대해서 찾아 보는 것을 추천..) 고로, 직사각형의 네 변 중 하나에서 원을 타고 다른 변으로 갈 수 있는지를 판별해야 한다. 예를 들어, 1번에서 2번으로 움직일 수 없으려면, 1 - 2 사이에 있는 어떠한 변에서, 1 - 2 반대쪽에 있는 어떠한 변으로 움직이는 경로가 있어야 할 것이다.

일단 binary search를 통해서 R을 고정시키고 답을 찾는 아이디어가 있다. R이 가능한 답이면 그 이하는 항상 가능할 것이기 때문이다. 변 4개와 원을 N+4개의 정점으로 표현하고, 변과 원 사이 / 원과 원 사이의 거리를 계산해서 R 이하이면 에지를 이어주고 DFS로 경로를 찾으면 되기 때문이다. 이렇게만 해도 O(N^2lg(-eps)) 정도의 알고리즘이 나온다. (시간 안에 나오는지는 잘 모르겠다.)

이를 더 줄이기 위해서는, 각각의 변과 원 사이 / 원과 원 사이가 이어지기 위한 최소 R을 계산하자. 간단한 수식으로 O(1)에 계산한다면, 이제 R이 답이 된다는, 그래프에서 R 이하의 간선만을 사용해서 경로를 찾을 수 있다 와 동치다. 이 때, minimum spanning tree 상에 존재하지 않는 간선은 전혀 필요하지 않다. 고로 Prim Algorithm을 사용해서 N^2에 최소 스패닝 트리를 계산하고, 4^2개의 쌍에 대해서 O(N) 정도에 답을 계산하면 전체 문제를 O(N^2 + M)에 해결 가능하다.

3. Stretching Streamers

정수론에 대한 언급이 있어서 어렵다고 느낄 수 있지만, 쉬운 문제이다. gcd의 성질과 전혀 상관 없이 문제에서 어떻게 에지가 주어지든 경우의 수를 셀 수 있기 때문이다.

1번 정점과 연결된 정점이 하나 존재할 것인데, 이 정점을 v라고 하자. 이후 원호상에서 두 에지가 교차하면 안되기 때문에, 1 - v 간선 왼쪽에 있는 스패닝 트리와 오른쪽에 있는 스패닝 트리는 완전히 독립적이다. 나누어진 영역에서 스패닝 트리를 구하는 것은, 1번 정점이나 v번 정점을 루트로 했을 때, 거기서 연결된 정점 하나를 고정하고 계속... 그렇다면, 동적 계획법을 사용해서 구할 수 있지 않을까?

예상대로 동적 계획법으로 해결 가능하다. 먼저 1번 정점과 연결된 가장 번호가 작은 정점을 v라고 하면, 이제 : 

 * 2번 정점에서 v번 정점을 영역으로 하고, v번 정점이 루트인 스패닝 트리

 * v번 정점에서 n-1번 정점을 영역으로 하고, v번 정점이 루트인 스패닝 트리

두 개를 계산하면 되고, 부분 문제들 역시 동적 계획법으로 재귀적으로 해결할 수 있다. DP 점화식 상태는 원호 상 구간과, 루트가 구간의 어느 쪽에 있는지로 정의된다. 즉, DP[구간 시작, 구간 끝, 루트가 왼쪽 끝인지 오른쪽 끝인지] 의 형태이다. 상태 전이는 루트와 연결된 가장 번호가 작은 정점을 고정시키면서 구해 나가면 된다. 문제가 원형이긴 하지만 실제로는 구현에 전혀 상관 없다.