---
tags: 成大高階競技程式設計 2021
---
# 2021 Week1 - Introduction
> Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
> --- Donald Knuth
本教材由成大競技程式設計課程助教撰寫，採 [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh_TW) 授權條款。
# 競技程式設計 (Competitive programming)
競技程式設計，簡稱競程，是一個透過寫 code 來解題的比賽，
考驗你的邏輯、數學與資料結構演算法，當然還有程式能力。
大型實體比賽有「全國大專電腦軟體設計競賽[^NCPC]」（NCPC），
「國際大學生程式設計競賽[^ICPC]」（ICPC, International Collegiate Programming Contest）；
線上比賽有一年一度的 [Google Code Jam](https://codingcompetitions.withgoogle.com/codejam) (GCJ)，比賽眾多的平台 [Codeforces](https://codeforces.com/) 等等。
<hr class="dashed">
# C++ :comet:
程式執行時間是 <font color="#2ecc71">AC</font>[^verdict] 的一大關鍵，注重效能的 C++ 因此成為一大主流，
而 C++ 在設計的靈活性上也有非常好的表現，本課程也將以 C++ 為主。
> 不會 C++ 的同學也沒關係，課程以教導概念為主，程式語言只是工具，
> 並且課堂與大部分外面的比賽，也都支援使用其他語言解題[^language]。
講到 C++ 許多人可能會想到 OOP[^OOP]，但 C++ 其實是 multi-paradigm programming language，
這邊就講 C++ 在競程中比較重要的部分：
* Procedural Programming
* 每個問題只有一份程式檔案（e.g., \*.cpp, \*.py）
* 這份程式碼整體風格還是以跟 C 一樣的 procedural programming 為主
* Generic Programming
* STL（Standard Template Library）[^STL]
* 讓同一份程式碼可以搭配不同型態來使用
* 通常只會在 codebook 中用到
* Object-oriented Programming
* STL Containers（e.g., std::vector, std::queue, std::map, ...）
* 對資料結構進行簡單的封裝（e.g., DSU, Segment tree）[^DSU_and_SegTree]
<hr class="dashed">
# CODEBOOK :bookmark_tabs:
不論線上或是實體比賽，大多都允許使用預先寫好的程式碼，
這也是為什麼我們會準備自己的 codebook，除了節省時間外，
更重要的是能夠**確保正確性**；兩者綜合起來，可說是一大利器。
而本課程的課堂比賽也都開放使用 codebook。
> 有些人喜歡自己實作，有人則會收集網路上的程式碼，
> 其實都可以，對於競程來說，重要的還是了解並使用過。
<hr class="dashed">
# 題目形式 :mag:
競程的題目主要包含以下幾個區塊：
* 題目敘述
* 時間限制 / 記憶體限制
* 以通過時間限制為目標
* 時間複雜度夠低即可，正常情況下常數大小不影響結果[^TimeComplexity]
* 記憶體限制通常很大，少數時候會卡某些儲存方式（e.g., $n \times n$ 的表格）
* 變數意義與範圍
* 輸入輸出格式
* 不用考慮不符合規範的輸入
* 多餘輸出都可能導致 <font color="#e74c3c">WA</font>（包含換行、空白與 Tab 等不可見字元）
* 範例測資
* 一筆至多筆
* 可能包含對應的答案解釋
<hr class="thin">
下面舉個實際的例子：
### 題目敘述
給定一個數列，請找出該數列的最大值。
### 輸入說明
第一行輸入一個正整數 $N\ (N\leq2\times10^5)$，代表數列的長度，
接下來一行輸入 $N$ 個非負整數 $A_1,A_2,\cdots,A_n\ (0\leq A_i\leq10^9)$，$A_i$ 代表數列中第 $i$ 個元素。
### 輸出說明
請輸出一個整數，代表該數列的最大值。
### 範例輸入
```
5
2 4 3 5 1
```
### 範例輸出
```
5
```
### 時間限制 & 記憶體限制
- Time limit: 1 second
- Memory limit: 512 MiB
<hr class="thin">
一份 <font color="#2ecc71">AC</font> 的程式碼會類似這樣，
依照題目所給的輸入，經過計算並按照規範格式輸出，
且能夠通過時間與記憶體限制。
:::spoiler 正確程式碼
```cpp!
#include <iostream>
using namespace std;
int main() {
int n, x, mx = 0;
cin >> n;
for(int i = 0; i < n; i++){
cin >> x;
if(x > mx) mx = x;
}
cout << mx << "\n";
}
```
:::
<hr class="dashed">
# 評測系統 :balloon:
在解題完成後，主辦方需要驗證程式碼的正確性，驗證的地方即為評測系統。
現在的比賽幾乎都是採用線上評測系統（簡稱 OJ[^OJ]），
寫完程式後將原始碼送到 OJ，OJ 會透過若干組測試資料來驗證，
並在短時間內就可以得知該筆評測的結果，這是與其他學科考試或是作業不同的地方。
當你的程式的輸出與 OJ 上的正確答案一致時，就會被判定為正確；
因為編譯、輸入、輸出、判定都是自動化進行，所以如前面所述，
程式不應輸出多餘的東西，只要有任何多餘的空格或是換行，
OJ 就可能會認定為錯誤，還請各位多留意。
在大部分的比賽中都可以再次提交，不用擔心錯一次就沒機會了，
不過比賽規則（如：ICPC）通常會有錯誤罰（penalty），
當提交的程式碼得到 <font color="#2ecc71">AC</font> 以外的結果時，
會在解題時間計算上增加一定的分鐘數，分鐘數依比賽而定（ICPC 為 $20$ 分鐘）；
舉例來說，當某一題在比賽開始後第 $68$ 分鐘送了第 $5$ 次才 <font color="#2ecc71">AC</font>，
則該題 penalty 為 $68+20\times4=148$，
而整場比賽的 penalty 就是<font class="focus">每題</font> <font color="#2ecc71">AC</font> <font class="focus">的題目</font>之 penalty 加總；
在計算排名時若遇到解題數相同的，則 penalty 較少的名次較前面。
<hr class="dotted">
## 評測結果 :100:
將程式碼送出後，就會得到評測結果，有些 OJ 會用簡寫來表示，
以下為常見的評測結果，各 OJ 可能會有些許差異，在此特別附上 ICPC 的評測結果供對應。
| 簡寫 | 全稱及常見寫法 | ICPC Verdict | 說明 |
|:-:|:-:|:-:|-|
| <font color="#2ecc71">AC</font> | Accepted | <font class="sol-ac">correct</font> | 程式執行正確 |
| <font color="#e74c3c">WA</font> | Wrong Answer | <font class="sol-err">wrong-answer</font> | 答案錯誤 |
| <font color="#3498db">TLE</font> | Time Limit Exceeded | <font class="sol-err">timelimit</font> | 執行超時，可能是演算法不夠快速或程式陷入無窮迴圈 |
| <font color="#f1c40f">RE</font> | Runtime Error | <font class="sol-err">run-error</font> | 執行時期錯誤，可能是除以 $0$ 或是程式沒有正常結束 |
| <font color="#f1c40f">MLE</font><br>or<br><font color="#f1c40f">RE</font> | Memory Limit Exceeded[^MLE] | <font class="sol-err">run-error</font> | 記憶體區段錯誤，你的程式使用太多記憶體，或者存取空指標或超出陣列範圍外的位置，也可能是遞迴過深導致 |
| CE | Compilation Error | <font class="sol-err">compiler-error</font> | 編譯錯誤，可能是寫錯或本地編譯環境與 OJ 不同 |
[^NCPC]: 不要懷疑，它就是競程的比賽；筆者也覺得名稱很怪。
NCPC 競賽規則與系統上與 ICPC 相近
[^ICPC]: 台灣的區域賽通常為「台北站」或「台北-新竹站」
[^verdict]: 詳見[評測結果](#評測結果-)
[^language]: 本課程評測環境支援 C, C++, Python；[全國大專電腦軟體設計競賽](https://ncpc.nsysu.edu.tw/)（NCPC）則支援 C, C++, JAVA, Python
[^OOP]: OOP：[物件導向程式設計](https://zh.wikipedia.org/zh-tw/%E9%9D%A2%E5%90%91%E5%AF%B9%E8%B1%A1%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1)（Object-oriented Programming），constructor 與 member function 等均為 OOP 的特徵
[^STL]: STL： C++ 內建的[標準模板庫](https://zh.wikipedia.org/wiki/%E6%A0%87%E5%87%86%E6%A8%A1%E6%9D%BF%E5%BA%93)
[^DSU_and_SegTree]: 資料結構：上面提到的 [DSU](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) 與 [Segment tree](https://en.wikipedia.org/wiki/Segment_tree) 都是競程中常見的資料結構，也將出現在這學期的課程中
[^TimeComplexity]: 未來課程會詳細解釋時間複雜度與程式的常數
[^OJ]: OJ：線上評測系統（Online Judge）
[^MLE]: 本課程 OJ 會顯示 Segmentation Fault
<style>
hr.thin {
height: 0.5px;
}
hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}
hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}
/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}
/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}
.sol-ac {
color: green;
font-weight: bold;
font-variant: small-caps;
}
.sol-err {
color: red;
font-weight: bold;
font-variant: small-caps;
}
.focus {
color: red;
font-weight: bold;
}
</style>
Sign in with Wallet
Connect another wallet