Try   HackMD

認識競技程式

什麼是競程?

競程就是競技程式的縮寫,英文則是 competitive programming,簡稱 CP。算是資訊領域的分支,亦是有趣的學生活動之一。這領域近年來越來越熱門,對於升大學、考研究所、找工作都很有幫助,然而大多數人在資料結構與演算法相關課程看到一些基本的題目,就被嚇到而不敢跳進這個領域

參與競程你會需要

  • 程式能力: C/C++ (八成)、Python (or Java)
  • 熟悉演算法: 二分搜尋、greedy、暴搜、dp、分治法、
  • 熟悉資料結構: 線段樹、樹狀陣列(數組)、雜湊表、字串(還有他的演算法)、
  • 數學能力: 數論(取mod)、排列組合、位元運算、高中幾何、線性代數(向量)、圖論
  • 英文閱讀能力: 大學才要用到,因為題目都是英文

以上天花亂墜一堆東西,但實際上最需要的只有兩個東西: 思維能力程式實作能力

競賽內容

簡介

競程不像寫網站、遊戲等比較大的專案需要注意美觀、使用者需求等,只有程式的輸出輸入正確與否而已。競程比賽會有很多題目,每一題不外乎就是要寫出符合題述的程式

一個競程題目會有:

  • 題述
  • 限制
  • 輸入說明
  • 輸出說明

其中限制這點非常重要、這會影響到我們需要用到什麼演算法或資料結構

舉例

題目 CSES Missing Number

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 →


程式實作

#include <iostream>
using namespace std;
 
int main() {
 
    long long n, ans, tmp;
    cin >> n;
    ans = n * (n + 1) / 2;
    for(int i = 0; i < n - 1; i++){
        cin >> tmp;
        ans -= tmp;
    }
    cout << ans << '\n';
 
    return 0;
}

輸入

10
2 8 10 6 5 1 3 7 4

輸出

9

送出結果

在寫出程式並送出之後,網站或系統會在他的主機端塞給你的程式一些測資,少則數個,多則一百個。最後都會反饋出以下結果:

  • 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,難度親民

私人企業競賽

  • HP codewars: 零食很多,免費參賽,寫題目就可以抽獎 作者(ShanC)抽過筆電喔
  • Meta Hacker Cup: 這我不熟,但是聽說比賽都是在深夜

線上題庫

中文題庫

  • Zerojudge 高中生程式解題系統: 水題很多,怪題也不少,但是匯集了許多不同題庫的題目,也有很多競賽、檢定題目,像是 APCS 題就很齊全,上面也有相當多題解可以參考,新手友善的一個題庫
  • TIOJ: 建中題庫,對新手非常不友善
  • Green Judge: 好像在我高二的時候就一直開不起來,似乎是死掉了
  • 洛谷: 對岸的題庫,題目非常齊全,想找到任何觀念的裸題都可以找的到

英文題庫

  • CSES: 每一題都是精華中的精華,如果想要磨練基本競程題型一定要刷最少一百多題,要精熟差不多需要 250 題
  • Codeforces: 有很多不同國家地方的題目
  • Leetcode: 企業愛看的題庫,許多 code interview 都會參考裡面的題型

參與競程你會獲得

程式與思維能力提升

經過長期的磨練,會發現程式與思維能力有所提升
這是顯而易見的

課業

大學資工的必修課都會瞬間變得超簡單,也比較容易給同學、教授留下好印象
高中的話我不知道

升學

在資訊領域到底有誰不愛會寫程式的人啦
大學、研究所都是搶著要的
我有個打競程的學長,在公司面試時寫 code 快到被人懷疑是 GPT 寫的

人脈

你會認識到電資圈很多怪人:

  • 一直拿獎牌的人
  • 動不動就把測資或網站 hack 掉的人
  • 很不擅長社交的人
  • 一輩子都在 Go 的人
  • 東方廚
  • 擅長通靈的人

切記一點就是要動不動就要說別人很電 orz,這是親切的打招呼方式
電神最會做的事情就是裝弱

知識

在競程碰到不會的東西是常有的事情,也因此會大量接觸不同資工/數學領域會用到的知識,有時候常因為好奇而不小心一頭栽入一個領域也是很正常的事

競程專業術語

電神

專門指很強的選手

orz

跪拜姿勢的象形文字,通常用於遇到電神時的打招呼方式,其中

  • o 代表頭
  • r 代表手臂
  • z 代表腿部

被電爛

遇到電神時會發生的事

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

5
2 3 1 5

Output

4

隱藏測資

題目不給你看,且在系統判斷你的程式時會嘗試的測試資料,常由輸入 (input) 與輸出 (output) 組成。基本上再提交程式之後,題目沒過的話都是在隱藏測資的輸出有問題

參考資料


ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/7