Asia-Pacific Informatics Olympiad 2010

• A푼김에 나머지도 풀어봐야지~하고 건들었는데 B의 미궁 속에 빠져 헤어나오지 못했음ㅋㅋㅋ
• A : \( dp[i] = \max_{j<i} (-2ap_j)p_i + (dp[j]+ap_j^2-bp_j) + ap_i^2 + bp_i + c \)  Convex Hull Optimization.
• B : case를 잘 따져야 하는 tree dp... 풀릴듯 안풀려서 네시간정도 잡았는데도 답이 없다-_-
• 
• 결국 풀어냈다ㅠㅠ 처음에 그림 쓱쓱 그려보며 길이 합이 최대인 disjoint path 2개를 찾는다는 사실은 알아냈는데, 이걸 구해내는 것이 정말 어려웠다.. dp+greedy로 풀어낼 수 있었는데, 경우의 수를 하나하나 고려해줘야 했다-_-;
• C는 도저히 접근조차 허용하지 않는 최고존엄의 문제라 솔루션을 열심히 찾아본 결과 본래 2010 APIO사이트 url을 얻었는데, 현재는 사이트가 날아가서 web archive에서 솔루션을 받아냈다-_-

• APIO solution.pdf

• C를 해설보고 풀어냈는데, 기하적 감각과 카운팅 센스가 곁들여진 멋진 문제였다.. {A,B,C:D}의 순서쌍을 세는데, 여기서 A,B,C를 지나는 원을 그렸을 때 D가 그 안에 포함됨을 의미한다. 이런 사각형 ABCD의 성질을 생각해보면, convex일 때와 concave일 때 두 가지로 나눌 수 있다. convex인 경우 저 순서쌍 2개를 만들 수 있고, concave일 경우엔 하나밖에 못만든다. (자세한 증명은 솔루션에) 즉 convex의 개수를 A, concave의 개수를 B라고 하면 답은 \( 3.0 + (2A+B)/\binom{N}{3} \)로 쓸 수 있다.
• 이제 \(2A+B\)를 구해야 한다. \(A+B\)는 사실 쉽게 구할 수 있다. \(\binom{N}{4}\)와 같기 때문. 솔루션에는 \(4A+3B\)를 구하는 법을 소개하고 있다. 바로 특정 사각형에서 한 점을 지나는 직선을 그을 때 나머지 세 점을 반쪽 평면에 들어가게 할 수 있는가를 따지는 것이다. 이러면 convex의 점들은 모두 만족하여 \(4A\)개만큼 세지고, concave의 경우에는 하나는 제외되어 \(3B\)만큼 세어진다. 따라서 \(4A+3B\)의 값을 구할 수 있는 것!
• 실제 구하는 것은 angle sweeping으로 쉽게 짤 수 있고, 구현에는 30여줄이면 충분했다..ㅠ