Competitive Programming
「 Association for Computing Machinery (ACM) 」是一個致力於電腦科學教育的協會,出版大量的專業期刊文獻,舉辦重大的計算機科學會議,在資訊界舉足輕重、名聞遐邇。
ACM 每年度都會舉辦一次「 The ACM-ICPC International Collegiate Programming Contest (ACM-ICPC) 」,是一個給全世界大專院校學生參加的演算法程式設計比賽,比賽目的在於考驗選手臨場的演算法設計能力、程式編寫能力。 ACM 首先在世界各地舉辦初賽,再從各個賽區選拔出表現優秀的隊伍,角逐世界總決賽。
ACM-ICPC 帶動了演算法程式設計的風氣。世界上許多大專院校的資訊系所,仿照 ACM-ICPC 的比賽模式,紛紛自行開發出即時線上比賽系統,能夠自動批改、評分、計時、統計。學生不必齊聚一堂,藉由網際網路,就可以相互切磋程式設計技巧。比賽結束之後,便將比賽題目編列題庫,開放線上批改程式的功能,供學生賽後練習檢討。這套系統大家普遍稱呼為「 Online Judge 」。
從事這項活動,不僅可以熟悉程式設計、學習演算法、鍛鍊智力,還可以培養自主學習與獨立解題的能力 ── 此即程式設計師的核心價值。
這項活動開始獲得大家重視。產業界舉行演算法競賽,發掘優異人才;學術界開設課程,促進演算法的研究發展。由於競賽的緣故,大家將這項活動稱呼為「 Competitive Programming 」。
UVa Online Judge 工具網站
最古老、最有知名度的 Online Judge ,是由西班牙知名的瓦雅多利大學「 Universidad de Valladolid (UVa) 」開發的「 UVa Online Judge 」。資源非常豐富。
演算法題庫
演算法例賽
演算法面試考題
演算法競賽
![]() | ACM International Collegiate Programming Contest縮寫:ACM-ICPC對象:大專院校學生 (學士班一年級至碩士班一年級)時間:台灣站11~12月 亞洲各站是8~12月 世界總決賽是隔年5~7月主辦:Association for Computing Machinery承辦:台灣賽區由台灣大專院校輪流承辦 |
![]() | ACM SIGMOD Programming Contest對象:大專院校學生時期:2~4月 |
![]() | Google Code Jam對象:社會大眾時期:4月~7月 |
TopCoder Open對象:社會大眾時期:4月~8月比賽項目相當多元,其中一個項目是演算法競賽。 | |
![]() | Facebook Hacker Cup對象:社會大眾時期:1月~3月 |
![]() | HP CodeWars對象:高中學生、大專院校學生,各分公司就地舉辦時期:台北4月 |
![]() | Internet Problem Solving Contest對象:社會大眾時期:5~6月 |
NCPC2016、2015、2014 | 全國大專電腦軟體設計競賽縮寫:NCPC對象:台灣大專院校學生時間:9~10月主辦:教育部承辦:由臺灣師範大學與中山大學輪流辦理 |
NCPU2016、2015、2014 | 全國私立大專院校程式競賽縮寫:NCPU對象:台灣私立大專院校學生時間:6月主辦:各私立大學輪流辦理備註:ICPC台灣站衍生賽事 |
NCTU2016 | 全國科技大專院校程式競賽縮寫:NCTU對象:台灣科技大專院校學生時間:6月主辦:各科技大學輪流辦理備註:ICPC台灣站衍生賽事 |
NPSC | 網際網路程式設計全國大賽縮寫:NPSC對象:台灣高中學生、國中學生時期:11~12月主辦:科技部承辦:台灣大學 |
ACM International Collegiate Programming Contest
資訊界規模最大、歷史最悠久的競賽,最近幾屆競賽皆有上千所學校、數萬名選手參加。
ACM-ICPC 是一個氣氛相當活潑,非常具有特色的競賽。一場 ACM-ICPC 的賽事,由許多活動所組成,主軸當然是現場上機競賽,另外還有安排晚餐宴會、娛樂表演、城市遊覽等行程。整個賽程為期兩至三天,過程有吃有玩,遊樂的成分比競賽的成分還多,對於參賽選手來說是相當新鮮的體驗。活動細節請參考歷年的 ACM-ICPC 區域賽網站。
ACM-ICPC 的競賽方式是三人一隊,並且要有一位同校教授作為領隊教練。教練的主要作用,是負責向大會接洽賽事行程,替選手打點賽事期間的生活細節,讓選手無後顧之憂,得以傾盡全力比賽,教練就如同經紀人的角色。另外,報名時可以額外登記一名後備隊員,發生緊急狀況時得替補上陣。
現場上機競賽的過程,是所有隊伍聚集於會場,一支隊伍分配一張桌子、三張椅子、一臺電腦、一份英文題本。開賽後所有隊伍同時開始作答,選手必須迅速調校好電腦環境,然後編寫程式解決問題,將程式碼上傳給裁判批改。
所有作答皆是即時批改,幾分鐘內回覆結果,結果只有對與錯兩大類,答錯還可以再答。成績的計算方式,是以答對題數作為主要的排名依據;但是作答的錯誤次數、上傳答案的時刻,統統列入扣分,最後作為次要的排名依據。因此選手除了要盡力答出問題,也要盡快答出問題,還要盡量避免答錯問題又一錯再錯。實力在伯仲之間的隊伍,勝負的差距往往取決於審題與答題的效率。動作慢人一步,或者大意發生失誤,就很可能名落千丈。
選手有五小時時間,要解出十道左右的演算法問題,期間可以喝水、外出上廁所、享用大會提供的奢華點心、在題本上塗鴉、把題本拆了摺紙鶴、睡覺、談情說愛、玩電腦遊戲;唯一的限制,就是不得與隊伍之外的人交流。
比賽規則看似輕佻,但是事實上,五小時時間解十道左右的題目,電腦卻只有一臺,所以比賽過程是非常緊迫的,就算是技藝高超的選手,也幾乎無暇休息,必須分工合作、爭取時間。通常是一人隨時坐在電腦前作答,充分運用電腦,發揮時效;另外兩人則在旁解讀其餘題目,在腦中羅織解法,伺機輪換上陣。五小時的比賽過程,選手克服環境限制、調適心理壓力、發揮大腦潛能,也可以說是一場精神的對抗賽。
至於教練必須在會場外等待,不得與選手交談。不過教練們可以彼此交流,也可以觀戰和吃點心。現場上機競賽可以說是教練在整個賽程當中最輕鬆的時刻,也是辛苦之後驗收成果的時刻。
現場上機競賽還有許許多多的有趣的地方,此處只做初步介紹,詳細過程留給各位選手們自行體驗吧!
根據規定, ACM-ICPC 區域賽必須要有全國性(或者兩省以上)的預賽。台灣歷年都是以 NCPC 作為預賽,然而實際上 NCPC 根本就不是預賽。會有這種現象,主要原因是台灣的參賽隊伍十分稀少,無從篩選隊伍。直至 2015 年,台灣才開始正式舉辦網路預賽,跟隨亞洲各國的比賽模式,時序如下:
一、區域預賽(網路賽):由 ACM-ICPC 台灣區負責人負責組織比賽,各大專院校教授熱情協助。國內外選手透過網路比賽,最後根據當年承辦人員的戰鬥力,從中選出 40 至 80 隊,參加現場賽。由於國外隊伍出國參加現場賽,需要時間打點準備,所以網路賽往往很早舉辦, 3 至 6 個月前就會舉辦。
二、全國賽:與 ACM-ICPC 無關。台灣教育部舉辦的 NCPC ,全國學生一較高下。成績優秀的隊伍,教育部全額補助參加 ACM-ICPC 。
三、區域正式賽(現場賽):請參考前面介紹的內容,國內外選手齊聚一堂進行較量。最後依照複雜的公式和規則,評量各個區域的戰鬥力之後,從各賽區選出至少 1 隊,參加世界總決賽。
四、世界總決賽:每年都從世界五大洲輪流選擇一間學校,作為主辦學校;從全世界篩選一百多隊參加總決賽。以往台灣大專院校實力較差,總是被國外學校痛宰,鮮少晉級總決賽。直到近年才有改善跡象,與國外學校互有進退(一群無名英雄前仆後繼苦心經營數年的成果);同時也積極的參與其他國家的區域賽,爭取其他賽區的總決賽門票。目前台灣僅台灣大學、交通大學有能力進入總決賽。
營隊
講義
書籍
![]() | Discrete Mathematics and Its ApplicationsKenneth RosenMcGraw-Hill離散數學,資工系用書,演算法的數學知識。此書含有許多程式解題的基礎概念。細讀此書,對程式解題有一定幫助。此書有繁體中文譯本。 |
![]() | 數學思考台北市建國高中第49屆314班合譯九章出版社很有趣的數學書籍,教導如何解決數學問題。書中提到的思考方式,其實和程式解題是相通的。這本書由《Thinking Mathematically》改著,原書作者為John Mason。 |
![]() | How to Solve ItG. PólyaPrinceton University Press經典的數學教育著作。這本書有繁體中文譯本《怎樣解題》。 |
![]() | 名題精選百則:技巧篇冼鏡光儒林出版社收集程式設計的經典問題,而且這些問題不會用到特殊的資料結構與演算法。題目大多小巧精緻,非常具有啟發性。 |
![]() | Cracking the Coding InterviewGayle Laakmann McDowellCareerCup收集面試問題,其中包含許多演算法益智問題!這本書有繁體中文譯本《來自程式的試鍊:專為程式開發人員所寫的技術面試完全攻略》。 |
![]() | Competitive ProgrammingSteven Halim, Felix HalimLulu世界上第一本演算法競賽教科書!詳細介紹競賽常用演算法,精心挑選大量UVa Online Judge練習題,配有追蹤解題進度的網站UVa Hunting,規劃相當完善的教材。 |
![]() | 將演算法競賽的所有經典主題分門別類,依照學習順序編排例題,仔細說明解題思路。這本書有簡體中文譯本《算法问题实战策略》。 |
![]() | プログラミングコンテストチャレンジブック秋葉拓哉、岩田陽一、北川宜稔マイナビ選錄大量題目,以題目為主角,介紹各種演算法。這本書有繁體中文譯本《培養與鍛鍊程式設計的邏輯腦:世界級程式設計大賽的知識、心得與解題分享》。 |
![]() ![]() | 算法竞赛入门经典刘汝佳清华大学出版社算法竞赛入门经典——训练指南刘汝佳、陈锋清华大学出版社http://code.google.com/p/aoapc-book/這是一套系列作,目前只出版兩本。知識水平是所有書籍之中最高的。想要躋身高手行列的人,絕對不要錯過此系列作。第一本書有繁體中文譯本《打下好基礎:程式設計與演算法競賽入門經典》。第二本書有繁體中文譯本《提升程式設計的解題思考力─國際演算法程式設計競賽訓練指南》。 |
联系客服