[toc]

這篇書本筆記把我所知道的所有技巧都寫上去了。

<!--

## 簡單介紹

### 什麼是程式競賽

通常是寫一些演算法題目，使用程式撰寫。
簡稱競程
這篇專指演算法競賽。
大多使用C++，不需要什麼太高深的語法。

### 需要學習什麼?
- 程式能力: C++
- I/O
- STL Container
- 高速寫程式碼，同時要兼顧一點可維護性。
- 資料結構
- 必須了解
- 演算法/技巧 (底下放一些有學過，但是不代表我會 的東西)
- 基礎: 一些資料結構得會的，尤其是樹。
- Greedy: Activity Selection、Interval Cover、Optimal Matching、Huffman Coding、scheduling...
- DP:
- 背包: 01背包、完全背包、分組背包、各種背包
- subsets(bitmask)、LCS/LIS...
- 圖: D/BFS、MST(也算是greedy)、Shortest-Path(Dijkstra/Bellman/Floyd/SPFA...)、Topo/DAG、強連通分量(Tarjan)、Min Cut/Max Flow、LCA...
- 可能是技巧?: Disjoint Set、雙指標、滑窗、rolling hash、PQ、位元枚舉、分治、cache...

### 競賽制度

有分成OI制/ICPC制
- OI制
- 題目有部份分
- 沒有提交錯誤罰時
- ICPC制
- 可以攜帶文件參賽 (CPE不行)
- 題目只有完全正確或錯
- 每題提交錯誤一次，罰時20

底下專講ICPC制

不同題數: 題數高的排名越前
同題數的: 加總所有有解出的題的 "解題成功距離比賽開始的時間 + 罰時"，該值越低，排名越前
(如果提交，但是沒有解出題，該題會罰時20)

我們找一位同學的比賽紀錄來做範例:
~~這傢伙不行啊，哎呀~~

第1題比賽開始57分鐘後解出
第2題比賽開始20分鐘後解出
第3題比賽開始51分鐘後解出
第4題比賽開始175分鐘後解出，被罰時1次
第5題有提交2次，但都沒有解出來
第6題比賽開始134分鐘後解出
第7題沒有提交

57 + 20 + 51 + (175 + 20) + 134 = 457

分數: 5題，時間: 457

### 競賽題目

一個題目通常有:
- 敘述
- 輸入說明
- 範例輸入（測資）
- 輸出說明
- 範例輸出
- 執行時間限制
- 暗資

寫的程式必須通過暗資才算是解題成功。

### 提交作答的結果

- <font color="#00FF00">AC</font>
Accepted
代表程式正確 -> 解題成功
- <font color="#AA0000">WA</font>
Wrong Answer
代表程式輸出有誤
- <font color="#AA00AA">RE</font>
Runtime Error
太多原因了，通常是陣列、遞迴問題。
- <font color="#000000">CE</font>
Compile Error
代表程式編譯失敗
- <font color="#0000AA">TLE</font>
Time Limit Exceeded
代表程式超過規定執行時間
可能是迴圈永不中止、算法所花時間過長
- <font color="#FFFF00">MLE</font>
Memory Limit Exceeded
代表程式使用過多記憶體

### OJ

onlinejudge系統，可以找到題目寫的地方。
也有一些開源/能自架的OJ：
如 青島大學Judge、DOMJudge（ICPC賽使用）

- ZeroJudge
台灣高中/大學常用
中文化
題目新手友善
題目很多來自其他OJ/台灣競賽。

- Online Judge
30年歷史，經典
題目量龐大，難
知名

- LeetCode
面試刷題平台？
不只有算法題

高中時期打過的，記得裡面題目都蠻多的：
- TIOJ
建中資訊
- ~~Green Judge~~
~~中女中電研~~
- ~~CGOJ~~
~~成功電研~~

總之，可以從ZeroJudge起手。

### 台灣競賽資訊
- APCS (檢定)
大學程式設計先修檢測
分為觀念/實作

- CPE (檢定)
大學程式能力檢定
共7題，題源來自Online Judge
不少大學的資工系設此為畢業門檻

- YTP
少年圖靈計畫
三人一組

- ICPC
國際大學生程式設計競賽
三人一組
有分 regional / world final
一個大學能有多組參加 regional， regional #1 能參加 world final。
在台灣，regional參加資格:
1. NCPC 全國大專院校程式設計競賽 取前40
2. TOPC (ICPC Asia Taiwan Online Programming Contest) 取前40
3. PUPC 私立大學程式設計競賽 取前10
4. NCTU 科技大專校院程式設計競賽 取前10
5. CPE 取前10隊(3人)

來講講regional:
目前台灣最高規格的比賽就是ICPC台灣區賽了，我有幸在去年拿到資格進去打幾場 : )
我們連honorable mention都沒拿到
然後報名費5000，啊，哭了

## 比賽技巧

### 查榜大法

有些比賽題目並不會依照難易度排序，可以偶爾去看榜上哪題解出的人(隊伍)較多，那題可能就比較簡單。
對於ICPC賽特別好用。
CPE也行吧

### 題目

#### 通用

看題目的測資，請看看輸入格式，
是給一個數字n，然後輸入n個東西
還是說直接輸入到EOF之類的

#### CPE前三題

前三題完全在送分，基本上不需要什麼演算法技巧。

不會有什麼算法太差問題，遇到小算法題一律暴力解即可。
可以先看Sample Input/Output，可以快速抓到題意。
看不懂題目的請搞好你的英文。前三題看不懂通常不是程式問題。如果是的話，代表你最基礎的程式能力不行。

策略:
第一題: 5~10分鐘秒殺
第二題: 10~15分鐘
第三題: 20~30分鐘

建議拿下前三題再往下走。

-->