APIO 2016

(5.14 첫 작성)

대회때 100 / 26 / 100점을 받았다.

http://apio2016.org/results/

Problem 1. Boat

처음 봤을 때 어려워 보이지는 않았고, 어쨌든 대회 시간 안에 풀수 있을 것이라 생각했다. 실제로도 아주 어려운 문제는 아니었지만, 완전히 잘못된 풀이에 낚여서 1시간 이상을 허비한 게 아직도 아깝다. 그걸로 코딩까지 했으니 원.. 틀린 아이디어를 완전히 버리고, subtask를 읽어나가면서 차근 차근 다시 생각하니, 이 때는 쉽게 풀렸다.

먼저 편의상 interval을 [ai, bi+1) 형태로 처리하자. 이러한 형태의 문제에서 가장 큰 걸림돌은 구간의 길이가 크다는 것이니, 어떠한 긴 구간을 빠르게 처리할 수 있는 방법을 고민해봐야 한다. 좌표 압축을 통해서, 구간에서 의미 있는 시작 / 끝 점을 2N개만 남기고, 그 안에 속하는 긴 수들을 빠르게 처리하는 알고리즘을 고안하자.

DP[i][j] = j번째 보트를, [0, i) 시간(압축됨) 에 구매하는 방법 이라고 점화식을 세우자. DP[i]에서 DP[i+1]을 유도하기 위해서, DP2[j][k]를 정의한다. DP2[j][k] = [i, i+1) 시간에 k개의 보트를 골랐고, 마지막은 j번 보트인 조합의 수 라고 하자.

구간 [i, i+1) 의 길이를 L이라고 하면,

DP2[j][k] =

Sum(DP[i][l]) * L for all l < j (if k == 1)

max(L - k + 1, 0) / k * Sum(DP2[l][k-1]) for all l < j (otherwise)

나눗셈은 modular inverse질로 해결 가능하고, 잡다한 summation은 부분 합을 적절히 쓰면 된다. 대회 때 나는 조합의 수가 아니라 순열의 수를 세고, 마지막에 factorial inverse로 나눴다. DP2를 알면, 자명히 DP 배열을 변화시킬 수 있다. 시간 복잡도는 O(N^3)이다.

cpp : https://github.com/koosaga/olympiad/blob/master/APIO/apio16_boat.cpp

Problem 2. Fireworks

3번과 1번을 모두 풀고 2시간 남짓 남았을 때 봤던 문제다. 답을 고정시키는 방법으로 접근했는데, 전혀 도움이 안되는 것을 확인하고, 도저히 어떻게 접근해야 할지 감을 못 잡았다. 답을 고정시키는 방법에서 탈피하니 26점 풀이가 보였고, 이 풀이대로라면 55 - 100점까지도 어떻게 할 수는 있겠다 싶었지만, 55점 이상으로 가면 코딩이 말도 안될 거 같아서 도저히 AC를 받을 자신이 없었다. 그래서 걍 남은 시간동안 존x 가만히 있었다..

몇주 뒤 다시 생각해 볼 일이 있어서 열심히 고민했고 결국 풀었다. 내 풀이는 O(Nlg^2N)이며 O(NlgN)으로 줄일 수 있는 풀이이다. 상당히 어려운 문제이지만 코드 자체는 상당히 간단하다. 열심히 설명했지만 충분히 고민해보지 않았다면 이해하기 힘든 풀이일 지도 모른다 (그림이 없어서 특히..) 먼저 26점 풀이부터 차근차근 설명하도록 하겠다. (7점 풀이가 궁금하다면.. Ci 중앙값 찍으면 된다.)

26점 풀이는 dynamic programming과 비슷한 원리로 작동한다. 각각의 노드 v마다 다음과 같은 배열을 기록하고 관리한다.

 * dp[x] = v의 subtree 상의 에지 cost를 조정하여, 루트에서 v의 subtree의 모든 노드까지의 거리를 x로 만들고자 할 때 드는 최소 비용.

이제, 각각의 노드마다 dp 값의 변화를 보자. 일단, 리프 v에서, dp 값은 v일 때 0이고, 아닐 때 모두 infinity이다. 리프 아닌 정점 v에서, dp 값은 일단 자식 노드들의 dp 배열들의 합인데, 이 때, 자식 노드가 C[i] 만큼의 에지를 타고 올라오기 때문에 dp값에 변화가 있어야 한다. 정확히는 다음과 같은 변화가 생긴다.

 * dp[x] = min(dp[y] + y - x) if(x <= y <= x + C[i]) (에지의 값을 y - x만큼 줄이는 것에 대응된다)

 * dp[x] = min(dp[y] + x - y) if(y <= x) (에지의 값을 x - y만큼 늘이는 것에 대응된다)

이러한 변화는 쉽게 300^2에 가능하기 때문에, dp[x]를 O(N * 300^2) 에 해결하면 26점이 나온다.

55점 이상을 노리려면 dp 값을 효율적으로 계산해야 한다. 이 때 먼저 관찰할 수 있는 것은, dp 배열이 일차 함수들의 조합이라는 점을 알 수 있다. 어떠한 구간에서는, ax + b 꼴의 값을 가지고, 어떠한 구간에서는 cx + d 뭐 이런식.. convex hull trick을 생각하면 이해가 쉬울 것이다. 또한, 이 dp 배열은 볼록 함수의 형태를 띄고 있다.

