| layout | title | date | tags | ||
|---|---|---|---|---|---|
post |
教育部 101 年度全國電腦軟體設計競賽 (2012 NCPC) |
2012-10-20 |
|
今年是第四年參賽了，在沒有練習的情況下，退步的幅度越來越大。加上作息也越來越不正常，導致比賽過程中精神不佳。這次賽後解出了 4 題，基本上都算是簡單題。這次參賽一樣是與去年的兩個學弟一起比，記得去年 ICPC 賽後，曾答應學弟說決定要再拼個最後一年。不過很對不起他們，我自己因為興趣修了一些硬課，搞的自己一直處於忙碌狀態，沒想到到的碩一，忙碌得程度劇增。沒做到自己的的承諾心中也蠻愧咎的，尤其看學弟練習的這麼勤勞！
這次比賽一開始，很興奮的拿起題目開始閱讀。我率先看了 Problem B，看快速的看完了題目覺得應該是數學題可以導公式。而聖棨看了 Problem A，他說是模擬題，他簡單的告訴我題目的意思，基本上就是有點像在寫編輯器。題目意思滿簡單的，於是我就著手進行 coding，題目看似字串處理，不過我決定採用 list 的概念來實現。其中的字串操作僅有游標位移、插入、取代與刪除，用字串的方式在插入與刪除時會較複雜。我採用 STL 中的 vector，使用 insert 與 erase 即可輕鬆完成這題。不過題目的範例測資有錯誤，也造成我困惑很久。
在 Problem A 通過後，白狗看完了 Problem C，並告訴我他的想法。貌似是 LIS 的題目，由於 n 高達 5000，為了以防 TLE 的出現，決定採用 O( N × log N ) 的 LIS 演算法。submit 上去整個崩潰，一直 Wrong Answer，也找不到錯誤。於是我就先去看其他題目了，我開始看 Problem G，一題解密題，有給定加密算法。我很努力的想要逆推，甚至還想找出矩陣，在利用反矩陣來解，不過都行不通，此時精神開始不濟，就睡著了一下 :(。而聖棨與白夠仍在努力看其他題目，在我清醒後看到聖棨似乎在 Problem B 卡了很久，問了他目前的想法，他以數學的角度推了些可能的公式。但過度複雜，我不認為 ACM 競賽會出現過度複雜的公式，或是說一定有比複雜公式更好的作法。
我就決定把 Problem B 重新拿來看，才發現可以用 DP 來解！而此時的間也只剩下一小時了，也就是計分板開始停止更新了。比賽過了四個小時，才通過一題，自己都覺得很崩潰。但 Problem B 感覺滿有把握的，我儘快的將他 implement 並 submit，沒想到竟然通過了，讓我們精神都來了！這時我又回去看一直錯的 Problem C，在白狗的建議下，我決定改採用 O( N2 ) 的 LIS 演算法，沒想到竟然就通過了。看來當初實在想太多，也發現自己對於這些演算法的特性不夠了解。晚上與交大的朋友討論後，才知道使用 O( N × log N ) 的 LIS 演算法時，元素之間必須要有 partial order 的性質。
在剩下 40 分鐘左右，我們決定在衝一題 Problem F，這題就完全數學題了。我一直從測資猜公式，Wrong Answer 了好幾次，將範例輸出畫了出來觀察了一番，才發現到邊的性質，以及尤拉迴路！在發現這點後，直接請聖棨快推公式給我，推了兩次終於通過了！！是說我們都不知道自己 Problem F 答對了，氣球就送過來了，整個受寵若驚！
最後就以四題結束了比賽，與台清交相比可以發現實力差距之大。以及南北實力差距之大，北區題數最高為 8 題，而南區題數最高就我們 4 題。對競賽題目有興趣的話，可以到 ZeroJudge 上查看！熱血的 Morris 已將題目貼到上面，也自行產生了測試資料！
另外，比賽當天早上看到了篇文章，講述著台灣各大學目前的實力差距。成大目前似乎點慘，我想不僅外人看得出來，我們自己人應該也很清楚成大目前的實力。不過，我不認為這與電子哥的離開有關，電子哥還在時，練 ACM 的風氣就已經漸漸消失了。我想我們內部需要好好檢討原因為何，這兩年因為私人因素我幾乎不參與訓練的事宜，僅在比賽時出現，看到成大的現況，實在心有不甘。期許，我還在成大的這段期間，還能帶給成大些什麼？！