순간이동 장치 (IOI 2008)

http://www.koistudy.net/?mid=prob_page&NO=2058

재밌는 문제..

텔레포터를 타고 여기저기 옮겨나간다는 문제의 개념이 상당히 당황스러울 가능성이 높다. 막히지 않으려면 "그래프"라는 사실을 빠르게 파악해야 한다. 나뉘어진 선분 구간은 정점이고. 텔레포트는 간선이라는 것을 관찰하면

* 경로 간선의 개수를 최대화

* indegree와 outdegree는 모두 1이다 (시작 끝점 빼고)

* 텔레포터의 설치는 두 정점 i, j의 나가는 간선의 교환이다

이 사실을 파악하면 문제가 상당히 깔끔해진다. 먼저 그래프의 성질을 관찰하자.

* 컴포넌트 내의 indeg / outdeg가 모두 1이면 컴포넌트는 사이클을 이룬다.

* 고로 그래프는 사이클 컴포넌트들의 집합이다.. 근데 시작 끝점은 indeg / outdeg가 0일 수도 있음.

* 시작점에서는 항상 끝점으로 갈 수 있으며, 그 중간에 있는 점들은 앞선 조건을 만족한다. 시작점과 끝점을 포함하는 단 하나의 컴포넌트는 직선이다.

이제 M개의 연산이 어떤 것인지 살펴보자.

* 간선 개수 C1, C2인 사이클 2개를 합치면 C1 + C2 + 2 크기의 사이클 1개가 생긴다.

* 간선 개수 C1, L2인 사이클과 직선을 합치면 C1 + L2 + 2 크기의 직선 1개가 생긴다.

* 사이클이나 직선 안에 텔레포트를 넣으면 크기가 1 증가하며, 크기 1의 사이클이 생긴다.

(직선 2개는 합칠 수 없음에 유의하자)

이제 문제가 아주 아주 간단해졌다. 크기 L의 직선과 사이클의 집합 S가 주어졌을 때 M개의 연산을 잘 사용해서 직선 길이를 최대화하는 것이 목적이다. 여기에는 쉬운 그리디 알고리즘이 존재한다.

* 먼저 사이클 2개를 합치는건 사이클과 직선을 2번 합치는 것보다 나쁘거나 비슷하기 때문에 그러한 연산은 없는 셈 쳐도 된다.

* 그러면 사이클과 직선을 합치거나, 텔레포트를 넣는 것이 유일한 선택지인데, 전자가 후자보다 항상 낫거나 비슷하다. 고로 두 연산 중 전자가 우선순위를 가진다.

* 자명히 크기가 가장 큰 사이클이 우선순위를 가진다.

이제 알고리즘을 제시할 수 있다. 크기 200만의 배열을 잡은 후 각각의 점에서 simulation을 통해서 사이클과 직선의 크기를 모두 구하자. 사이클은 큰 순서대로 정렬한 후, M개의 연산을 진행하면 된다. 코드는 아주 짧다. 갓문제!