Competitive Programming

Competitive Programming

The International Collegiate Programming Contest (ICPC)」是針對全世界大專院校學生的比賽,考驗選手臨場的演算法設計能力、程式編寫能力。

ICPC帶動了演算法程式設計的風氣。世界上許多大專院校的資訊系所,仿照ICPC比賽模式,紛紛自行開發出即時線上比賽系統,能夠自動批改、評分、計時、統計。學生不必齊聚一堂,而是透過網路,互相切磋程式設計技巧。比賽結束之後,將比賽題目編列題庫,開放自動批改程式的功能,供學生賽後練習檢討。這套系統大家稱呼為「Online Judge」。

從事這項活動,不僅可以熟悉程式設計、學習演算法、鍛鍊智力,還可以培養自主學習與獨立解題的能力──此即程式設計師的核心價值。因此這項活動逐漸獲得大家重視。產業界舉行演算法競賽,發掘優異人才;學術界開設課程,促進演算法發展。這項活動大家稱呼為「Competitive Programming」。

International Collegiate Programming Contest

ICPC是資訊界規模最大、歷史最悠久的競賽。從1977年開始,每年在世界各地舉辦初賽,選拔表現優秀的隊伍,角逐世界總決賽。最近幾屆競賽有上千所學校、數萬名選手參加。

ICPC是一個氣氛活潑的競賽。整個賽事包含許多活動,主軸當然是現場上機競賽,但是另外還有娛樂表演、晚餐宴會、城市遊覽等等行程。整個賽事過程為期兩至三天,有吃有玩,遊樂的成分比競賽的成分還多,對於參賽選手來說是相當新鮮的體驗。

ICPC的競賽方式是三人一隊,並且需要一位同校教授作為領隊教練。教練的主要作用,是負責向大會接洽賽事行程,替選手打點賽事期間的生活細節,讓選手無後顧之憂,得以傾盡全力比賽。教練就如同經紀人的角色。

現場上機競賽,所有隊伍聚集於會場,一支隊伍分配一張桌子、三張椅子、一臺電腦、一份英文題本。主持人宣布比賽開始之後,所有隊伍同時開始作答,選手必須迅速閱讀題本當中的問題,然後編寫程式解決問題,將程式碼上傳給裁判批改。

所有作答皆是即時批改,幾分鐘內回覆結果,結果只有對與錯,答錯還可以再答。成績的計算方式,是以答對題數作為排名依據;但是作答的錯誤次數、上傳答案的時刻,統統列入扣分,作為次要的排名依據。因此選手要盡力答出問題,也要盡快答出問題,還要避免答錯問題又一錯再錯。實力在伯仲之間的隊伍,勝負的差距往往取決於審題與答題的效率。動作慢人一步,或者大意發生失誤,就很可能名落千丈。

選手有五小時時間,要解出十道左右的演算法問題,期間可以喝水、外出上廁所、享用大會提供的奢華點心、在題本上塗鴉、把題本拆了摺紙鶴、睡覺、談情說愛、玩電腦遊戲;唯一的限制,就是不得與隊伍之外的人交流。

比賽規則看似輕佻,但是比賽過程其實非常緊迫。五小時時間解十道左右的問題,電腦卻只有一臺。即便是技藝高超的選手,也幾乎無暇休息,必須分工合作爭取時間。通常一人隨時坐在電腦前作答,充分運用電腦,發揮時效;另外兩人則在旁解讀其餘題目,在腦中羅織解法,伺機輪換上陣。五小時的比賽過程,選手克服環境限制、調適心理壓力、發揮大腦潛能,也可以說是一場精神的對抗賽。

競賽過程還有許多有趣的地方,留給參賽選手們自行體驗吧!

