Monday, July 21, 2014

APIO 2010 Commando 해법(Solution)

Link : APIO 2010 English Problems APIO 2010 Korean Problems

Source Code



S(n)을 x라 하면 y = f(x) = 2aS(i)S(x)+aS(i)^2+bS(i)+f(i)는 기울기가 -2aS(i)인 일차함수가 된다. S(i)는 increasing sequence이고 a < 0이므로 -2aS(i)는 monotonic increasing하게 된다. 그러면 새로 추가되는 (i)번째 선분에 대해서, (i-2)번째 선분과 (i-1)번째 선분의 교점 x값보다 (i-2)번째 선분과 (i)번째 선분의 교점 x값이 작거나 같다면 (i-1)번째 선분은 필요가 없게 된다. 이런 과정을 반복하다가 최종적으로 마지막 선분에 x = S(n)을 대입해주면 답 f(n)을 구할 수 있다. 이러한 기법을 Convex hull Trick이라고 한다.

PEGWiki's Convex hull trick

No comments:

Post a Comment