演算法筆記

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 」。資源非常豐富。

Lucky貓的ACM園地、Ruby兔的ACM園地、Unfortunate狗的ACM園地、uniDog的ACM園地UVa Online Judge題目中譯！非常偉大的工作，請大家要心懷感激！uHunt可以查詢自己在UVa Online Judge的解題進度、簡單題列表、世界排名等等。另外也整理了一套題庫，適合初學者循序練習。輸入使用者名稱就會出現。是你不得不知道的網站！uDebug提供UVa Online Judge題目解答的執行檔，自行輸入資料，可以生成正確輸出，進而測試自己的程式。World of 7uHunt站長的兄弟所製作。整理了UVa Online Judge題目的解法提示、演算法動畫。Problem Classification on Spanish Archive題目分類。

演算法題庫

UVa Online Judge西班牙Valladolid大學的Online Judge。是最古老也是全世界最知名的Online Judge，題庫目前約有4000+題。題目類型非常廣泛。絕大部分的題目難度偏易，適合初學者磨練程式設計功力。ACM-ICPC Live Archive專門收集ACM-ICPC的比賽題目，依照年份與賽區進行編目。可惜的是題庫尚未收集完整，尚待大家合力完成。PKU JudgeOnline中國北京大學的Online Judge。中國最大的Online Judge。題目類型偏向演算法競賽，可以找到比賽常見題型。好處是網路上能輕鬆找到中文的解題報告。Timus Online Judge俄國Ural大學的Online Judge。俄國最大的Online Judge。有比較進階的演算法題目，難度偏高。Sphere Online Judge波蘭Sphere實驗室建立的Online Judge。波蘭最大的Online Judge。會員可自創題目，題目很有特色，但是品質良莠不齊。URI Online Judge巴西最大的Online Judge。高中生程式解題系統 ZeroJudge台灣高雄師大附中建立的Online Judge。台灣最大的Online Judge。

演算法例賽

TopCoder，簡介全世界規模最大的程式競賽網站，其中包含了演算法競賽。Codeforces俄國最大的演算法例賽。題目較有挑戰性。賽後會提供詳細的題目講評，是個自主學習的好地方！CodeChef印度最大的演算法例賽。AtCoder日本最大的演算法例賽。BestCoder中國最大的演算法例賽。由中國杭州电子科技大学維護。ITSA & PTC 線上程式設計競賽台灣最大的演算法例賽。台灣教育部提供的例行賽事。

演算法面試考題

leetcode世界知名的演算法面試考題網站。想要省時省力的面試主考官從裡面挑題目，於是求職者不得不去練習這些題目。然而工作上用不到這些知識，已經發展到了病態的地步。PAT计算机程序设计能力考试中國的證照考試。CPE大學程式能力檢定台灣某些教授聯手搞出來的證照考試，你懂的。

演算法競賽

2016TW、2015TW、2014TW	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月
Taipei	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 Live ArchiveACM-ICPC官方消息：https://www.facebook.com/ICPCNewsACM-ICPC亞洲區指導員：西杰的博客与阿雄台灣ACM-ICPC非官方協會：ACM-ICPC Contest Council for Taiwan中國ACM-ICPC非官方協會：ACM-ICPC中国区竞赛指导委员会中國非官方消息：ACM/ICPC信息站日本非官方消息：ACM-ICPC Japanese Alumni Group教練感想：2016 ACM-ICPC World Finals — MZ’s log

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

一、區域預賽（網路賽）：由 ACM-ICPC 台灣區負責人負責組織比賽，各大專院校教授熱情協助。國內外選手透過網路比賽，最後根據當年承辦人員的戰鬥力，從中選出 40 至 80 隊，參加現場賽。由於國外隊伍出國參加現場賽，需要時間打點準備，所以網路賽往往很早舉辦， 3 至 6 個月前就會舉辦。

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

三、區域正式賽（現場賽）：請參考前面介紹的內容，國內外選手齊聚一堂進行較量。最後依照複雜的公式和規則，評量各個區域的戰鬥力之後，從各賽區選出至少 1 隊，參加世界總決賽。

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

營隊

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

講義

台大資訊系資訊之芽算法班熱心學生自動自發舉辦的高中營隊以及教材。板橋高中資訊社演算法講義熱心學生自動自發努力彙整的教材。建國中學資訊科培訓講義熱心學生自動自發努力彙整的教材。交通大學PSPT課程講義熱心老師自動自發努力彙整的教材。成功大學ACM課程講義熱心學生自動自發努力彙整的教材。Stanford CS 97SI: Introduction to Competitive Programming ContestsStanford大學開設的課程。競程日誌熱心網友的解題心得分享資料結構與演算法/leetcode/lintcode題解面試題目教學。

書籍

	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/這是一套系列作，目前只出版兩本。知識水平是所有書籍之中最高的。想要躋身高手行列的人，絕對不要錯過此系列作。第一本書有繁體中文譯本《打下好基礎：程式設計與演算法競賽入門經典》。第二本書有繁體中文譯本《提升程式設計的解題思考力─國際演算法程式設計競賽訓練指南》。