| layout | title | date | tags | ||
|---|---|---|---|---|---|
post |
教育部 99 年度全國電腦軟體設計競賽 (2010 NCPC) |
2010-11-06 |
|
對於這次比賽結果真的很意外，竟然能拿到實際排名第四名。真的運氣太好XD，高手竟然失常，真可惜。但下個月的 ICPC 應該就被他們打趴了吧＝ ＝。這次比賽的過程，還是有點不順，還是會卡一些 bug。但還好都沒慌，大家都很穩地做該做的事情，可惜正確率還是太低（但系統真的有點OOXX）。以前總是會因為 bug 慌得要死，也沒死命要電腦 debug，隊友有把握就先給隊友！題目也靠蔡立宸都看完了，分工分的還 OK，希望下個月的 ICPC 能更穩！這是我們第一次參加全國性的比賽，是個好的開始XD。繼續加油吧！
題外話
測試機器時，對面那對跟斜對面那隊都是中山的，然後這兩隊有兩個人是情侶（不同隊）。測試機器到後面竟然就開始卿卿我我，似乎要親親似的。測試機器時間就算了，反正大家都跑來跑去。正式比賽快結束前，那女的竟然把投靠到那男的那邊，邊看他 coding。現在是正式比賽耶，這樣不算舞弊嗎....？
話說這一對情侶，南程盃也是卿卿我我的...
NCPC 本來是 10/23 要比的，但因為颱風，延期到 11/6。這兩週整個超級忙，一堆作業，還有考試。光 FM 就花了我一個禮拜寫，整整兩個禮拜除了團練，其他時間都沒寫題目。賽前一周還一直玩ipod的遊戲，心想比賽完蛋了...
11/5先回高雄，結果我的網路壞了，於是就很早睡。還好不像之前賽前一晚，失眠整晚，難得一躺下去就睡著了。
11/6 早上七點半起床，開始盥洗換衣服吃早餐準備出門。騎車騎到一半，我媽媽打來說我字典忘記帶了，就要繞回去拿。然後又開始前往中山，中山整個很遠＝ ＝＋。騎車騎太久都會眼睛很酸，超擔心等等會很想睡覺。8: 30 準時到達停車場，然後快速趕到比賽會場進行報到。
報到完就到休息室聊天，然後發現lionking他們竟然還沒來！好在 9: 00 報到結束前他們終於到了。接著開始測試機器，測試機器有三題。
Problem A - 字串可以循環的LCS
Problem B - 比較數字
Problem C - 3n+1 problem
先看了 A 然後開始想，蔡立宸先看其他題。他看到了 B 就說這題超簡單，我們就先寫 B 了。看 scoreboard，一堆人早 AC 這題了。斜對面桌還說他們是目前南區冠軍，然後開始寫 3n+1，結果一直 RE...。3n+1 這基本題竟然讓我們卡超久，RE了好幾次，最後把 int 都改成 long long int 終於過了＝ ＝＋。最後想A，最簡單的方法就是枚舉兩個字串的開頭做 LCS，但這樣是O( N^4 )，但可以優化到O( N^3logM )，但還是太久，可是我還是想要這麼一試。因為系內賽也因為一直想到O( N^2logN )的方法覺得太久不敢寫，最後兩個小時都卡那題，結果正確解法就是那樣＝ ＝＋。寫到一半，韓正廷來跟我們說他們的解法，本來覺得是錯的，後來想想是對的。就開始用他們的方法寫，我寫完後，測試 sample input，一直錯...。這題花我好多時間，一直有 bug，真的是每十行就一個 bug...，後來測資總算都對後開始 submit，一直 RE。開始把陣列加大等一些無聊舉動= =，還是 RE。找了好久才發現...freopne("ta.in", "r", stdin);。明明就是要開pa.in，我開ta.in幹嘛:(。就這樣結束了測試時間，為了那題都要崩潰了，整個信心都沒了。吃飯時就協議，coding 都交給陳映翰好了，今天我是 bug 王:(。
接著等到 12: 30 開始比賽，一共有 11 題。陳映翰先拿了 B 去看，其他的我跟蔡立宸先分著看。我也先看了 D，這時陳映翰也開始寫 B 了，似乎是題 DP。他寫完後測試測資（測資很多很難打，浪費時間），測資都對後馬上 submit，結果獲得 WA...。後來發現他忘記拿掉 break ＝ ＝。拿掉後就AC了，接著換我寫 D，D 就是一個很經典的問題，給一棵樹，找出可以讓這棵樹的高度最小的 root。對我來說就是 library 題，library 打一打就 AC 了。解著又換硬漢寫 H，寫了很久，但也 AC 了，又輪到我寫 C。C 題目整個很簡單，一些線段長度的問題。結果先拿 CE，又拿兩個 RE，debug 超久。後來先換硬漢寫 K，我把 code 印出來繼續 debug。過了快一個小時我就先去上個廁所，結果回來他們說我的 C 過了。真是無言，果然是他們測資還什麼有問題，大家對 C 的提問超多的。
寫一寫都會跳出別人問問題的回答，接著陳映翰的 K（筷子問題）也 AC 了。然後他又開始寫 J，這題是 k shortest path 的問題，他就開始照我的 library 寫。KSP 的 code 超長，整個很容易有小錯誤，後來測資對後就馬上 submit，結果WA...。才發現沒答案時要輸出 -1，又 submit，還是 WA，然後又發現是 undirected graph，這次 submit 總算 AC 了。此時我們六題，排名第六，超擔心就這樣沒前三名了。接著換蔡立宸寫 F，本來想很久，後來聽他方法感覺 OK，於是他開始寫。過沒多久也封榜了，開始不能得知其他人寫得如何，自己有沒有被超過。他邊寫我邊幫他看，陳映翰先去導 A 的公式。F 寫完後測資也對後，我們也 submit 了，結果得到一個 WA。我們開始懷疑這個做法對不對，因為適用 greedy，總覺得沒想清楚就是掛，然後先讓陳映翰寫 A。後來再重新想一次他的方法，發現他的前半部是對的，後半部根本就是 bipartite matching。就等陳映翰寫完他的 A，然後 F 的 matching 交給我改，等他寫完發現測資測不對。我就先把他的 A 印出來，讓他 debug，然後我上去改 F，改成 matching 後就 AC 了。又換硬漢改他 A 的 bug，過兩分鐘也 AC 了，就這樣氣球一直來XD，真的超爽！
這時候剩下三題，我們還有15分鐘，我們決定放棄了，這三題都是之前一直想不出來。而且時間也剩太少，應該也來不及，就開始研究封榜的 scoreboard，慢慢等時間過去。真是難熬的 15 分鐘，撐過後總算豁然開朗。
馬上打給電子哥跟他說我們的成績，但都不知道到底是第幾。後來聽他說教練休息室有完整的 scoreboard，於是馬上跑去那看。我們竟然排名第四！！天啊！我當時真的不敢相信。前兩名 9 題，第三名第四名 8 題，接下來是 7 題。希望最後的名次是第二，拜託第二名取三個。
記分板網址：scoreboard