前言—個人經驗

從大學到研究所在楊老師指導下,曾參加多次的各種程式設計競賽,沒記錯了話應該是教育部所辦的4次、ACM亞洲區3次、校內2次、趨勢初賽和決賽,雖然比賽成績不盡理想,但還是有些許的經驗和感想能提供給有志參與比賽的同學參考。

在大二升大三那年第一次參加比賽,當年連一題都沒寫出來,隔年因為程式功力增加和多上了一次暑假的基礎演算法課程,並且有著熟識和良好默契的隊友,彼此的實力也相仿,所專精的領域也有所差別,再加上不錯的運氣,成功利用較短的時間寫出三題而拿到第六名的成績,後來的幾次此賽沒有多花點時間準備跟練習,所拿到的成績也就不如以往。但其實以實力和經驗來說,大四那年相較後來這幾年卻是遠遠的落後,當時真的只是靠較好的運氣和先前的準備才拿到還不錯的成績的。

比賽方式,不是對就是錯

程式設計比賽蠻特殊的一點就是評審的方式和僅有一台電腦,題目通常會有七、八題左右,而決定答對或答錯則是依照你是否100%正確的解答出評審所有的測試實例。對大多數的程式設計者來說,離開了電腦,通常都無法順利的思考程式和撰寫,而這僅能藉由事先的模擬比賽來練習。在比賽時,短短的四、五個小時中,能正確的答對最多的題目則是唯一的目標,因此,比賽時最重要的是如何能發揮三個人和一台電腦的最大力量。題目的分工和電腦的分時使用也是比賽時的重點。我們習慣是先將題目拆成三份分頭進行,第一個確定能「正確」並「快速」寫出的人便直接使用電腦撰寫,其他人則將程式寫在紙本上。如果手上的題目無法了解,則先對隊友做簡單的解釋,並交換題目看,需要時再進行討論。

一次答對不是件簡單的事,而被評審傳回錯誤確不知道錯在那,也是非常常見的問題,在比賽中短短的四、五個小時中,能藉由改正而拿到分數,卻更不容易。而一般來說,發生錯誤的原因不外乎是程式撰寫時發生了些小錯誤或是根本上的解題方式錯誤。以我們的經驗來說,當傳回錯誤時,先將程式碼印出,並由原先撰寫的人直接在紙本上檢查,而電腦則交由另一個撰寫下一題。如果確定應該不是程式的錯誤,則試著和隊友討論解題方式,再不行,也只能先暫時擱置等到有時間時再試著解決。

嘗試再嘗試

相信各位學弟妹們應該都會比我早接觸到電腦和程式設計並參加比賽,也有更多的機會嘗試和累積經驗,一開始或許會遇到些挫折,但別忘了學習過程的樂趣;比賽結果或許不如已意,但也別忘了當評審傳回答案正確的訊息時,令人激動和興奮的情緒。

漸進式的學習經驗

和各位分享一些書本上的經驗,演算法是需要很長的時間來學習和體驗其精華,通常來講,如果是有志參加比賽的同學們,一般是在大二(大一升大二)時開始學習最基本的演算法的,第一次接觸或許吸收有限(至少我是這樣),但隨著經驗的增加和每年再念一次的演算法和相關課程,雖然學的都是相似的課程,但每年卻都覺得有不同的感觸和新的想法,這就是時間和經驗的增長。以我自己為例,光是簡單的dynamic programming,也是在學了兩三(次)年和實際撰寫後才算是真正瞭解其精神,另外dynamic programming在比賽時出現率蠻高的,

程式設計實務

比賽的題目通常來自各種不同的領域,某些領域和演算法課本上的東西不是那麼的直接相關,例如影像處理、電腦圖學等,更有一些題目是數學上的問題,這部份就需要相當的經驗和數學能力才能解決,多看題目多學習些不同領域的課程,會有相當大的幫助,尤其是有幾個人能一些討論,研究題目時彼此間想法的激盪分享,會讓你有更大的進步空間和增加持續的動力,當然要找人來討論不是件容易的事,我們以前也是在老師的幫忙之下才能聚在一起討論,不知道你們是否已經找到志同道合的伙伴。除此之外,知道解答方式和是否能快速的寫出正確的程式之間還是有一段距離,思緒越清楚程式經驗越豐富將會更有幫助,欠缺足夠的程式經驗會讓許多原本撰寫上就較煩瑣的程式而無法在短短的四個小時間完全。比賽事前的準備也相當的重要,以前老師都會要求我們先寫一些基本的library,然後印成紙本比賽時帶進去,如果需要時只要重新key in,這會在比賽時節省不少的時間,而在撰寫時也能得到相當有用的經驗。某年參加比賽時,有題convex hull便是直接把library中的程式key in,再做小小的修改就成功的拿到一分。在library不夠大時,或許應用到的機率不高,但只要能用上時便是相當大的幫助,並且學習撰寫一個自己及別人都能簡單應用的library也是一件相當重要和不容易的事,雖然要花費蠻多的時間和練習,但卻非常值得親自嘗試。

演算法設計

通常要寫一個演算法時,必需先知道題目的問題、輸入和輸出,並給完整的定義,如果可以了話最好能用數學式子詳盡的寫下來,而最後才是設計演算法的部份。相信在書本上看到的演算法也都是以這樣的方式寫下來的。如果能完成這個部份,那恭喜你已經完成了設計一個演算法時的第一個工作了。這看似簡單,但試著寫看看時會發現不是那麼的容易,我現在也都還做的不是很好,你也可以試著把你寫的定義給隊友看,如果他能在不經過你任何解釋下而看懂,那就算是成功了。
Problem:
Input:
Output:

真實的問題

以下為一些個人的感想和比賽並沒有直接的關係,但在演算法的研究上我認為這是非常重要的一個觀念。在演算法書本上所能看到其實只是些最基本的部份,題目上的定義也很完整,而真正在比賽時的題目以及做研究或生活上所遭遇到的問題確不是那麼容易就能完整的定義,所以定義一個題目是第一步,也是最重要的部份。比賽時或許還好,因為這些通常都是能解決的問題,有完整的題目和固定的答案,也不需要太繁複的手續,但在處理真實的問題時,這卻可能是最困難的工作,因為你可能不能確定你所要的答案究竟是什麼,因此如何的定義題目和答案便是第一個工作,而後面才是處理有沒有解,有解了話怎麼求出,無解了話是否能退一步求出還能接受的答案(approximate algorithm, heuristic algorithm),而找出答案後如何評估其正確性更是一個難題。

結語

雖然沒有獲得好的成績,比賽時所獲得的經驗和學習練習時所學到的東西會比比賽時所得到的名次和獎金來的重要且長久,而且比賽後的悔恨也能提供你成長的動力。

嘉茂