NegativeGraphDiv1

Problem Description

TopCoder Link(doesn't require login)

Idea

charge가 작은 경우에는 그냥 경우의 수를 모두 계산해서 문제를 풀 수 있다. D[c, s, e] := c개만큼 charge를 사용해서 s부터 e까지 가는 데 드는 최소 비용. 이라고 정의하고 DP로 풀면 됨. 다만 c가 꽤 큰 문제이기 때문에, 이걸 그대로 적용하진 않고, 다음과 같은 경우가 성립할 거라고 가정했다.(오른쪽 반례 부분은 추후 설명함)

Image hosted for free at CtrlV.in

즉, 답 S = {p_0, p_1, p_2, ... p_m}$S = {p_0, p_1, p_2, ... p_m}$ 라고 가정할 때, 그 중 어딘가(p_i$p_i$라고 부르자)에서 동일한 사이클을 여러번 돌고 그 다음 목표지점으로 이동하는 방식으로 답이 구성될 거라는 가정을 세워 봤다. 이때 p_0$p_0$부터 p_i$p_i$까지의 중간 점의 갯수는 N 이하일 것이고, 또 p_i$p_i$에서 뺑뺑이 도는 사이클의 크기도 N 이하일 거라고 판단했다. 왜냐하면 N보다 커지면 같은 점을 두번 방문하는 꼴인데... 그렇게 되면 또다른 사이클이 존재하게 되는 셈이니 처음 가정에서 벗어나기 때문이다.

실제 풀이 코드

https://gist.github.com/blmarket/84bc3ae1941242a06a70#file-negativegraphdiv1-fail-cpp

당당하게 N 이하일 거라고 가정했지만, 넉넉한 버퍼를 뒀다. 일단 c=0..120$c=0..120$까지 계산을 수행하고, i$i$가 100 이하, 사이클의 길이가 100 이하인 모든 경우에 대해 계산해보도록 했다.

반례

위 그림에서 같이 적어놓았듯, 사이클이 딱 한종류로만 존재할 거라는 가정이 틀렸다. 생각해보면 위의 base idea는 charge의 갯수가 특정 interval일 때에만 올바른 답을 제공하게 된다.

Image hosted for free at CtrlV.in

따라서 여러 가지 다른 cycle을 섞어서 charges에 맞게 사용할 때 더 좋은 답안을 얻을 수 있게 된다. 기본 가정 자체가 틀렸으니 이건 뭐 땜빵으로 해결할 수 없는 FAIL!

정답 풀이

실은 c가 커져도 DP 대신 matrix multiplication의 아이디어를 적용해서 풀면 바로 계산해낼 수 있음. 제가 짠 코드 말고도 연습방에 좋은 풀이가 많습니다.

https://gist.github.com/blmarket/84bc3ae1941242a06a70#file-negativegraphdiv1-success-cpp

Written with StackEdit.