Google Code Jam 2015 - Round 1A 題解

Sylveon

題目：https://code.google.com/codejam/contest/4224486/dashboard
論壇的翻譯：http://forum.tfcis.org/thread-993-1-1.html

TOI 2!有玩的全員通過~  CL 發現一個爛bug就爆了一筆 = =

翻譯第一題的題意浪費我超多時間= =

Problem A. Mushroom Monster
題解：Gready (因應Gready課教授要我們分享題目)

兩個答案是獨立的，最佳解如下
1.把所有減少的量的加起來就好
2.每10秒最多吃兩兩相臨項，減少量的最大值為速率，模擬求出答案即可

兩方法都是線性的，可在[tex]O(N)[/tex]時間內完成

Problem B. Haircut
題解：[del]模擬(JOE提供的平行演算法)[/del]、二分搜尋法

如果你有夠好的電腦或是足夠多的處理器，你可以暴力做出來XD。

我們可以線性時間算出在時間T理髮師剪完多少人的頭髮，於使我們可以二分搜出地K人何時會被剪到頭髮，再根據撿到的時間回推是哪個理髮師剪得即可。
時間複雜度為：[tex]O(BlogM)[/tex]


Problem C. Logging
題解：極角排序

本題要問每一個點，使該點變成凸包邊上的頂點，最少要刪除多少點。
考慮凸包的性質，對於每一個凸包頂點、邊上點，與相鄰的凸包點夾角小於[tex]180^{\circ}[/tex]，換句話說，如果點P是凸包上的點，那凸包上剩餘的點都要在以該點為原點，夾角小於[tex]180[/tex]度的半平面裡。對於要計算的點我們可以枚舉所有其他點，把平面分成兩半，再檢驗分成的兩個平面有多少點，取最小值即可，那時間複雜度為[tex]O(N^3)[/tex]。


如果我們檢驗時，對於其他點先對角度做排序，那我們可以維護首尾區間，在線性時間旋轉掃描所有答案，該方法中最浪費時間的是極角排序，總複雜度為[tex]O(N^2logN)[/tex]





該方法可參考：TIOJ 1205
http://forum.tfcis.org/thread-885-1-2.html
http://cbdcoding.blogspot.tw/2015/02/tioj-1205.html