比賽結果（updated）

艱困的戰役終於結束，疲憊的戰士返回他的家鄉。

這次的題目和上次一個很大不同的地方在於，上次的題目第一題是超白爛題，我用了不到半小時就解出來。這次的題目都有一定難度。所以上次我可以寫兩題，這次連我在內所有人都陷入苦戰。

比賽時間為五個小時，我選擇了前兩題來寫。第一題是有個叫做John的宅男，他想告訴Mary一個冷笑話，可是又沒膽子親自跟她講。假定A比B年老且A是B的朋友，則A可以把笑話傳給B。題目要求說：寫個程式，給所有的（A,B）關係，找出John有幾種方法可以把冷笑話傳給Mary。第二題則是講了一個字串編碼方法，要求寫個程式將其實做出來。然後一看就知道是霍夫曼編碼，ITOA Chapter 16：Greedy。

比賽剛開始我以為第一題可以用BFS做出來，結果一直WA（Wrong Answer），思考後認為應該是演算法的設計本身就有問題了，所以當機立斷跳只要有苦工就一定寫的出來的霍夫曼編碼問題，結果我的萬年詛咒Segmentation fault又出現了，好在寫PHP也累積了不少的除錯經驗，在不依靠GDB的情狀下用Printf加上STL全部改指標把所有的漏洞抓出來。但是改好了以後又進入了無限WA地獄。（用GDB反而會糟，因為比賽單位的GDB根本沒設定好orz，一遇到fscanf就報錯的除錯器實在不怎麼能用。）

那時開Firefox看即時排名，乙組的人全部零題，也就是說只要弄出一題，就有機會拿到冠軍，但萬一連一題都寫不出來，今年乙組就很歡樂的全滅惹，就在巨大的壓力下不斷測試不斷送出，結果寫到比賽剩下不到一個小時的時候，我注意到題目沒有限定只能用大寫英文字母，就把某個陣列開大，結果PC^2就對我說Yes了，於是我也很開心的拿到全場唯一的氣球。小小的教室，緊張的氣氛中，我們的桌子上高聳唯一的氣球，那種感受只能用「極品」來形容啊XDDDD。拿了氣球以後心情就放鬆很多，至少確認我是北區第一了（因為北區的人全部擠在同一間教室比），頭腦就比較冷靜可以慢慢想剛剛一直WA的第一題，就在那時候我成功畫出一個圖證明我原來的演算法不對，於是就把發現的漏洞修補掉，可是仍然一直WA，就這樣改改送送WA到達了比賽結束。

這次比賽會場碰到好友DL低工口蠻多次的，第一次是比賽前擦身而過，大家互相比鬼臉，再來就是比賽後出場碰面，低工口很開心的告訴我他一個人不到一小時就寫了三題。當然順便要跟我炫耀每一題的解法是如何的簡單，結尾再加一句「低疤你真是弱爆惹」附加thumb-down手勢XD，我自己的隊友回家以後，我要尋找帶隊教練的蹤跡就留在比賽場地，一邊跟DL打嘴炮、一邊看DL的人馬集合。

後來確定帶隊老師因為有事已經自己回家以後，我就前往捷運站，結果DL他們的腳程慢到不可思議，竟然在捷運站又給我碰到，於是又打了另一輪的嘴炮（其實內容大概就是DL希望大乙二連霸冠軍低疤先生請客XDrz，但其實以獎金除以花費的時間的話，其實是低工口的數字比較高才對XD），等他們人馬到齊後，搭同一班捷運在台北車站分手各自回家。

晚上DL回到新竹後，在打世紀以前做了些對話，低工口分析了他如何做出那些題目，「第一題很簡單，倒過來DFS加上簡單的DP就結束了」，這句話當時聽不懂，結果睡一覺醒來就懂了：對於所有節點u相關的forwarding pair（v,u），DFS（v），然後有結果就存在陣列result[v]，DFS一遇到已經有結果的v就直接return。其實是ITOA chapter 17 DP後面講的變形。至於其他的東西，因為牽涉到圖論，我ITOA又沒看圖論，所以也就沒有深究了。

