認識競技程式

# 認識競技程式 ## 什麼是競程? 競程就是競技程式的縮寫，英文則是 competitive programming，簡稱 CP。算是資訊領域的分支，亦是有趣的學生活動之一。這領域近年來越來越熱門，對於升大學、考研究所、找工作都很有幫助，然而大多數人在資料結構與演算法相關課程看到一些基本的題目，就被嚇到而不敢跳進這個領域 ## 參與競程你會需要... - 程式能力: C/C++ (八成)、Python (or Java) - 熟悉演算法: 二分搜尋、greedy、暴搜、dp、分治法、... - 熟悉資料結構: 線段樹、樹狀陣列(數組)、雜湊表、字串(還有他的演算法)、... - 數學能力: 數論(取mod)、排列組合、位元運算、高中幾何、線性代數(向量)、圖論 - 英文閱讀能力: 大學才要用到，因為題目都是英文以上天花亂墜一堆東西，但實際上最需要的只有兩個東西: **思維能力**、**程式實作能力** ## 競賽內容 ### 簡介競程不像寫網站、遊戲等比較大的專案需要注意美觀、使用者需求等，只有程式的輸出輸入正確與否而已。競程比賽會有很多題目，每一題不外乎就是要寫出符合題述的程式一個競程題目會有: - 題述 - 限制 - 輸入說明 - 輸出說明其中限制這點非常重要、這會影響到我們需要用到什麼演算法或資料結構 ### 舉例 #### 題目 [CSES Missing Number](https://cses.fi/problemset/task/1083) <img src="https://hackmd.io/_uploads/BJjCf-Z-1e.png" style="margin: 0 auto; display: block; width: 450px"> #### 程式實作 ```cpp #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; } ``` #### 輸入 ```tex 10 2 8 10 6 5 1 3 7 4 ``` #### 輸出 ```tex 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](https://tpmso.org/toi/): 臺灣資訊奧林匹亞，挑選手進 IOI，可藉由 APCS 或是縣市資訊學科能力競賽推薦 - [IOI](https://ioinformatics.org/): 國際資訊奧林匹亞，臺灣每次最多只有四個名額 #### ICPC 賽制大學的競賽都是 ICPC 賽制，團體賽(三人)，所有測資都需要答對才有分數 - NCTU: 僅限科技大學 - NCPU: 僅限私立大學 - TOPC: ICPC 臺灣地區賽的前導賽 - NCPC: 僅限國立大學，分初賽與決賽 - Taiwan ICPC Regional: 可藉由上述四種比賽推薦取得比賽資格，基本上能進去比賽就已經很厲害了 - ICPC World Final: 競程最高殿堂，取 Regional 的前兩名推薦 ### 檢定 - [APCS 大學程式能力先修檢測](https://apcs.csie.ntnu.edu.tw/): 高中生的檢定，對升大學很有幫助 - [CPE 大學程式能力檢定](https://cpe.cse.nsysu.edu.tw/): 大學的檢定，高中電神也可以參加 ### 線上競賽 - [Codeforces](https://codeforces.com/): 每周都會有競賽，難度分為Div 4、3、2、1，其中 Div 1 最難 - [AtCoder](https://atcoder.jp/): 這是日本的網站，每週都有 AtCoder Beginner Contest，難度親民 ### 私人企業競賽 - [HP codewars](https://www.facebook.com/codewars.taiwan/?locale=zh_TW): 零食很多，免費參賽，寫題目就可以抽獎 ||~~作者(ShanC)抽過筆電喔~~|| - [Meta Hacker Cup](https://www.facebook.com/codingcompetitions/hacker-cup/2024): 這我不熟，但是聽說比賽都是在深夜 ## 線上題庫 ### 中文題庫 - [Zerojudge](https://zerojudge.tw/) 高中生程式解題系統: 水題很多，怪題也不少，但是匯集了許多不同題庫的題目，也有很多競賽、檢定題目，像是 APCS 題就很齊全，上面也有相當多題解可以參考，新手友善的一個題庫 - [TIOJ](https://tioj.ck.tp.edu.tw/problems): 建中題庫，對新手非常不友善 - Green Judge: 好像在我高二的時候就一直開不起來，似乎是死掉了 - [洛谷](https://www.luogu.com.cn/): 對岸的題庫，題目非常齊全，想找到任何觀念的裸題都可以找的到 ### 英文題庫 - [CSES](https://cses.fi/problemset/): 每一題都是精華中的精華，如果想要磨練基本競程題型一定要刷最少一百多題，要精熟差不多需要 250 題 - [Codeforces](https://codeforces.com): 有很多不同國家地方的題目 - [Leetcode](https://leetcode.com/): 企業愛看的題庫，許多 code interview 都會參考裡面的題型 ## 參與競程你會獲得... ### 程式與思維能力提升經過長期的磨練，會發現程式與思維能力有所提升這是顯而易見的 ### 課業大學資工的必修課都會瞬間變得超簡單，也比較容易給同學、教授留下好印象高中的話我不知道 ### 升學在資訊領域到底有誰不愛會寫程式的人啦大學、研究所都是搶著要的 ||我有個打競程的學長，在公司面試時寫 code 快到被人懷疑是 GPT 寫的|| ### 人脈你會認識到電資圈很多怪人: - 一直拿獎牌的人 - 動不動就把測資或網站 hack 掉的人 - 很不擅長社交的人 - 一輩子都在 Go 的人 - 東方廚 - ||淫夢||廚 - 音遊大佬 - 擅長通靈的人 ... 切記一點就是 **「必須要動不動就要說別人很電 orz，這是親切的打招呼方式」** 電神最會做的事情就是裝弱 ### 知識在競程碰到不會的東西是常有的事情，也因此會大量接觸不同資工/數學領域會用到的知識，有時候常因為好奇而不小心一頭栽入一個領域也是很正常的事 ## 競程專業術語 ### 電神專門指很強的選手 ### orz 跪拜姿勢的象形文字，通常用於遇到電神時的打招呼方式，其中 - o 代表頭 - r 代表手臂 - z 代表腿部 ### 被電爛遇到電神時會發生的事 ### virtual 簡寫為 vir，意為模擬賽，指模擬在比賽的狀況下 (相同時間、相同題目集) 寫出題目集。在 [codeforce gym](https://codeforces.com/gyms) 上，有許多近幾年 ICPC 的題目，可以用於練習，亦可與隊友一同練習。當然，其他網站像是 [AtCoder](https://atcoder.jp/) 也可以 virtual。如果沒有網站的話，也可以找題目集自己練。virtual 是變強很重要的一個過程，建議所有競程玩家都可以練習，並且不要在賽前或賽中看答案題解 ### 補題在任何比賽 (包含 virtual) 都會有不會或是寫不對的題目，在賽後檢討並寫出來正確 **AC** code 的行為稱作「補題」。補題是進步很重要的必經之路，一定要補題才能知道自己的盲點，並且學會新知識與技巧。如果確定題目真的自己不會，可以再補題時看其他人寫的題解或是 code ||~~竊取別人的智慧變成自己的智慧~~|| 註: 若一場比賽所有題目都寫得出來而不須補題，代表此比賽不適合你，應該挑戰更難的才會進步 ### 暴搜指窮舉所有可能 ### 範測範例測資的簡稱，指題目會給的測資，通常由輸入 (input) 與輸出 (output) 組成 <img src="https://hackmd.io/_uploads/BJjCf-Z-1e.png" style="margin: 0 auto; display: block; width: 450px"> 如上圖，範測就是 **Input** ``` 5 2 3 1 5 ``` **Output** ``` 4 ``` ### 隱藏測資題目不給你看，且在系統判斷你的程式時會嘗試的測試資料，常由輸入 (input) 與輸出 (output) 組成。基本上再提交程式之後，題目沒過的話都是在隱藏測資的輸出有問題 ### 裸題直接套用教學時使用的模板即可 **AC** 的簡單題 ### 破台解出一場競賽的所有題目 ### 防破台題防止你解破台的題目，超級難 ## 備註 ### 別人貶低競程仔怎麼辦他比較沒智慧，我們同情他，我們不理他 ### 正確的練習態度 - 刷題 $\rightarrow$ 複盤 $\rightarrow$ 刷題 $\rightarrow$ 複盤 $\rightarrow \cdots$ - 如果遇到有興趣的主題，一定要找書跟資料來看 - 多跟別人討論，增進互動才能創造奇蹟 ### 推薦書籍/資料以下資料都是競程常見的 Topics，如果發現其中幾個 (那怕只有一個)，不要吝嗇去多鑽研，這樣才有機會解出防破台題。有時候破台題都是從以下這些刁鑽的領域出現的，像是 [ICPC2021 H](https://codeforces.com/gym/103443/problem/H) 就可以用隨機+近似算法+DP+一般圖匹配來解題。這些 topics 都是要另外讀書才會的，光靠刷題絕對學不會 #### 競程 - [Laaksonen - Competitive Programmer’s Handbook](https://cses.fi/book/book.pdf) - [geeksforgeeks](https://www.geeksforgeeks.org/dsa/dsa-tutorial-learn-data-structures-and-algorithms/) - [cp-algorithms](https://cp-algorithms.com/) - [AP325 by 吳邦一教授](https://drive.google.com/file/d/1hX7q3wVKkLuoMhEEm7uuLjq4BuhZAEgn/view) #### 演算法 - Graham, Knuth, Patashnik - Concrete Mathematics: A Foundation for Computer Science - CLRS - Introduction to Algorithms - Vazirani - Approximation Algorithms #### 組合數學 - Kenneth Rosen - Discrete Mathematics and Its Applications - Wilf - Generatingfunctionology - D.B.West - Introduction to Graph Theory - 張鎮華、蔡牧村 - 演算法觀點的圖論 - Tucker - Applied Combinatorics - [MIT OCW - Additive combanitorics and graph theory](https://www.youtube.com/watch?v=RDO6Py97IDg) - [NYCU OCW - 組合學導論](https://www.youtube.com/watch?v=qRBT9SEHnRw) ||數論我不熟|| ## 參考資料 - [APCS 大學程式設計能力先修檢測](https://apcs.csie.ntnu.edu.tw/) - [TOI 資訊奧林匹亞競賽](https://tpmso.org/toi/) - [從零開始的競程介紹 by LittlePants](https://hackmd.io/@LittlePants/Hyw_rueGK) - [臺海大競程講義](https://hackmd.io/@LeeShoWhaodian/CPintro#/) - [競程介紹 by tw20000807](https://hackmd.io/@tw20000807/all/https%3A%2F%2Fhackmd.io%2F%40tw20000807%2Fcp) - [What is Competitive Programming? by William Lin](https://www.youtube.com/watch?v=ueNT-w7Oluw) - [AP325 by 吳邦一教授](https://drive.google.com/file/d/1hX7q3wVKkLuoMhEEm7uuLjq4BuhZAEgn/view) - [SA 流 C++ 競程修練心法](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FBkTJ0imPB) - [新竹實驗中學C++程式語言教學講義](https://hackmd.io/@CLKO/B18yT_i5Z) - [競程怎麼入門](https://kelly-lu.gitbook.io/jing-cheng-ru-men-bi-ji) ---- > [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2025/3/7