查看: 1202|回復: 2

[GCJ] Google Code Jam 2015 Qualification Round 題解

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

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

    發表於 2015-4-12 11:21:08 | 顯示全部樓層 |閱讀模式

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

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

    x
    本帖最後由 domen111 於 2015-4-12 18:18 編輯

    題目: https://code.google.com/codejam/contest/6224486/dashboard
    Scoreboard: https://code.google.com/codejam/contest/6224486/scoreboard
    翻譯: http://forum.tfcis.org/thread-982-1-1.html

    GCJ能破台真開心,來發個題解囉!

    Problem A. Standing Ovation
    簡單題,for迴圈掃過去讓每個害羞等級都能站起來即可
    for掃過去時一邊計算有幾個已經站起來的人,如果無法讓那些人起立就再加一些害羞程度為0的人(反正加進來的朋友害羞程度是多少都沒差),O(S[sub]max[/sub])輕鬆解決
    AC code: http://ideone.com/fkrxxr

    Problem B. Infinite House of Pancakes
    暴力算有幾個特殊時間,用priority_queue維護即可
    第一個想法:全部都掉priority_queue,每次把最大的那個切兩半再丟回去,不過這其實是假解,會WA的測資和假解的code在此: http://ideone.com/f1E9wA
    正確解法:還是用priority_queue,不過同一個數字被切第二次時應該要切三等份,切第三次則是切成四等份,並依此類推,實作細節見程式碼
    更簡單的解法:賽後聽說直接枚舉每個人最多吃多少,超出的部分分掉就行了,看來我的作法太麻煩了
    AC code: http://ideone.com/Q9Eklg

    Problem C. Dijkstra
    四元數,乍看之下這題很數學,不過其實沒那麼難,而且他很好心的告訴你乘法有什麼性質了
    如果是小測資的話,先暴力把那個長度X*L的字串S弄出來,就for直接掃過去,設一個數字t=1,一直累乘,直到t=i,t重設為1,繼續掃直到t=j,t重設為1,繼續掃直到t=k,如果後面還有剩下一些字元的話,算看看是不是乘起來為1,若是則答案為YES
    為什麼是對的呢?認真想一下,會發現切成三段只要切在第一個能夠切的地方就可以了
    至於大測資,你會發現如果一個字串乘了4次一定=1,如此一來可以省掉很多多餘的計算(超過4輪就可以break掉了),詳見code第63,70行
    實作上,我用一個struct去存我的數字,寫個operator幫我算。字串重複x次我則是用一個struct做虛擬的字串
    AC code: http://ideone.com/apP8ZX

    Problem D. Ominous Omino
    小測資數字那麼小,就人腦暴力算一下X=1~4的情形,4比較複雜一點,沒想清楚容易錯(害我傳了一個WA)
    後來你會發現,其實大測資也能用這麼暴力的方法AC,因為X>=7一定是RICHARD,如下圖

    至於x=5,6就得要人腦推一下了,如果沒想清楚也是容易WA(而且賽後才會知道)

    看了一些前幾名的作法,大部分都是和我一樣的"人腦暴力法",只有shik是真的寫了好長的程式碼去算(shik的code)

    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    該用戶從未簽到

    0

    主題

    1

    帖子

    23

    積分

    初入竹園

    Rank: 1

    積分
    23
    發表於 2015-4-12 22:57:20 | 顯示全部樓層
    其實我第一個想法和你一樣~吃了一個 Incorrect! 後發現 1 1 9 就爛掉了。我就想說「那我應該切多少啊?」,然後發現枚舉切多少也不會超時。

    話說你的時間複雜度顯然比較好 XD。
    回復 支持 反對

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-15 00:02
  • 簽到天數: 3 天

    [LV.2]偶爾看看I

    1

    主題

    6

    帖子

    26

    積分

    初入竹園

    Rank: 1

    積分
    26
    發表於 2015-4-13 09:01:02 | 顯示全部樓層
    感謝多門大大的分享^^
    回復 支持 反對

    使用道具 檢舉

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

    本版積分規則

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