【贊助企業｜Google】
想找尋更多練習Coding的機會嗎？
來看看線上程式比賽KickStart！
Google每年舉辦許多場次
錯過了之前的比賽嗎？
這次不要再錯過了！
---------------------------------------------------
參加比賽你可以：
✅ 提升你的程式設計功力 Grow your coding skills
✅ 解決有趣又有挑戰性的題目 Tackle fun, challenging problems
✅ 了解在Google做軟體工作所需要的技能 Get a taste of the skills needed for a technical career at Google
現在就報名#KickStart，了解更多 Learn more about #KickStart and register today→ g.co/kickstart
google kickstart 比賽 在 [心得] Google Code Jam 2008 參賽心得- 看板Soft_Job 的推薦與評價
這次趁自己給自己放假的時間，參加了 Google Code Jam 比賽，那是一個程式設
計比賽，裡面有全世界的怪物參加。
我那時候參加的動機是，想試試看自己有多少能耐，看看自己能走到哪一步，雖然
我大概知道自己是到不了後面的比賽的，但是還是想試試。
在他還沒比賽之前，有開放幾題的練習題給大家做，我做之後的感想是，這是數學
與演算法的比賽，演算法方面我還算 OK，可是針對 Dynamic Programming 方面，我看到
題目真的是沒有什麼直覺可以快速組織出如何使用 DP 演算法，畢竟上次使用 DP 大概是
快五、六年以前，感覺似乎已經流失了許多，我看到許多可以使用 DP 的題目，但卻沒有
感覺如何寫。所以比賽之前，我就猜到我應該會死在這一類的題目上面，因為有使用 DP
跟沒使用 DP 而使用最笨的方法解題，無論在解題時間或是執行時間上面都是差很多的。
再來，我在練習題中，發現每三題之中一定會出一題以上的數學題目，像是求機率
，求方程式...等等。 哎呀！ 我又知道了，我大概 95% 也會死在這種題目上，我以前在
數學上沒有下太多功夫，所以會死在數學題目上是應該的，只能碰碰運氣，看看能不能碰
到正好會的。
我稍微簡單的介紹一下他進行的方式，給你三題，英文出題，題目會跟你講輸入資
料的格式是什麼，也會規定輸出資料的格式。他的輸入資料是給你下載的，其中又分小資
料集檔案跟大資料集檔案，小資料集檔案一旦你開始下載，就開始計時，計時四分鐘，你
必須把你所下載的檔案內容用某種方式輸入到你的程式中 ( 例如讀檔 )，然後輸出他所
規定的格式的結果出來，放入一個檔案中，然後上傳你的輸出檔案與程式碼。而大資料集
檔案，是你下載之後，給你八分鐘的時間，時間內也是一樣，把結果與程式碼上傳。大資
料集跟小資料集，顧名思義，就是一個是資料量比較小，另外一個資料量比較大，資料量
比較小的讓你可以先不用考慮最佳化，而資料量比較大的就一定要考慮最佳化，不然有機
會會沒辦法計算出結果。 但是我這次的經驗是，一開始最好就要考慮最佳化，不然你大
概也沒時間考慮了，第二個經驗是，一定要先寫好讀寫資料的程式框架，這樣才可以節省
時間。
喔！對了，大資料集的正確性只有在比賽結束之後，你才會知道，而小資料集是在
你上傳之後就會跟你說正確與否。
資格賽沒多久就到了，他的時間給你 24hrs 來解三題，兩題演算法、一題數學題
，演算法都可以使用貪婪方式解決，可是數學題目是幾何機率問題... @.@ 我一開始連
機率都有點忘記，還要去看圖形，時間很快的過去，我解完了兩題演算法題目，然後最後
一題數學題就在一頭霧水中沒做。不過資格賽只要你有做完任何一題的小資料集與大資料
集，且結果正確，就可以參加下次的比賽 Round 1。
很高興，我成功的通過了資格賽，不過看到那題數學題，我大概就冷了一半，所以
我把志願放在希望能走到 Round 2 就好了。
Round 1 要開始的那段期間，我正好也要考駕照，所以大部分的時間都花在練習開
車以及準備筆試上面，再加上早上跟晚上都有英文課程，所以那段期間沒什麼在準備，不
過我知道，準備了也沒用，這種東西臨時抱佛是沒什麼用的。
Round 1 分成三個時段，參賽者可以選擇兩個時段參加，也就是說，你有兩次機會
，第一次沒成功，還有第二次，每個時段挑選 840 名參賽者出來。
我選擇了禮拜六的早上跟禮拜日的晚上，也就是第一場跟最後一場，我個人認為，
個人認為啦，沒精算過，第一場應該是最多人參加，但是可能題目會比較簡單，而最後一
場，由於前面兩場把精英都挑走了，所以第三場應該是最有機會晉級的，為什麼我會強調
個人認為呢？因為我發現國外論壇也有討論參加哪場是最好的，還有人開始在上面用機率
來精算，有個人看到了大家開始拿數學公式狂討論機率，就發表了「大家果然都是數學的
狂熱分子，大家加油吧！」，唉，我看到卻是心涼了一半。
Round 1 A 終於來臨了，第一題是個送分題，兩個向量相乘，要怎麼排列才能算出
最小的乘積，這題很簡單，題目我也看懂了，但是在做的時候，不知道哪根筋不對，人家
明明說兩個向量的數量相同，我卻到後面在思考數量不同的情況，最後才突然想到不需要
考慮這個，浪費了許多時間。第二題題目英文對我來說有點艱難，我在題目看不太懂的情
況下，沒辦法寫出演算法，因為有一個地方我一直沒弄懂他題目的意思，而這個會影響到
最後結果。當然，最後我就在這種情況下，只解完了第一題，然後第一輪失敗。
在 Round 1A 結束後，我研究了別人的解法，才瞭解題目的意思， 「The
minimum possible number of batches are malted. 」 意思是加麥芽口味的數量要最小
化，而我當時以為他的意思是 「加麥芽口味的當成最小值」，差很多，所以當然解不出
來。
再來， Round 1B 是禮拜六晚上開始，不過我沒參加，但是我還是跑上去看了題目
，順便試做，然後我還挺慶幸我沒參加 Round 1B 的。 因為，第一題最少分的就是一個
類數學題，而且最重要的是，我題目也有一點看不太懂，我事後來看整個三輪的正確率，
也是 Round 1B 的正確率最低，這一輪打擊了我不少自信。
Round 1C 在禮拜日晚上五點，終於到了，第一題計算手機按鍵上面的字母如何配
置可以讓按的數量最小，這題雖然挺簡單，但是我還是花了 30 分鐘，而最快的人只花了
5 分鐘...第二題是計算 Ugly Number，老實說，我看到這題我大概猜的出來是要使用
DP，但是我實在沒什麼感覺要如何使用，最後只好用暴力解法，只是暴力解法就是又花
時間又慢，而且我中途還一度腦袋打結，最後，沒在時間內完成，而我進入 Round 2 的
希望也破滅了。
不過我最後還是把那題用暴力法寫完，大概是因為不甘心吧，只是暴力法只能解小
資料集，碰到大資料集大概就無能為力了。
比賽對我來說已經結束了，老實說心中有一些沮喪，不過也感覺理應如此，因為演
算法跟數學對我來說，一個是很久沒碰 (在公司裡面頂多用用簡單的演算法，而不會用
DP )，一個是更久沒碰而且也沒強過。 而 Google 的比賽比較像是數學家的比賽，感覺
跟 ACM 、 TopCoder 很像。
如果我還想參加的話，我大概要把以前沒擁有過的數學認識非常多下，然後狂做
ACM 跟 TopCoder 的題目，把演算法的那種直覺抓住。就我的感覺，這種比賽是可以訓
練以及準備的，訓練的方式就是一直做題目，然後數學也一直做，而參加這種比賽最好的
時機就是你在當學生的時候。出去工作之後，東西很容易在一不小心的情況下流失。 不過
也許這只是我的藉口吧！
這種比賽精英真的很多，這次我還特別選了優勢比 C++ 大的 Ruby 來做，不過我
看到上面高手大部分是使用 C、C++、Java，所以我輸也沒什麼藉口，只能說實力就是這
樣。
不過這次在上面也看到一些很有趣的現象，還有人用 SQL 來解題，也發現有人每一
題都用不同的語言來解，可能是想跟別人與眾不同吧！ 在參加比賽還能有這種閒情逸致
，真的是高手。不過也可能是這種比賽大部分都是演算法正確就沒問題，所以重點不在語
言上面。 但是我覺得語言還是有優勢存在，因為我使用 Ruby 就不太需要擔心大數的問
題，可以專心在演算法上面。
比賽對我來說雖然結束了，心中也有一些失落，但是也激起了我想要把數學搞懂以
及想要做題目的慾望，我要大喊！ 「Google Code Jam! 我明年一定要進入 Round 2!!」
XDrz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.151.55.252
※ 編輯: redray 來自: 202.151.55.252 (07/28 23:39)
... <看更多>