心得

第二次參加 ICPC，這次比的好爛，但自己心不在這，也沒在練習，本來也就只是陪學弟參加。拿到這樣的成績，其實還蠻不意外的。但雖然這次比的很爛，但其實這次參加的很開心。

與國外隊伍的交流，是這次最值得的事情。也突然意識到明年是最後一年可以參加 ACM-ICPC 了，突然想好好把握這一年。可惜沒有上交大，沒機會跟煥博大神一起參賽了:(。

這次比的這麼差，最主要就是自己沒有花時間練習，加上得名的衝勁似乎也沒有以往強烈。花時間練習，不僅僅可以加強自己對題目的敏感度，也可以加快 coding 的速度，可以加快看題目的速度！

這次比賽，也多了很多時間與其他平常較少接觸的同學聊了很多。也看了更多的想法，然後回家後被電子哥訓了一頓，這場比賽的過程，其實也給了我很多體悟，加上電子哥的訓話，我覺得我體悟更多了。

該立下一個確切的目標，並努力。而不是像個多頭馬車，使得自己一事無成。

這週大概要儘快找到研究所的指導老師，接著就是儘快完成專題了。大四下開始，決定再衝刺 ACM，並加強英文。

競賽過程

11/25 - Day 1

這天起了個大早，大家預計搭乘 8: 33 的自強號，所以我想我應該要在 7: 30 起床。但莫名的在大約 7: 20 左右起床，因為想要看一下時間，就拿起了手機。竟然發現我手機呈現關機狀態！！！我整個驚醒，趕快喚醒電腦看時間，幸好不是睡過頭了。如果睡過頭還沒人能打電話叫醒我，我就崩潰了。

起床盥洗了一下，想說要離開電腦兩三天，所以決定出門前，在上個 bbs 之類的，接著就出門了。大夥兒就在火車站門口集合，一直等到大約 8: 30 了，幾乎所有人都到齊了。就只剩王同學還沒來，8: 27 打給他時，他竟然還在宿舍。於是他就沒趕上火車了，他的隊友也有情有義的留在火車站等他，他們就換了下一班自強的票。

歷經三個小時的車程，總算到達新竹了。話說在車上跟 Jimmy 聊滿多的，以前都沒有跟他聊過，聊的滿開心的。到新竹後，也 11 點多了，找午餐吃就成的當務之急。但人多（我們這次出 5 隊，但有一隊遲到所以有 12 個人）實在難以決定要吃啥，最後大家吃了肯德基，但我莫名嘴巴破好多洞，這幾天吃什麼都好痛苦。

另外，也在車上得知成大放榜了，恭喜我自己正取成大資工所與成大電通所。雖然電通是正取倒數第二，回去該忙著找指導老師了！

吃完肯德基後，我們去等待前往中華大學的公車，遲到的隊伍也很幸運的趕上這般公車。上公車是惡夢的開始，往中華大學的路程是山路，而且非常的迂迴。加上公車比較老舊，以往不會暈車的我都覺得有點暈了。

到達中華大學後，才聽說 template 可以帶 25 頁，我才想起來 ICPC 都是 25 頁，是 NCPC 才是 20 頁。馬上去附近的影印店在印一份 25 頁的，但其實也就只是拿去年的，大概多了些 java 的寫法而已。因為我都會加上 syntax highlight，所以我都彩印，但經然要 200 新台幣（好貴，比台南貴＝ ＝）。其實我覺得 template 通常比賽用不到，可是沒帶會沒安全感 XD。

接著大家就在中華大學門口拍個合照，然後趕去報到了。話說小Q還打給我，說他已經在會場了，真是個好久不見的朋友。進會場後，就先去找幾個外校的高手打個招呼裝熟一下XD。然後是振奮人心的開幕典禮，不得說黃金雄教授真的是霸氣十足，還有台味十足。

在開幕典禮後就是練習賽，練習賽基本上就是規則講解然後測試機器。但他也沒說不能先看練習賽題目，幾乎大家都在練習愛開始前就把三題練習題都寫完了。等練習賽開始就是比誰上傳比較快了。

練習賽後就晚餐時間，晚餐就吃 buffet。我吃到睡著了我，於是我就跟隊友說想回房間休息了，一回房間我就睡著了…。我的隊友A 也睡著了，隊友B 至少先洗了個澡然後也睡了。我在十點多驚醒馬上去洗澡，但熱水很小，超冷！！洗完澡後，一直叫隊友A起來洗澡，他一直給我倒下去，但最後總算起床了。然後我就看個電視看到快十二點就睡覺了。看了「超危險特工」，看布魯斯威利當鐵人。

11/26 - Day 2

這天是整個 ICPC 的重頭戲，也就是正是比賽的日子。我整個很早起，一樣叫隊友叫了很久他們才肯起床，然後順便打給其他隊伍叫他們起床吃早餐。早餐只供應到八點，不吃會沒力氣比賽阿！我跟我隊友們六點半就下樓去吃早餐，我們似乎是最早的幾個人之一。我們都快吃完了，其他人才漸漸下樓吃早餐。

話說王同學又給我睡覺，都打去他房間了，一直到七點半都沒看到他們隊伍的人影。打手機給他，發現它們全都還在睡，太誇張了！！！吃完早餐後，王同學那隊上樓拿行李，結果又是所有隊伍＋老師等他們一隊。老師就請我們先去做車先到會場，他會等他們。真是太扯了！我現在看到他只會想到遲到了，而且他們還說一定會 delay，所以是故意遲到的意思嗎＝ ＝？

抵達會場後，十點要開始比賽，大家開始漸漸入場。我跟王同學他們那隊幾乎是最晚入場的，我在外面準備些 template 的資料。另外，我們還跟日本專修大學的教練拍照，因為他有很酷的鬍子。我還很白痴的找專修大學的候補隊員拍照，因為是個可愛的女生 XD。

接著就進入比賽會場了，緊張啊！！話說這次比賽用來驗證 template 的印章小小的還滿不錯的，不像 NCPC 的都超級大，都蓋到 code 了＠＠。進入比賽會場後，就開始等待比賽開始，大概等了二十分鐘吧。比賽一開始時，竟然發生了一件慘事，就是所有隊伍都無法登入電腦，似乎是密碼給錯了。

當比賽開始後，我第一題就看 A，這題就是之前修過的「無線網路」中提過的 Hidden Terminal Problem，要找出有幾對 Hiden Terminal 的 Pair。但我剛開始想的太多了，竟然覺得有點難就先跳過，這時隊友看完了 E，就題大意就是從 A 走到 B，並使得經過路徑中的最大權重最小。我直接想到是 shortest path 的解法，就很快的用 Dijkstra 解決了。此時隊友也明白 A 到底要幹嘛，就找出有幾對 pair，加上點的數量不多，沒舉就可以了，於是 A 也過了。

再來我開始寫 B，一樣是 shortest path 的問題，但有點變化，但我有點沒把握解法，但不管就先寫。此時看到 scroeboard 很多隊伍已解出 D，於是我請隊友快看 D 並想一個可行的解法，他也很快的看完並想出來了，有點像是分配資源的問題。給定很多工作的開始時間與結束時間（不確定題目是不是說時間），要用最少的資源完成所有工作。就針對起始時間對工作排序，若起始時間相同則比較結束時間。接著用 greedy 的方法每次將下一個工作放到最找閒置的資源，若沒有閒置資源，則使用新的資源。

在 D 過了後，我回去繼續寫 B，上傳了兩次才發現自己演算是錯的，題目大意是要找最短路徑，但加上一些路徑的 constraint，所以要做些變化才行。我接著就完成修改過的解法，也很有把握的說，但很快的得到一個 Wrong Answer。我在反覆的 review 我的 code，一直覺得沒有問題了，在崩潰之際，我突然想測試看看起點跟終點一樣的狀況，才發現我在這種測試資料會有問題。在修改後上傳就得到 Yes 了，這大概是太久沒練題目的報應＝ ＝。

解完了四題後，大概花了兩個小時左右。我們發現 C 也很多人解出來，開始去看 C，一直要求二進位還有模數加上機率的題目，由於數字可能大到 200 位元。但看這麼多人都很早解出這題，我的直覺告訴我不可能是大數運算。但我們都往數論的方向去思考，完全沒有頭緒，規律找半天也找不到。接下來的三個小時就完全沒有寫出半題:(。

在這三小時我也看了 G 跟 F，G 的題目是給你一隻程式的程式碼，測試資料就是給你這隻程式的執行步驟，問你是不是合法的執行步驟。這題想的也超級複雜，但中途也想到暴力解，找出所有可能的執行流程後，在與測試資料比對即可。但一直覺得這樣時間複雜度過高就做罷了，比賽後發現大家都是這樣做的＝ ＝。

另外，F 是一個機械手臂要旋轉到某個位置，問你是否可行。我想到的是 backtrack 枚舉，但我是針對每個旋轉點都考慮他的八個方向，後來想想時間複雜度過高，8^10 真的太高了。賽後問台大的高手們，發現的確也是枚舉，但枚舉的是每個方向用幾次，在聽完他的解釋後我終於恍然大悟了。另外還有一題 I，給你一張圖，要在圖上蓋機場，會有一些計算權重的方法，機場可能建立在某一條邊上。看完也真是毫無頭緒，賽後問聽說是 search 題。最後還有一題 H 我就沒看了，到現在也不知道題意＝ ＝。

最後四題慘敗，真的有點慘XD。但我也沒感到特別不高興，大概也知道自己這一年很混，拿這樣的成績沒什麼好抱怨的。比賽完就開始在個高手間亂串門子問一些題目的解法，話說那題我們一直往數論想的 C 是 DP ！！真是慘到崩潰。

在漫長的等待後，終於到了頒獎典禮，頒獎典禮也會頒發 NCPC 的獎項，所以今天拿了張 NCPC 的佳作獎狀＝ ＝。不得不說台大真的太威猛了，似乎四隊還五隊破台，但也不得不說台大的隊名都有點詭異，例如：m(_ _)m、a * ( b / gcd( a, b ))，真是造成司儀的困擾XD。

頒獎後是晚宴時間，晚宴我也吃到快睡著＝ ＝。但因為有人也想要跟可愛的日本女生拍照，就硬要等到他們吃完 ╮(╯_╰)╭。然後我們就真的去跟日本隊伍拍照了，但接下來就是這次參加 ICPC 最值得的事情。我們開始跟日本隊伍聊天，聊 ACM，聊一些文化，聊科技聊技術等等。英文超破的我只能用關鍵字跟他們溝通XD，跟他們聊到被餐廳趕人，還繼續到 lobby 的沙發上續攤，就這樣一直聊到快 11 點。第一次跟外國人聊天，真的聊的很開心，而且覺得自己英文會進步！常常講著講著就會冒出沒什麼用過的單字。我們聊天的對象是京都大學（Kyoto University）跟專修大學（Sensu University）的隊伍，話說京都大學的教練現在碩二，已經被 Google 聘了，明年就要去 Google 了！他們的隊員也有在 Google 實習過，整個很酷很屌！還有都有留下他們的 twitter 跟 mail，希望能保持聯絡！雖然他們 twitter 的訊息我都看不懂，但剛好這學期有學日文，也用日文跟他們講了一兩句話XD。

話說日本真的很少用 Facebook，聽其中一個人說他覺得 Facebook 太難用了。最好笑的是他一登入 Facebook 就被鎖帳號了，似乎是語系的問題，在台灣連 Facebook 會是中文語系，所以被認為是帳號被盜。幫他改成日文後，他總算登入成功了，他也沒啥在用就是了。

他也馬上登入 Google+ 把我加進圈圈裡，話說他看到我的 profile icon 嚇一跳。他說大部分非日本人都不會用動畫的角色當做 icon，都用真實照片。他也說大部分日本人會用動畫角色當 icon，然後那個專修的女生馬上否定他XD。但未了避免他們覺得我很宅，我很急忙的用破英文解釋我以往都是用真實照片，只是最近無聊又覺得哈比（profile 那隻＝ ＝）長得很可愛就放了XD。但我覺得我的破英文應該沒有幫我解釋成功。

聊完後，一回房間我就又睡著了，睡到十二點多起來洗澡。洗完澡看一下電視，用一下電腦就又倒下去了。而且隔天還不能睡到十二點，一樣八點前結束早餐，所以也不能太晚起。

11/27 - Day 3

第三天早上調了 6: 30 的鬧鐘，但睡到七點才起床，擔心沒早餐吃就趕緊叫醒隊友，趕緊下樓吃早餐。話說我隊友們真的很愛睡，很難叫！！早餐吃著吃著，前一天晚上聊天的京都教練他們剛下樓吃早餐，竟然做到我們旁邊跟我們繼續聊，這一趟真的是值得了。

接著就要搭接駁車往火車站，但因為我們人數眾多，所以只好等下一班，這一等就半小時過去了。大約在十點抵達新竹火車站，但沒有事先訂票的我們也買不到任何有座位的自強號。我們就決定搭乘客運，結果客運沒有新竹→台南的，於是想找新竹→台中在轉乘台中→台南的。結果竟然沒有台中→台南的票了，我們只好回去火車站，買了新竹→台南的自強號站票。

在這漫長的三小時中，我們一直等待空位，大家就有做至就先坐著休息個幾十秒，被趕再起來。但竟然有人可以從頭坐到尾，也太幸運了吧！這三小時也跟大家聊了很多，聊聊研究所，聊聊 ACM，這之間體會不少。

在抵達台南後，沒吃午餐的我們又站了三小時，想必都餓了，就拿著大包小包的行李走進大遠百美食街吃午餐。接著就各自回家了，結束了這三天愉快又疲憊的旅程。

Problem List

Problem A

Hidden Terminal Problem，找出所有的 Hidden Terminal Pair。

枚舉三個點並判斷是否為一個 Hidden Terminal Pair 即可。

Problem B

給一張圖，城市與城市間有道路，道路上有長度的 weight 外，還有一個 condition K。要求找出最短路徑，另外就是不可以連續通過相同 condition 的道路。

將城市拓展成有 n × k 個，其中 n 為城市數量，k 為 condition 的數量。用 dist[ n ][ k ] 表示由起點到城市 n，上一條經由 condition k 的最短距離。因此只要在 shortest path 中加上判斷不要走重複 condition 的條件即可。

Problem C

暫無較好的解釋方法。

基本上是一題牽扯機率二進位與模數的題目。解法為 DP，等我確定解法與題目後再來改。

Problem D

給定 n 個工作，每個工作給你他的起始時間與結束時間。要用最少的資源完成這些工作。

作法是對工作排序，依據起始時間，若相同在比較結束時間。接著再使用 priority queue，每次 priority queue 的頂端總是第一個閒置的資源。若這個資源的結束時間小於下一個工作的起始時間，將此工作指派給此資源，因此只要將頂端的元素改成當前工作的結束時間。若頂端資源的結束時間大於等於當前工作的開始時間，就指派一個新的資源給他，也就是直接將此工作的結束時間丟入 priority queue。最後 priority queue 內的元素數量就是答案，基本上就是 greedy 的作法。

Problem E

一樣給一張圖，點與點之間有邊，邊上有權重。找出從 A 點到 B 點的路徑，使得經過的權重最大值最小。

看完很直接是想到 shortest path 的解法。只是把原本記錄距離的地方，改成記錄當前權重最大值。

另外，在賽後與煥博大神討論，他說他一看完的直覺是 binary search，作法就是 binary search 邊的 weight，在固定的 bound 下用 DFS 搜尋是否存在一條路徑可以從 A 點到 B 點。

Problem F

一個機械手臂，他有 n 段，因此有 n 個關節，每個關節都可以旋轉，旋轉的角度皆為 45k 度，但也表示要轉 k 次。現在給你一個區域，並判斷機械手臂的端點是否可以抵達這區域，並需要用最少的旋轉次數。

這題是請教台大的高手，很明顯的只有八種角度，而且在哪個位置旋轉不重要，將他當做向量就很好理解，不管在哪裡旋轉，最後的位置都一樣。因此我們枚舉，這八種角度各要使用幾次，把所有能使得機械手臂到達該區域的可能都找出來，並記錄最小值即可。

另外，要考慮一下機寫手臂的端點是個半徑 10 cm 的圓形。

Problem G

給你一隻城市的 code，測試資料會給你一個數字的序列，表示程式執行的行號順序。該題目就是問你，這串序列是否合法。

先將該程式所有可能的執行的序列找出來，接著再一一比對測試資料是否有出現。

Problem H

從缺，沒看過說，等我去看了也知道解法再補，或有有心人可以寄個 mail 來告訴我 :)。

Problem I

確切題意有點忘記，等題目出來再來補。

聽台大的說是 binary search 的題目，也聽到有 ternary search 的作法。