이제, 일차 함수 그래프를 잘 관리하면서, 두 일차함수를 더해주고, 에지를 타고 올라올 때 연산을 잘 적용해주면 문제가 풀림을 알 수 있다. 적절한 구현으로 일차함수를 더해주는 것은 선형 시간에 가능하니, 연산 적용 방법에 대해서 알아보자, 

 * 기울기 1 초과의 직선들은, 모두 기울기 1로 줄어든다.

 * 기울기가 -1인 직선이, -1 미만 직선 / -1 초과 직선 사이에 들어간다. 이 직선의 기울기는 x축 기준 c[i]이다.

이렇게 해서 일차함수를 더해주는 것 + 연산 적용이 선형 시간에 가능해 지니, 함수 하나 더할 때 마다 선형 시간이 걸리고 고로 O((N + M)^2) 의 시간에 이 문제를 풀 수 있다. 이렇게 해결하면 55점이 나올 것이라 추정. 대회 당시 이정도까지 생각은 했지만 구현할 엄두는 안 났다 (실제로 55점 득점자가 별로 없다.)

하지만, 위에서 서술한 55점 풀이는 단순히 구현이 짜증날 뿐만 아니라 일차함수를 더하는 과정에서 O(N + M)이라는 시간이 필연적으로 들 수밖에 없다는 단점이 있다. 100점을 하기 위해서는 저러한 일차함수의 표현 방법을 뒤집어야 하고, 각종 연산들을 빠른 시간 안에 처리해야 한다.

여기서 사용할 수 있는 아이디어는, 기울기가 +1씩 변하는 지점들을 적절한 자료구조에 저장해놓는 것이다. 여기서 그러한 자료구조로는 priority queue를 사용한다. 기울기가 변하는 점 모두 정수 좌표며, 기울기가 모두 [-서브트리의 리프 개수, 서브트리의 리프 개수] 사이의 정수이기 때문이다. 왜 그런지는 서브태스크 1과 같은 star graph를 그려보고 dp[] 그래프가 어떻게 나오는지 감상하면 알 수 있다.

지점을 저장할 때는, "상대적인 위치"로 저장하자, 노드 v에서의 dp[] 함수는 depth[v] 이상에서만 정의될 것이다. priority_queue에는 실제 위치 -  depth[v] 값을 저장해 놓는 것이다. 또한, depth[v] 지점에서의 함수의 값과, 현재 기울기를 알고 있어야지, 나머지 값도 구할 수 있을 것이니, 이 값 역시 적절히 저장해 놓는다.

이제, 다시 연산들을 검토해보자.

 * 일차함수를 더해줄 때는, depth[v] 값이 모두 똑같으니 priority_queue를 합쳐주면 된다.

 * 에지를 타고 올라올 때, 아주 깔끔하게 문제가 해결 된다. 끝의 기울기가 1 초과일 때까지 priority_queue에서 기울기 바뀌는 점을 제거하고, (즉, 기울기가 안 바뀐다고 생각) 두개의 원소를 뺀 다음, (기울기 0 / 1을 대변), 두개의 원소에다가 C[i]를 더해서 넣는다. 그림을 그려보면 이 연산과 위에서 설명한 연산이 같음을 알 수 있다.

priority_queue 를 합치는 데는 http://amugelab.tistory.com/entry/Dispatching-APIO-2012 의 요령으로 O(Nlg^2N)에 가능함을 알 수 있다. 연산 적용 시에는 모든 원소가 많아야 한번 사라지니 역시 O(NlgN)에 가능하다. 고로 총 시간 복잡도 O(Nlg^2N)에 문제가 해결된다. O(NlgN) 풀이도 있으며, 이는 위에 건 링크에서 Nlg^2N을 NlgN으로 줄인 방법 똑같이 하면 된다. 이렇게 복잡한 문제였는데 만점자가 있다니 놀랍.

cpp : https://github.com/koosaga/olympiad/blob/master/APIO/apio16_fireworks.cpp

Problem 3. Gap

인터랙티브라 상당히 당황스러웠던 문제. 쉬운지 어려운지 감이 안왔고 그냥 재미있어보여서 고민을 해봤는데, 그렇게 어렵지 않아서 금방 풀었다.

T = 1일 때는, 반복적으로 최댓값과 최솟값을 구하고, 구간에서 제거할 수 있다. 이 방법으로 모든 수를 구할 수 있고, (N+1)/2 개의 query로 답을 찾을 수 있다.

T = 2일 때는, 구간의 길이가 문제 풀이에 영향을 끼치게 된다. 이 때 쓸 수 있는 재미있는 아이디어는 답의 하한을 정해두는 것이다.

처음 길이 N의 쿼리로 구간의 최소 / 최댓값을 알아내면, 답은 무조건 T = ceil((Max - Min) / (N - 1)) 이상임을 알 수 있다. 이제, [S, S+T], [S+T+1, S+2T+1] .. 으로 반복적으로 구간에 질의를 날리자. 이를 통해서 해당 구간의 최댓값과 최솟값만을 추출할 수 있으며, 해당 구간의 최대 / 최솟값이 아닌 값은 알 필요가 없다는 사실 역시 알 수 있다. 근처의 최댓값 / 최솟값에 의해 bounded되서, 답이 T를 절대 넘을 수 없기 때문이다.

이 방법을 통해서 A[] 배열의 일부를 알 수 있고, 이는 답을 계산하기에 충분한 정보이다. 쿼리는 총 N번 날렸으며, 2N개의 원소를 포함하기에, cost는 정확히 3N이다.

IOI 2014 Game / 2015 Boxes처럼, 코딩이 극단적으로 쉬운 문제에 속한다. 그렇게 어렵지 않고, 아이디어만 있으면 되는, 좋은 문제다.

cpp : https://github.com/koosaga/olympiad/blob/master/APIO/apio16_gap.cpp