CCC12 Stage 2 - The Winds of War

http://wcipeg.com/problem/ccc12s2p6

먼저 아군과 적군은 cost 1, cost -1의 점으로 생각할 수 있으니 같이 생각하자.

문제는 (0,0) 점에서 시작해서 돌아오는 polygon을 만들고 안에 들어있는 cost의 합을 최대화 하는 문제이다. 세 점이 한 직선에 없어서 깔끔한 문제.

* N <= 100

먼저 polygon의 점들은 모두 들어오는 점의 부분집합이라는 걸 관찰하면 dp를 돌릴 수가 있는데,

점들을 모두 counterclockwise 순으로 정렬한 후 ccw(a[i], a[i+1], a[i+2]) > 0인 체인을 쭉 만드는 문제로 생각하자.

Sum[j][k] = (A[j] - A[k] - 원점 안에 들어있는 점의 가중치합) 라고 하면

이제 동적 계획법을 돌리는데 DP[i][j] = Max(j < k) DP[j][k] + Sum[j][k] + A[j].cost 라고 돌리면 되고

Sum과 DP 배열을 N^3에 계산하면 됨.

* N <= 1000

이 부분이 약간 어려운데 Sum[j][k]에 대해서 먼저 얘기해보자.

Sum[j][k]를 더 엄밀히 말하자면 (j < i < k && CCW(a[j], a[k], a[i])) 를 만족하는 점들인데

j < k인 점들에 대해서 a[j] 기준 counterclockwise 순으로 정렬을 쭉 해주면, CCW를 볼 필요가 없고 j < i < k 인지만 고민하면 된다. CCW 순으로 정렬했으니 Binary Indexed Tree랑 섞으면 N^2lgN에 해결 가능

DP 배열을 빠르게 계산하려면 위 식에서 j를 기준으로 생각해보자. 중간점 말이다.

j가 감소하는 순으로 계산을 해주면 DP[i][j] = Max(j < k) DP[j][k] + Sum[j][k] + A[j].cost라는 식에서 DP[j][k]는 다 계산이 되어 있을 것이다.

이제 j보다 인덱스가 작은 점과 큰 점을 모두 ccw 순으로 정렬을 하면.. 이게 참 말로 하기가 뭣한데 아무튼 해집합이 CCW상 연속된 집합으로 들어가며, 이 집합은 항상 증가한다 라고 할 수 있다.

그래서 Max값을 그냥 들고 다니면서 inchworm처럼 하면 됨. 코드 보는게 더 빠를 듯.

cpp : https://gist.github.com/koosaga/da1b2a7669c7d83554b6

여담으로 람다 식과 range based loop를 쓰니까 확실히 코드가 읽고 관리하기 쉬워졌다.