ICPC官方消息:ICPCNews
ICPC亞洲區指導員:西杰阿雄的博客
日本非官方消息:ACM-ICPC Japanese Alumni Group
中國非官方消息:ACM/ICPC信息站
選手感想:ACM-ICPC Asia Jakarta Regional Contest 2017 沿途紀實與心得
教練感想:2016 ACM-ICPC World Finals — MZ’s log
精選題解:關於競程日記 2019
歷年題庫:ICPC Live Archive

根據規定,ICPC區域賽必須要有全國性(或者兩省以上)的預賽。台灣歷年都是以NCPC作為預賽,然而實際上NCPC根本就不是預賽。會有這種現象,主要原因是台灣的參賽隊伍十分稀少,無從篩選隊伍。直至2015年,台灣才開始正式舉辦網路預賽,跟隨亞洲各國的比賽模式,時序如下:

一、區域預賽(網路賽):ICPC台灣區負責人組織比賽,大專院校教授熱情協助。國內外選手透過網路進行較量。比賽結束之後,根據當年承辦人員的戰鬥力,選出40至80隊參加現場賽。由於國外隊伍出國參加現場賽,需要時間打點準備,因此網路賽往往提早舉辦,3至6個月前就會舉辦。

二、全國賽:與ICPC無關。台灣教育部舉辦的NCPC,全國學生一較高下。成績優秀的隊伍,教育部全額補助參加ICPC。

三、區域正式賽(現場賽):請參考前面介紹的內容,國內外選手齊聚一堂進行較量。比賽結束之後,主辦單位依照複雜的公式,評量各個區域賽的戰鬥力,至少選出1隊,參加世界總決賽。

四、世界總決賽:從全世界篩選一百多隊參加總決賽,從五大洲輪流選擇一間學校作為比賽地點。台灣大專院校以往實力較差,總是被國外學校痛宰,鮮少晉級總決賽。直到近十年才有改善跡象,與國外學校互有進退(一群無名英雄前仆後繼苦心經營數年的成果);同時也積極的參與其他國家的區域賽,爭取世界總決賽門票。目前台灣僅台灣大學、交通大學有能力進入總決賽。

演算法競賽

2019TW2018TW2017TW International Collegiate Programming Contest 縮寫:ICPC 對象:大專院校學生    (學士班一年級至碩士班一年級) 時間:台灣站11~12月    亞洲各站是8~12月    世界總決賽是隔年5~7月 主辦:ICPC Foundation 承辦:台灣賽區由台灣大專院校輪流承辦
Google Code Jam 對象:社會大眾 時期:4月~7月
TopCoder Open 對象:社會大眾 時期:每年一次,時間不定 比賽項目相當多元,其中一個項目是演算法競賽。
Facebook Hacker Cup 對象:社會大眾 時期:每年一次,時間不定
Taipei HP CodeWars 對象:高中高職五專(一到三年級)學生 時期:每年一次,時間不定
Internet Problem Solving Contest 對象:社會大眾 時期:5~6月
ACM SIGMOD Programming Contest 對象:大專院校學生 時期:2~4月
NCPC 201920182017 全國大專電腦軟體設計競賽 縮寫:NCPC 對象:台灣大專院校學生 時間:9~10月 主辦:由臺灣師範大學與中山大學輪流辦理
NCPU 201920182017 全國私立大專院校程式競賽 縮寫:NCPU 對象:台灣私立大專院校學生 時間:6月 主辦:各私立大學輪流辦理 備註:ICPC台灣站衍生賽事
NCTU 201920182017 全國科技大專院校程式競賽 縮寫:NCTU 對象:台灣科技大專院校學生 時間:6月 主辦:虎尾科技大學 備註:ICPC台灣站衍生賽事
NPSC 網際網路程式設計全國大賽 縮寫:NPSC 對象:台灣高中學生、國中學生 時期:11~12月 主辦:台灣大學

演算法例賽

TopCoder簡介
美國規模最大的程式競賽網站,其中包含了演算法例賽。

Codeforces
俄國最大的演算法例賽。

CodeChef
印度最大的演算法例賽。

AtCoder
日本最大的演算法例賽。

