시간이 돈 (Balkan OI 2011)

http://oj.uz/problems/view/balkan11_timeismoney

처음에 이러한 문제를 딱 보고 생각이 난건, 한쪽의 sum을 고정시키고 진행하는 knapsack 류의 방법인데 (다익스트라가 그렇게 되니까) 해보면 알겠지만 Prim / Kruskal에서 그런 짓을 하는 거랑 다익스트라에서 하는 거랑은 느낌이 많이 다르다 (ㅜㅜ).

정점 V, 간선 E, max(t, c) = M = 255라고 하겠다.

O(ElgE * (VM)^2) / O(V^4M^2)

중요한 고찰이 필요하다. 나올 수 있는 모든 MST의 경우의 수를 (Sigma(T), Sigma(C)) 좌표 형태로 좌표평면에 찍었을 때, xy를 최소화하는 점을 골라야 한다. 최소인 점을 찾았다 치고, 그 점에서 y = T/x의 도함수 값을 y'라 할 때, 이 점은 y + y'x 역시 최소화한다. 이게 무슨말이냐 하면 모든 실수범위에서의 도함수의 경우를 나열하고 cost 함수를 저런 식으로 써서 MST를 구하면 된다는 거다. 실수를 전탐색한다는 게 참 웃기지만 뭐 일단 이렇게 하면 답은 나온다.. 그건 확실.

이제 답의 후보를 줄이자. 결론부터 말하면 답은 a / b 꼴이며 이 때 a, b <= VM이다. 이것의 증명은 자명해보이지.. 않다. 이제 이 경우들을 다 시도해서 MST를 구하면 됨.

O(ElgEVM) / O(V^3M)

결국 답의 후보를 줄이는 게 과제인데, 위에서 좌표 형태로 MST를 플롯했기 때문에 모든 좌표의 컨벡스 헐을 구하고 그 안에서 뒤지면 될 것 같다는 직감을 받을 수 있다. 컨벡스 헐의 크기는 O(VM)일 테니까 이제 이걸 할 수만 있다면 완벽하다. 물론 좌표의 크기가 지수적이니.. 여기서 아주 이상한 재귀적 방법을 사용한다.

먼저, t만을 최적화한 점과 c만을 최적화한 점을 구한 후, 이 두점을 s, e라 하고 재귀함수를 돌리자. 두 점을 잇는 일차함수를 최적화하는 점인 m을 O(ElgE)에 찾을 수 있고, 만약 그 점이 컨벡스 헐 안에 들어가면 [s, m] / [m, e]에서 또 계속 돌리자 계속.. 이렇게 하면 O(VM)개의 컨벡스 헐 후보를 모두 구할 수 있다. 유의미한 후보 중 구해지지 않는 후보는 없다.

실제로는 후보가 오더보다 많이 적어서 적은 것보다 훨씬 빨리 돌고 무튼 이렇게 하면 AC가 뜬다. 위에서 요구했던 증명은.. 컨벡스 헐 상에서 양 옆으로 인접한 두 점의 기울기를 생각해 보자.

사실 이 문제는 말로 하는 것 보다 코드가 더 나을 것 같다.. https://github.com/koosaga/olympiad/blob/master/Balkan/balkan11_timeismoney.cpp

또한 공식 풀이에 visualization이 아주 잘 되어 있으니 그것도 참고 http://www.boi2011.ro/resurse/tasks/timeismoney-sol.pdf

첨언

대회 때 이런 문제가 나왔고 데이터가 적당히 약해보인다면 simulated annealing을 시도하는 것도 나쁘지 않아 보인다.

여담으로 pseudopolynomial이니 아마 실제로는 np일거 같다.