認識競技程式
什麼是競程?
競程就是競技程式的縮寫,英文則是 competitive programming,簡稱 CP。算是資訊領域的分支,亦是有趣的學生活動之一。這領域近年來越來越熱門,對於升大學、考研究所、找工作都很有幫助,然而大多數人在資料結構與演算法相關課程看到一些基本的題目,就被嚇到而不敢跳進這個領域
參與競程你會需要…
- 程式能力: C/C++ (八成)、Python (or Java)
- 熟悉演算法: 二分搜尋、greedy、暴搜、dp、分治法、…
- 熟悉資料結構: 線段樹、樹狀陣列(數組)、雜湊表、字串(還有他的演算法)、…
- 數學能力: 數論(取mod)、排列組合、位元運算、高中幾何、線性代數(向量)、圖論
- 英文閱讀能力: 大學才要用到,因為題目都是英文
以上天花亂墜一堆東西,但實際上最需要的只有兩個東西: 思維能力、程式實作能力
競賽內容
簡介
競程不像寫網站、遊戲等比較大的專案需要注意美觀、使用者需求等,只有程式的輸出輸入正確與否而已。競程比賽會有很多題目,每一題不外乎就是要寫出符合題述的程式
一個競程題目會有:
其中限制這點非常重要、這會影響到我們需要用到什麼演算法或資料結構
舉例
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
程式實作
輸入
輸出
送出結果
在寫出程式並送出之後,網站或系統會在他的主機端塞給你的程式一些測資,少則數個,多則一百個。最後都會反饋出以下結果:
- AC : Accept,代表所有測資皆正確,通過
- WA : Wrong Answer,代表有測資是錯誤的,我們通常會念作「哇」,此題沒過
- TLE : Time Limit Exceed,代表有測資花太多時間,你的程式是烏龜吧,此題沒過
- MLE : Memory Limit Exceed,代表你的程式用到太多空間,太胖了要減肥啦,此題沒過
- RE : Runtime Error,代表記憶體戳到不該戳的位置 (或其他原因),此題沒過
- CE : Compile Error,代表你的程式語法錯了,此題沒過
有什麼競賽?
主要競賽
IOI 賽制
高中的競賽都是 IOI 賽制,個人賽,一題有對一些測資就可以拿部分分數
- 校內資訊學科能力競賽: 校內初選,前4可以被推派出去比賽
- 臺北市資訊學科能力競賽: 內中限額4名學生,因此要經過校內競賽選拔
- TOI: 臺灣資訊奧林匹亞,挑選手進 IOI,可藉由 APCS 或是縣市資訊學科能力競賽推薦
- IOI: 國際資訊奧林匹亞,臺灣每次最多只有四個名額
ICPC 賽制
大學的競賽都是 ICPC 賽制,團體賽(三人),所有測資都需要答對才有分數
- NCTU: 僅限科技大學
- NCPU: 僅限私立大學
- TOPC: ICPC 臺灣地區賽的前導賽
- NCPC: 僅限國立大學,分初賽與決賽
- Taiwan ICPC Regional: 可藉由上述四種比賽推薦取得比賽資格,基本上能進去比賽就已經很厲害了
- ICPC World Final: 競程最高殿堂,取 Regional 的前兩名推薦
檢定
線上競賽
- Codeforces: 每周都會有競賽,難度分為Div 4、3、2、1,其中 Div 1 最難
- AtCoder: 這是日本的網站,每週都有 AtCoder Beginner Contest,難度親民
私人企業競賽
線上題庫
中文題庫
- Zerojudge 高中生程式解題系統: 水題很多,怪題也不少,但是匯集了許多不同題庫的題目,也有很多競賽、檢定題目,像是 APCS 題就很齊全,上面也有相當多題解可以參考,新手友善的一個題庫
- TIOJ: 建中題庫,對新手非常不友善
- Green Judge: 好像在我高二的時候就一直開不起來,似乎是死掉了
- 洛谷: 對岸的題庫,題目非常齊全,想找到任何觀念的裸題都可以找的到
英文題庫
- CSES: 每一題都是精華中的精華,如果想要磨練基本競程題型一定要刷最少一百多題,要精熟差不多需要 250 題
- Codeforces: 有很多不同國家地方的題目
- Leetcode: 企業愛看的題庫,許多 code interview 都會參考裡面的題型
參與競程你會獲得…
程式與思維能力提升
經過長期的磨練,會發現程式與思維能力有所提升
這是顯而易見的
課業
大學資工的必修課都會瞬間變得超簡單,也比較容易給同學、教授留下好印象
高中的話我不知道
升學
在資訊領域到底有誰不愛會寫程式的人啦
大學、研究所都是搶著要的
我有個打競程的學長,在公司面試時寫 code 快到被人懷疑是 GPT 寫的
人脈
你會認識到電資圈很多怪人:
- 一直拿獎牌的人
- 動不動就把測資或網站 hack 掉的人
- 很不擅長社交的人
- 一輩子都在 Go 的人
- 東方廚
- 擅長通靈的人
…
切記一點就是要動不動就要說別人很電 orz,這是親切的打招呼方式
電神最會做的事情就是裝弱
知識
在競程碰到不會的東西是常有的事情,也因此會大量接觸不同資工/數學領域會用到的知識,有時候常因為好奇而不小心一頭栽入一個領域也是很正常的事
競程專業術語
電神
專門指很強的選手
orz
跪拜姿勢的象形文字,通常用於遇到電神時的打招呼方式,其中
被電爛
遇到電神時會發生的事
virtual
簡寫為 vir,意為模擬賽,指模擬在比賽的狀況下 (相同時間、相同題目集) 寫出題目集。在 codeforce gym 上,有許多近幾年 ICPC 的題目,可以用於練習,亦可與隊友一同練習。當然,其他網站像是 AtCoder 也可以 virtual。如果沒有網站的話,也可以找題目集自己練。virtual 是變強很重要的一個過程,建議所有競程玩家都可以練習,並且不要在賽前或賽中看答案題解
補題
在任何比賽 (包含 virtual) 都會有不會或是寫不對的題目,在賽後檢討並寫出來正確 AC code 的行為稱作「補題」。補題是進步很重要的必經之路,一定要補題才能知道自己的盲點,並且學會新知識與技巧。如果確定題目真的自己不會,可以再補題時看其他人寫的題解或是 code 竊取別人的智慧變成自己的智慧
註: 若一場比賽所有題目都寫得出來而不須補題,代表此比賽不適合你,應該挑戰更難的才會進步
暴搜
指窮舉所有可能
範測
範例測資的簡稱,指題目會給的測資,通常由輸入 (input) 與輸出 (output) 組成
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
如上圖,範測就是
Input
Output
隱藏測資
題目不給你看,且在系統判斷你的程式時會嘗試的測試資料,常由輸入 (input) 與輸出 (output) 組成。基本上再提交程式之後,題目沒過的話都是在隱藏測資的輸出有問題
參考資料
ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/7