演算法競賽

2013年8月22日，Yandex Algorithm競賽公開賽現場

算法競賽（又稱編程競賽、信息學競賽、程式設計競賽），不同於駭客松是一項智力運動，通常在互聯網上或局域網上舉行，其內容包括參與者嘗試根據提供的要求進行編程 。 參賽者被稱為競賽程序員 。算法競賽得到了多家跨國軟件和互聯網公司的認可和支持，例如Google和Facebook。

算法競賽通常涉及到主辦方向參賽者提出一組邏輯或數學問題（參賽者的數量可能從幾萬到數千不等），並且要求參賽者編寫能夠解決每個問題的計算機程序。評測主要基於解決的問題數量和編寫成功解決問題的程序所花費的時間，但也可能包括其他因素（產生的輸出質量，執行時間，程序大小等）。

歷史

已知的最古老的競賽之一是國際大學生程序設計競賽，該競賽起源於1977年，2011年中參賽者範圍已經擴大到88個國家/地區。自從2000年以來，它也同時與Internet的發展有了很強的聯繫。這促進了在網上舉辦比賽，同時也消除了地理性的問題。

概述

算法競賽的目標是編制源代碼，在有限的計算資源內來解決給出的問題。大部分的問題是屬於數學問題或者邏輯學問題。它們通常屬於下面幾個類型中的一個：組合數學、數論、圖論、幾何（很多時候是計算幾何）、字符串和數據結構。和人工智能相關的內容在某些比賽中也很會出現。

不論問題的類別，解決問題的過程都可以大致地分為兩大步驟：構思一個算法，以及使用一個編程語言來實現算法（允許使用的語言每個競賽都會不同，主要以C++，Java，Pascal等為主，但是IT企業的競賽大多會使用該企業的常用語言）。

大多數競賽中，選手只應該為每一題編寫一個源程序，這個源程序的系統調用會受到限制。一般創建新進程，訪問網絡，操作無關文件等等都是不允許的。一般情況下，選手只能使用他/她所使用的語言的標準庫（例如C++語言的STL）。

一道傳統的題目由以下幾個部分組成。下面使用大多數OJ使用的試機題目A+B問題來做簡要的闡述：

試題組成

名稱	概述	實例
題目描述	這個部分包括對需要求解的問題的描述，有時也會有一個題目背景。 一般問題並不會直接給出數學模型，而需要參賽者自己設計模型，進而求解。	給你兩個數$A,B$，請求出$A+B$的值。
輸入輸出格式	這個部分描述了程序應當怎樣讀取數據和輸出答案， 在交互式題目中，這個部分描述了程序應當怎樣與交互系統進行交互。 在某些題目中，這個部分還會包含數據範圍和限制。	輸入格式 輸入包含一行，為整數$A,B$。 輸出格式 輸出包含一行，為求得的答案。
輸入輸出樣例	這個部分給出了一或多組正確的輸入輸出，選手可以用來簡單地檢驗他們的程序。 但是這些數據往往非常簡單，難以檢查出選手程序中的所有錯誤，同時它們往往規模較小。	輸入樣例 ${\texttt {1}}$ ${\texttt {2}}$ 輸出樣例 ${\texttt {3}}$
數據範圍	大部分的競賽都會有這個部分，它描述題目的數據範圍和特殊性質。最後的測試數據必定滿足這一限制。 在如國際資訊奧林匹亞競賽等有子任務的比賽中它會描述了各個子任務的數據範圍和（如果有）特殊性質。如果選手不能解決整個問題，那麼他們可以嘗試只解決一部分測試數據以獲得該子任務的分數。	對於 50% 的數據，保證 $1\leq A,B\leq 10^{6}$ 對於全部數據，保證$1\leq A,B\leq 10^{9}$。

試題

在一般的競賽中，試題有以下幾種。

• 傳統題要求程序從輸入讀入一些數據，進行求解後輸出，這是最常見的題目。

• 提交答案題會事先下發輸入數據，選手需要通過任意方法（包括計算器、手算、編寫程序等）進行求解，並提交答案文件。

• 交互題會讓選手程序與交互系統進行交互，一般會通過輸入輸出或者調用給定函數庫來實現。例如 NOI 2019. I 君的探險 （頁面存檔備份，存於網際網路檔案館）

• 通信題要求選手編寫兩個相互協作的程序解決問題。例如 UER #8. 打雪仗 （頁面存檔備份，存於網際網路檔案館）

賽制與測評

在大多數競賽中，評測是通過主辦者的計算機進行的，這通常稱為裁判系統。裁判會對選手提交的代碼通過一組（通常是秘密的）測試數據進行測試。測試方法是所謂的黑箱測試，也即，裁判不關心選手的程序是如何實現的，而只要求它能夠在規定的限制內正確地解答出問題。

大多數競賽中，選手在提交代碼之後能夠即時獲取反饋，一般反饋分為以下幾種：