至於看ITOA有沒有用？大概有兩件事情算是他的作用，第一件事情就是我寫霍夫曼編碼的時候，因為看過ITOA相關章節，所以coding比較順，只要專心應付Segmentation fault就好，第二件事情就是聽了DL的hint以後睡一覺可以想出第一題的解法，但因為我沒把ITOA中BFS的證明看熟（如為甚麼BFS一定可以跑出最小路徑的證明等），所以還是不完全清楚為甚麼不能用BFS，雖然我有畫出讓我程式跑不出來的圖，但改了以後還是WA。再來就是有一題堆積木，如果限定最小的那一面只能向下的話，那題就是DP，但積木的每個方向都可以擺下面那我就不知道了，這個不能算解的東西應該也可以歸功於ITOA對於DP分解步驟的訓練吧orz

那能說ITOA不值得看嗎？好像也不能這樣講，在我看過的十四個章節中，ITOA嚴謹的展示了如何分析一個演算法的complexity，如何結構嚴謹的判斷一個問題是不是可以用DP，如何證明一個問題可以用Greedy，一些基本的資料結構各種操作的複雜度。沒這些東西的話解題只剩下直覺可以用來猜orz。但我看了之所以幫助不大，除了我沒看完之外，可能也是因為我的實戰經驗太少，沒有apply theory的機會，工具不熟悉自然不能觀察題目的脈絡了。如果我當年不是一直打小朋友，而是看完ITOA後寫200題ACM，情況可能會有所不同吧。

對於STL我也有一些想法：如過說用C++寫應用程式是在人間工作的話，C++的template metaprogramming就是穿梭陰陽界了。把class T帶入template以後，根據class T介面的不同就有可能發生不同的問題。這次比賽中我也吃足了這方面的苦頭，特別是寫霍夫曼碼那題的時候，我自己定義了一個資料結構node來表示tree的節點，結果把他拿去存list就一直Segmentation Fault，後來急中生智不用list<node>改成list<node*>，裡面丟的只是指標，只是一個32bit正整數，不管STL做了多少複製，什麼時候複製什麼時候刪除，取值取到的值是不是當初同一個instance我統統不管，只要可以存、可以取、可以刪除就好，implementation隨便他玩，我只針對取出來的指標進行處理。這樣做以後SEGSEIV就不見了。無怪網路上會有人說：寧願用C用void*去寫library，再用wrapper包起來給C++用，也不要去碰C++的template。抽象化的滲漏現象，完全一表無遺。我還沒提到template帶來的恐怖除錯訊息呢.....

比賽完後要做什麼呢？除了靜待比賽名次正式發佈外，我也要回到正常的醫學生生活去了，每天讀共筆，處理系學會要求的文件，有空讀點電腦書。電腦書的話就是GoF的Design Pattern，不過因為讀ITOA覺得也算有趣，Design Pattern之後搞不好可以把他放進去，有好多好玩的電腦書可以讀，我要怎麼辦啊XDDDD

最後做個總結，現在最大的心得就是：我愛霍夫曼啊XDDDD（霍夫曼擊，一分之一～～～～）
---Update---

有一件事情忘了提，一開始我只確定我是北區那間教室的第一名（因為那個教室只有我有誓約勝利之氣球Excaliballon），所以我一直很擔心南區會不會有高手解出兩題或是coding比我快（畢竟我C++很久沒用了，coding的速度和精度會下降也是理所當然唄）。就去查了NCPC參賽名單，結果發現今年的乙組只有北區。ㄎㄎ

嘎～哈哈哈哈哈哈哈

今年霍夫曼戰士低疤創下了兩項驚人的紀錄：

1.全場其他隊伍題數加起來乘以二也沒有低疤多
2.乙組比賽Accepted的題目超過90%是低疤寫出來的

話說那顆誓約勝利之氣球Excaliballon 跟世紀帝國「XXX已經升級到城堡」根本是一樣的東西，給別人壓力的orz 全文連結