Alien Trick과 구현시 팁

만약 Alien Trick에 대해 이미 알고 있다면 절취선 아래의 내용만 읽어도 도움이 될 것입니다.

Alien Trick이 알려지기 시작한 것은 IOI 2016 이후이며 아직까지도 많이 알려지지는 않은 알고리즘이다.
나 같은 경우 2019년에 Alien Trick을 공부하였는데 구현한 코드를 찾지 못하여 구현에 어려움을 겪었다.
이 글을 통해 더 많은 사람들이 Alien Trick에 대해 알았으면 좋겠다.
koosaga 님의 글 과 imeimi 님의 글 을 먼저 읽고 오면 좋다.

내가 KCPC 2020에 출제한 문제를 바탕으로 설명을 하겠다.
$Cost[i][j]$를 부분수열 $a[i...j]$에 존재하는 서로다른 수의 개수로 정의하자.
$dp[i][j]$는 부분수열 $a[1...j]$를 $i$개로 쪼갰을 때의 답으로 정의하자.
점화식은 $dp[i][j]=\max_{k<j}dp[i-1][k]+Cost[k+1][j]$ 이다.

이 때 $Cost[i][j]$가 Monge 이기 때문에 좌표평면에 점 $(1,dp[1][n]),(2,dp[2][n]),...,(n,dp[n][n])$의 꺾은선 그래프는 위로 볼록하다. 이 부분에 대한 증명은 구사과님의 포스팅을 참고하자.
이를 직관적으로 이해할 수도 있다. 수열을 쪼개는 횟수가 늘어나면 답이 증가하는데, 직관적으로 쪼개는 횟수가 1에서 2가 될 때보다 99에서 100이 될 때 답이 늘어나는 폭이 작을 것이다.
그래프에 접선의 기울기에 따라 대응되는 접점이 생기는데, 접선의 기울기가 감소할수록 접점의 $x$좌표가 증가한다는 것을 알 수 있다.

여기서 그래프의 접선의 기울기에 대해 이분탐색을 하여 접점의 $x$좌표가 $k$일 때를 찾는 것이 Alien Trick 이다.
접선의 기울기가 $\lambda$일 때 접점을 찾는 것은 $dp[x][n]-x\cdot\lambda$의 최댓값을 찾는 것과 동일하며 이는 수열을 쪼갤때 마다 $\lambda$ 만큼의 가중치를 빼야 한다는 뜻이다.
따라서 $dp[i]=\max_{j<i}dp[j]+Cost[j+1][i]-\lambda$라는 점화식을 계산하고 이 때 최적해를 만드는 쪼개는 횟수가 접점의 $x$좌표가 된다. 이는 dp를 역추적하는 유형의 문제와 비슷하게 계산할 수 있다.
따라서 점화식을 단순히 계산하면 $O(n^2\cdot \log n)$으로 풀 수 있고 점화식을 segment tree를 이용하여 계산하면 $O(n\cdot \log^2 n)$으로 풀 수 있다. 자세한 설명은 첨부파일을 확인하자.

solution_최종.pdf

0.47MB

---

문제는 한 접선에 대응되는 접점이 여러개일 수 있다는 것이다. 이를 해결하는 방법에는 여러가지가 있는데 가능한 접점중 가장 왼쪽을 택하는 것이 방법이 될 수 있다. 하지만 귀찮기도 하고 이 문제에서는 가능하지만 매우 힘들거나 불가능한 경우도 많다. 그 외에는 반정수 구간에서 이분탐색을 하거나 이분탐색을 두 번 하는 방법이 있다.

내가 쓰는 방법은 위의 방법보다 훨씬 간단하다. 일단 이분탐색을 진행하여 $\lambda=mid$ 일 때 답 ($dp[n]$) 이 $Ans$ 라고 하자.
결론부터 말하면 $Ans+mid\cdot k$ 의 최솟값이 정답이 된다.
$Ans$ 는 $dp[x][n]-mid\cdot x$ 의 최댓값이다. 즉 $Ans+mid\cdot k$ 는 $dp[x][n]+mid\cdot (k-x)$ 이다. 이는 $(x,dp[x][n])$ 에서 접선을 그었을 때 $x$ 좌표가 $k$ 일 때의 $y$ 좌표와 같으며 이는 항상 $dp[k][n]$ 보다 같거나 크다. 만약 접선의 기울기가 $(k,dp[k][n])$ 에서의 기울기와 같다면 $dp[k][n]$ 을 얻을 수 있다. 그림을 그려보면 쉽게 확인할 수 있다.

어디서 접선을 그어도 항상 k에서의 y좌표는 dp[k][n]보다 같거나 크다.

구현한 코드이다.