查看: 1135|回復: 1

[GCJ] Google Code Jam 2015 - Round 1A 題解

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2015-4-20 11:42:51 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    題目: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]


    079.png


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

    點評

    第一題寫得不太清楚,一堆人看不懂,在官方粉專也有人在抱怨  發表於 2015-4-21 08:00
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表