IOI Aliens에 나온 optimization에 관하여

이 글의 대부분의 내용이 https://koosaga.com/243 에 재작성되었으니, 확인해 보는 것을 추천한다.

[2017.07.29 초판]

[2017.11.10 증명 추가]

IOI 2016에 출제된 Aliens 문제의 해법에서는, 굉장히 독특하면서 다양한 문제에 적용될 수 있는 최적화 기법이 나왔다. Aliens 문제와 비슷한 몇 개의 문제를 통해 이 기법을 설명하려 한다.

#1. Aliens (IOI 2016 Day2 Problem3)

먼저 이 문제의 최적화 방법을 알기 위해서는 O(nk) 풀이를 알고 있어야 한다. 이 풀이에 대해서는 전명우님의 블로그에 서술되어 있다. 고로 여기서 설명하지 않는다.

O(nk) 풀이를 보면, 다음과 같은 특징이 있다.

• k가 커질수록 답은 항상 감소한다. 
• k에 대한 조건이 없다면, O(n)에 문제를 해결할 수 있다. k에 대한 인자를 빼고 O(n) dp를 구하면 되기 때문이다. 
• k가 커질 수록 답이 감소하니. 이 dp는 분할을 최대한 많이 하려 할 것이다.

여기서 아주 독특한 생각을 한번 해 보자. k에 상관없이 문제를 해결할 때. dp(i) = dp(j) + cost(i+1, j) 형태의 점화식이 나온다. 이를 cost(i+1, j) + inf로 바꾸면 어떻게 될까? 처음에는 최솟값을 만들기 위해서 최대한 사진의 개수를 크게 하려 하겠지만, 이 때부터는 사진을 찍는 데 있어서 비용이 너무나도 커진다. 고로 inf가 충분히 크다면 단 하나의 사진만이 찍힐 것이다. 즉 모든 외계인이 한 사진에 속하게 될 것이다. 

이를 일반화 해서 비용을 cost(i+1, j) + lambda라고 하자. lambda가 0인 경우는 사진 개수가 최대한 커질 것이고, inf인 경우는 사진 개수가 최소화 될 것이다 (k = 1). 더 나아가서, lambda가 커지면 사진 개수는 감소할 것이다. 그렇다면, 아주 절묘한 lambda를 잡아서, 사진 개수가 정확히 K개 찍히는 게 최적인 순간을 포착했다면 어떻게 될까? 이 때의 총 cost를 Ans라고 하면, Ans - lambda * K의 비용이, K개의 사진을 찍는 최소 비용임을 알 수 있다. 고로, 절묘한 lambda를 찾으면 답을 구할 수 있다! 

그렇다면, 절묘한 lambda를 항상 찾을 수 있을까? 앞서 말했듯이 K는 lambda에 대한 감소 함수이다. 고로 최적 사진 개수가 K 이하인지 초과인지로 이진 탐색을 하는 접근이 매력적일 수 있다. 하지만, 유감스럽게도 lambda가 감소 함수라는 것 만으로는 아직 부족하다. 본인 역시 TCO R2C Hard에서 잘못된 문제에 이러한 접근을 사용해서 실패했는데, 만약에 lambda에 대한 최적 사진 개수가 10 10 10 8 8 3 3 3 1 1 1 .... 과 같이 일부 값이 누락된 꼴로 나온다면, 예를 들어, 정확히 2개의 사진을 썼을 때의 값을 알 수 없다. 예시로. K = 1일 때 15, K = 2일때 13, K = 3일 때 4 일 경우, K = 2를 계산하는 적당한 lambda가 있는지 찾아보자!

하지만. 다행이도 이 문제에 대해서는 저러한 걱정을 하지 않아도 된다. 이는 바로 K에 대한 최적 해의 함수가 볼록하다는 것이다. (lambda에 대한 K의 함수가 아니다. 헷갈리지 말자) 위에서 적은 "반례"의 경우는 볼록 함수가 아니기 때문에, 이 문제에서 고려하지 않아도 괜찮다. 이 성질은 일견 직관적인 것이, 그리디하게 생각하면, 하나의 사진을 더 찍을 때 최대한 변화량을 크게 해서 사진을 찍으려 할 것이고, 고로 앞에서 적은 변화량이 나오다가 뒤에서 큰 변화량이 나오는 것은 직관적으로 이상하다. 엄밀한 증명하고는 거리가 상당히 있지만 이러한 문제의 볼록성 증명이 쉬워 보이지 않아서, 이러한 직관을 가지고 찍는 게 (...) 최선인 것 같다. 아니면 naive한 풀이를 짜고, assertion을 넣어서 서브태스크 / 랜덤 데이터에서 테스트 해보거나.. 만약 cost 함수가 사각 부등식 (Quadrangle Inequality) 를 만족한다면, 항상 K에 대한 최적해의 함수가 볼록하다! 이 증명에 대해서는 아래 첨부 파일의 3절을 참고하라.