ITSA & PTC 線上程式設計競賽
台灣最大的演算法例賽。台灣教育部提供的例行賽事。

競程日記
台灣學生自行舉辦的例賽。

演算法題庫

Kattis
瑞典Kattis公司建立的Online Judge。

URI Online Judge
巴西do Alto Uruguai e das Missões大學的Online Judge。

Sphere Online Judge
波蘭Sphere實驗室建立的Online Judge。

HDU Online Judge
中國杭州电子科技大学的Online Judge。

Timus Online Judge
俄國Ural大學的Online Judge。

UVa Online Judge
西班牙Valladolid大學的Online Judge。最古老的Online Judge。

高中生程式解題系統 ZeroJudge
台灣高雄師大附中建立的Online Judge。

UVa Online Judge工具網站

uHunt
可以查詢自己在UVa Online Judge的解題進度、世界排名。
整理了一套題目清單,適合初學者循序練習。輸入使用者名稱就會出現。

uDebug
提供UVa Online Judge解答的執行檔,
自行輸入資料,可以生成正確輸出,進而測試自己的程式。

Lucky貓的ACM園地Ruby兔的ACM園地Unfortunate狗的ACM園地uniDog的ACM園地
UVa Online Judge題目中譯!
非常偉大的工作,請大家要心懷感激!

Problem Classification on Spanish Archive
題目分類。

程式設計訓練

The 10 Best Coding Challenge Websites for 2018
綜合介紹。

PAT计算机程序设计能力考试
中國的證照考試。

CPE大學程式能力檢定
台灣某些教授聯手搞出來的證照考試,你懂的。

演算法競賽營隊

臺灣大學程式解題競賽培訓營
熱心學生自動自發努力辦理的營隊。

交大競技程式訓練冬令營、夏令營
熱心老師和學生自動自發努力辦理的營隊。

演算法競賽講義

板橋高中資訊社演算法講義
熱心學生努力彙整的教材。

建國中學資訊科培訓講義
熱心學生努力彙整的教材。

交通大學PSPT課程講義
熱心老師努力彙整的教材。

成功大學ACM課程講義
熱心老師和學生努力彙整的教材。

OI Wiki
熱心網民努力彙整的教材。

Stanford CS 97SI: Introduction to Competitive Programming Contests
熱心學生努力開設的課程。

CMU CS 15-295: Competition Programming and Problem Solving
熱心老師努力開設的課程。

Competitive Programmer's Handbook
芬蘭IOI國家隊訓練教材

OI公共圖書館
中國IOI國家隊技術報告

演算法競賽書籍

數學思考
九章出版社

How to Solve It
George Pólya
譯本《怎樣解題》

Competitive Programming
Steven Halim, Felix Halim
新加坡演算法競賽名著

Guide to Competitive Programming:
Learning and Improving Algorithms Through Contests
Antti Laaksonen
芬蘭演算法競賽名著

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
구종만
韓國演算法競賽名著
譯本《算法问题实战策略》

プログラミングコンテストチャレンジブック
秋葉拓哉、岩田陽一、北川宜稔
日本演算法競賽名著
譯本《培養與鍛鍊程式設計的邏輯腦:世界級程式設計大賽的知識、心得與解題分享》

算法竞赛入门经典
刘汝佳
中國演算法競賽名著
譯本《打下好基礎:程式設計與演算法競賽入門經典》

算法竞赛入门经典——训练指南
刘汝佳、陈锋
中國演算法競賽名著
譯本《提升程式設計的解題思考力─國際演算法程式設計競賽訓練指南》

演算法競賽書籍:我沒讀過的新書

算法竞赛进阶指南

信息学奥赛一本通 提高篇

CCF中学生计算机程序设计 专业篇

演算法競賽相關連結

Awesome Competitive Programming
github的awesome系列,無論什麼亂七八糟的通通都有。

台灣資訊培訓相關資源彙整
以 台灣高中生 為出發點的 資訊培訓相關資源彙整。