Google Code Jam 2015 Qualification Round 題解

domen111

題目: 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)

johnchen902

其實我第一個想法和你一樣～吃了一個 Incorrect! 後發現 1 1 9 就爛掉了。我就想說「那我應該切多少啊？」，然後發現枚舉切多少也不會超時。

話說你的時間複雜度顯然比較好 XD。

WYJOIER

感謝多門大大的分享^^