• AC (Accepted)：通過，選手程序完成了任務。
• PE (Presentation Error)：輸出格式錯誤，選手程序輸出答案正確，但是格式錯誤（例如，行中間出現空格），在某些競賽中被視作 WA。
• WA (Wrong Answer）：答案錯誤，選手程序儘管成功運行，但並沒有成功求解問題。
• TLE (Time Limit Exceeded)：超出時間限制，選手程序運行時超出了題目給出的時間限制。
• MLE (Memory Limit Exceeded)：超出空間限制，選手程序所使用的空間超過了題目給出的內存限制。在極少數競賽中（例如USACO）被視作 RE。
• RE/RTE (Runtime Error) ：運行時錯誤，選手程序崩潰。
• OLE (Output Limit Exceeded) ：輸出超過限制，選手程序輸出了過多內容。
• CE (Compile Error) ：編譯出錯，選手程序沒有成功編譯。
• IE/SE (Internal Error/System Error) ：內部錯誤，評測系統出錯。這時選手應當報告比賽主辦方。某些平台細分為多種 （例如 Compilation Failed 編譯器錯誤， Denial of Judgement 拒絕評測，Judgement Failed 評測失敗，Checker Crashed 比較器崩潰等）。

另一些競賽 （例如NOI）不提供即時反饋。系統在競賽結束後會統一評測。

有些競賽只有「對」和「不對」之分，沒有部分分。例如ICPC。而另一些競賽會按照測試點或者子任務分別給分。有時，還會按照解的優劣性進行部分給分。

對於傳統題，一般判斷答案正確的方法是在過濾行末空格和文末回車之後逐行比對，但是，有的題目會使用特製的比較器來進行測評。對於其他類型的題目則一般通過比較器進行給分。

大多數競賽要求選手程序從標準輸入讀入數據，將答案寫到標準輸出，而早期競賽和NOI系列賽則要求選手從給定的輸入文件讀入數據，將答案寫到輸出文件。

主要競賽

比賽分為短期和長期兩種。

短期

中國

• NOI - 中國 自 1984 年起舉辦的競賽。

香港

• 香港電腦奧林匹克 - 香港 自 1997 年起舉辦的競賽

台灣

• 高級中學數理及資訊學科能力競賽 - 臺灣 自 1999 年起舉辦的競賽
• 臺灣國際奧林匹亞競賽 - 臺灣用於選拔國際資訊奧林匹亞選手的比賽，由國立臺灣師範大學資訊工程學系主辦

國際/其他地區

• 國際大學生程序設計競賽 (ICPC) - 歷史最悠久的競賽之一，由大學生三個人組隊參加；
• CodeChef - 從2009年起，每個月會有兩場短競賽 和每年一場的CodeChef SnackDown；
• Codeforces Round - 一般是兩小時，每星期舉行；
• Facebook Hacker Cup - 由 Facebook 提供和支持的競賽；
• HackerRank - 數種競賽；
• Google Code Jam - 由 Google 提供和支持的競賽
• IEEEXtreme Programming Competition - IEEE為其學生會員舉辦的競賽。
• 國際信息學奧林匹克 - 面向中學生的最古老競賽之一。

上述大多數競賽都按輪舉行，在NOI, IOI, ICPC等競賽中，獲得好成績的選手可以獲得金牌、銀牌或銅牌。

長期

• HackerRank Week of Code
• Topcoder 馬拉松

在線資源

有許多在線評測系統可以提供訓練資源。以下僅列出較常見的評測系統。

非中國地區

• Codechef是印度的在線評測系統，也提供比賽。
• AtCoder是日本的在線評測系統，提供比賽。
• Codeforces是俄羅斯的評測系統，提供比賽。
• UVa是西班牙的評測系統，收錄了大量 ICPC 的真題，題目質量較高。現在已經去掉了這個名稱而直接叫做Online Judge。
• SPOJ是波蘭的評測系統。
• SZKOPUL收錄了波蘭信息學奧林匹克的很多試題。

中國地區

• POJ是北京大學的評測系統。收錄了不少亞洲區 ICPC 真題。
• ZOJ是浙江大學的評測系統。
• LibreOJ是由網名 Menci 的 OI 選手維護的在線評測系統，理念是自由開放。
• UOJ是由網名 vfleaking 的 OI 選手維護的在線評測系統，理念是接受一切試題的評測。
• 評測鴨是由王逸鬆開發的評測系統，能夠將時間計算精確到納秒。
• 洛谷是上海洛谷網絡科技有限公司的評測系統，提供收費的網校服務。
• 香港電腦奧林匹克競賽網上評測系統 (HKOI Online Judge) 原為集訓隊的訓練平台，現已開放予全港中學使用。
• AcWing 是北京睿新奇知科技有限公司旗下品牌，擁有優秀的算法在線課堂，以及 AC Saber。

臺灣地區

• Zerojudge是台灣最大的評測系統，題目來源較為廣泛。
• Green Judge是由台中女中建立的評測系統，以新手向題目為主
• TIOJ是建國中學的評測系統。