201711.pdf

한편, 볼록 함수 꼴의 최적해에서 cost + lambda를 최적화 한다는 것은, -lambda 기울기의 접선을 그은 것으로도 해석할 수 있다. 만약이 접선이 한 점에 닿는다면, 그 점의 K가 답이 될 것이고, 변에 닿는다면, 변이 이루는 K의 구간 중 하나가 답일 것이다 (맨 앞인지, 뒤인지, 랜덤한지는 구현 종속적일 것이다) 만약 랜덤함을 가정한다면, 정수 lambda 뿐만 아니라, 0.5 + lambda 기울기도 봐 줘야 한다. K 이하의 값이 나온 최소 lambda를 찾자. 이 직선 안에 K에 대한 해가 있다. 고로 여기에 K * lambda를 더해주면 답이 된다.

이러한 방식으로 해결하는 문제들에는 다음과 같은 예시가 있다.

• CF Round #351. Levels and Regions (당시 의도된 풀이는 O(nk)였다.)
• POI 2012/2013. Laser (역시 당시 의도된 풀이는 O(nk)였다.)

#2. Blazing New Trails (NAIPC 2017)

연결된 그래프가 있고, 각각의 에지가 A 타입이거나 B 타입일 때, A 타입의 에지를 정확히 K개 사용하는 최소 스패닝 트리를 구하는 문제이다. 이 문제 역시 Aliens와 비슷한 방법을 통해서 풀 수 있다. 하지만 DP 타입의 문제가 아니니 이 방법이 자명하지는 않다. 일단 위에서 얘기한 k에 대해서 답이 어쩌구 저쩌구가 전혀 통하지 않기 때문이다.

어떠한 식으로 접근해야 할까? 이번에는 lambda를 B 타입 에지의 cost에 주자. 즉, A 타입 에지의 cost는 그대로 두고, B 타입 에지의 cost에 lambda를 더한 후의 스패닝 트리의 구성이 어떻게 되는 지를 살펴 보는 것이다. 이 때 lambda가 -inf라면, B 타입 에지의 개수가 최대화 될 것이고, lambda가 inf라면, A 타입 에지의 개수가 최대화 될 것이며, B 타입 에지의 개수는 lambda에 대한 감소 함수이다. 고로, 이번에도 절묘한 lambda를 찾아서, B 타입 에지가 K개 사용된 스패닝 트리를 찾았다면, Ans - lambda * K가 답이 될 것이다. 

역시 lambda가 감소 함수라는 것만으로는 부족하다. lambda에 대한 최적 B 타입 에지 개수가 10 10 10 8 8 3 3 3 1 1 1 .... 과 같이 일부 값이 누락된 꼴로 나올 가능성이 여전히 있기 때문이다. 볼록 함수에 대한 논의가 불가능하니, 이번에는 이 딜레마를 다른 방법으로 타개해야 하는데, 대충 이런 명제를 증명하면 된다.

eps를 아주 작은 양수라 하자. lambda = X - eps일 때 B 타입 에지가 최소 스패닝 트리에 K1개, lambda = X + eps일 때 B 타입 에지가 최소 스패닝 트리에 K2개라면, lambda = X일 때 B 타입 에지가 K2개, K2 + 1개, K2 + 2개... K1개인 최소 스패닝 트리를 모두 만들 수 있다.

이 명제의 증명은 다음과 같이 할 수 있다. 편의상 A 타입 에지, B 타입 에지로 minimum spanning forest를 만들었다고 치면 (즉, MST에 절대 안 들어갈 비싼 에지들을 전부 제거), X - eps일 때, 그리고 X + eps일 때 스패닝 트리가 유일하다. 또한, lambda = X + eps일 때 존재하는 B 타입 에지들은, lambda = X - eps일 때 무조건 존재한다. (아니라고 하면 모순).

lambda = X에서 Kruskal algorithm을 돌렸다고 했을 때, (같은 가중치일 때) B 타입 에지를 우선적으로 처리하면 K1개, A 타입 에지를 우선적으로 처리하면 K2개의 B 타입 에지가 남을 것이다. K2 + t개의 B 타입 에지를 가지는 스패닝 트리를 만들고 싶다면, MST에 새로 추가되는 K1 - K2개의 B 타입 에지 중 t개의 에지를 골라서, 이들을 A 타입 에지보다도 우선적으로 처리하자. 즉 우선 순위가 "선택된 B 타입 에지 < A 타입 에지 < 나머지 B 타입 에지" 이다. 선택된 에지들은 당연히 추가될 것이고, 나머지 B 타입 에지도 최소 K2개는 처리될 것이다. 고로 K2 + t개의 B 타입 에지를 가지는 최소 스패닝 트리가 존재한다.

이러한 방식으로 해결하는 문제들에는 다음과 같은 예시가 있다.

• Japan Domestic 2015. Bridge Construction Planning
• AGC 018. Coins