2020 競技程設教材 HackMD Book

2020 Week 1: 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 姓名標示-相同方式分享 3.0 台灣 授權條款授權，
任何人都可以自由使用及分享我們的文字^[1]

2020 競技程式設計課程各週的教材分別為：

• Week 1: Introduction (Convention, Competitive programming)
• Week 2: I/O & Standard Template Library (Complexity, C++)
• Week 3: Thought method
• Week 4: Search (Power set, Binary search)
• Week 5: Sorting (
  $O(N^2)$,
  $O(N{\log }_{2}N)$,
  $O(N)$, Topological sort)
• Week 5: Graph Structures
• Week 7: Dynamic Programming
• Week 9: Data Structures (Sparse table, Segment tree, BIT)
• Week 11: Graph (MST, SSSP APSP)
• Week 12: Graph (AP, SCC, LCA)
• Week 14: Number theory (GCD, Modular arithmetic)
• Week 15: Number theory & Calculation (Multiplication, Prime number)

教材編排及符號慣例

教材中若沒特別說明則將

$N$ 作為初始輸入規模的大小。
教材中若無特別聲明，則所有圖像或程式碼都屬於 Public Domain

句子/名詞加上粗體代表它很重要
句子/名詞加上斜體則代表這邊稍微思考一下

在每節主題後將給予一些範例以及練習，
所謂"範例"就是給道題目，並且會附上該解法；"練習"則是讀者自己該去解的題目。

什麼是演算法

演算法是解決問題的一個具體步驟，通常分成^[2]:

• 初始化
• 循環保持
• 終止

舉例來說，

你的目標是吃完一包大薯，每次可以吃一根薯條
要算出一包大薯有幾根薯條

本教材會使用這個藍色方框，作為一道問題的表示

能將這個演算法分為：

• 初始化： {
  　檢查有沒有一包大薯，沒有就去買;
  　吃了幾根薯條 設為
  $0$;
  }
• 循環保持： {
  　每次從那一包大薯裡面拿一根薯條;
  　吃掉那一根薯條;
  　吃了幾根薯條 加上
  $1$;
  　檢查終止條件，達成則跳出，否則繼續執行循環保持;
  }
• 終止： {
  　大薯吃完了;
  }

這三個步驟相當重要，
在分析別人的演算法又或是自己設計，最好都要想想有沒有符合。

同一件事可能有許多解決方案，這時候我們透過各種方式評估哪種演算法較適當，以提高效率。
切記，各演算法沒有絕對的優劣，根據不同的場合給予適當的實作才是根本之道

什麼是演算法競賽

演算法競賽是種透過寫出演算法來比較的比賽。
競賽通常會有數個題目，參賽者需要寫出或設計適當的演算法和資料結構以在規範的時間、空間解決問題。

因此，參賽者需要對各種資料結構和演算法有深入瞭解才能建構出合理的解題思路，也是算法競賽具體在比較的地方。

比賽分為實體賽與線上賽，提交程式碼並給予評判的系統稱為 Online Judge (簡稱 OJ)

當然平時練習也用 OJ

將寫出來的解交到 OJ 上，就會得到某幾種可能的結果(只會顯示一種)：

• AC (accepted)： 提交的程式產生的解答符合系統所給的所有測試資料
• WA (wrong answer)： 產生的解答不符合系統給的測試資料
• CE (compilation error)： 程式碼編譯錯誤，最好比對一下編譯器是哪家版本
• RE (runtime error)： 通常是陣列超出範圍、指標指向不該指的位置、除以 0、遞迴過深等等
• TLE (time limitation exceeded）： 程式運行的時間超過系統所限制的時間
• MLE (memory limitation exceeded)： 程式記憶體使用量超過系統所限制的空間

一個有趣的狀況是，有時候即使是 AC，也不見得你寫的解是正確的解答，是對方給的測試資料不夠嚴格。

範例 GCJ Kickstart Round E 2018 A Yogurt：

優格可以是開胃菜，主菜或甜點的營養成分，但必須在它過期前食用，它可能會很快過期！此外，不同的優格可能在不同的日子到期。
露西喜歡優格，她剛買了

$N$ 杯優格，但她擔心她可能無法在過期之前食用所有優格。第

$i$ 杯優格將從今天開始起過

$A_i$ 天過期，並且一個優格在過期當天或之後都不能食用。
儘管露西喜歡優格，但她每天只能吃至多

$K$ 杯優格。從今天開始她可以吃掉的優格數量最多是多少？

輸入的第一行給出了測試資料的數量

$T$。每個測試資料以包含兩個整數

$N$ 和

$K$ 的一行開始，接著

$N$ 個整數

$A_i$

對於每筆測試資料，輸出一行包含 Case #x：y，其中x是測試資料編號（從 1 開始），y 是露西可以消耗的最大優格杯數，如上所述。

限制：

$1\le T\le 100$.

$1\le K\le N$.

$\mathrm{\forall }i.1\le A_i\le {10}^9$.

小資料：

$1\le N\le 1000$.

$K=1$.

大資料：

$1\le N\le 5000$.

Input

4
2 1
1 1
5 1
3 2 3 2 3
2 2
1 1
6 2
1 1 1 7 7 7
  	
Output

Case #1: 1
Case #2: 3
Case #3: 2
Case #4: 5

讀完題目後，咱們開始分析吧!
看看這些條件和環境，
先把題目會用上的變數寫上：

int const maxn = 5e3 + 10;
int N, K, A[maxn];

解法就寫在 main() 中吧
並且先輸入

$T$, 每次要餵

$T$ 次測試資料：

int main()
{
  int T;
  scanf("%d", &T);
  
  while (T--) {
      :
      .
  }
  
  return 0;
}

(其中以後我們約定 : 接著下行 ., 表示這個區塊將有一些指令被省略)

而接著可能得用上一點生活經驗，
我們會想到：是不是應該優先吃保存期限低的優格？而且當然一定要一天吃上

$K$ 個優格
既然有靈感了，那就該嘗試一下這樣的決策是否能讓露西吃到最多的優格

總之先輸入測試資料

scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) scanf("%d", &A[i]);

接著我們得先將所有優格按保存期限排序 (要優先吃期限最小的)

sort(A, A+N);

如果這個優格不能吃了，理論上

$A_c-\text{day}$ 要小於等於

$0$
(其中

$\text{day}$ 表示從起點那天，總共過了多少天;

$A_c$ 為某個優格的期限)

而露西吃了

$K$ 個優格就該讓一天結束，那麼我們有 if(eat == K) day++;
(其中 eat 紀錄目前該天共吃了幾個優格)

綜合起來，當今天是第

$\text{day}$ 天時，優格期限從小到大

$A_{i+0}<A_{i+1}<A_{i+2}<...<A_N$
如果

$A_{i+0}-\text{day}\le 0$ 就得看是否

$A_{i+1}-\text{day}\le 0$ 依此類推… 直到否，就能將此優格吃掉！

所以有：

int day = 0, eat = 0;
int cnt = 0; // cnt := 紀錄最後吃了多少

for (int i = 0; i < N; i++) {
  if (A[i] - day <= 0) continue;
  else {
    eat++;
    cnt++;
  }
  
  if (eat == K) {
      day++;
      eat = 0;
  }
}

我們建議，在思考解法或是理解別人的解法的時候，應該也要從結尾往回開始去看。
也就是：

• 當露西當天吃完了
  $K$ 個，就讓今天過完？
• 將優格按照保存期限排序？

上述兩段的動機是什麼？

以下是完整解題程式碼：

#include<bits/stdc++.h>
using namespace std;

int const maxn = 5e3 + 10;

int N, K, A[maxn];

int main()
{
  int T, kase = 0;
  scanf("%d", &T);

  while (T--) {
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);

    sort(A, A+N);

    int day = 0, eat = 0;
    for (int i = 0; i < N; i++) {
      if (A[i] - day <= 0) continue;
      if (++eat % K == 0) day++;
    }

    printf("Case #%d: %d\n", ++kase, eat);
  }

  return 0;
}

bits/stdc++.h： 此標頭檔包含很多常用的標頭檔，使用 GNU GCC 的環境都有，比賽前最好先確認環境

範例 POJ 1852 Ants：

有

$n$ 隻螞蟻以每秒

$1$ cm 的速度在一根

$L$ cm 的竿子上爬，當螞蟻爬到竿子的尾端時它會掉下去，當兩隻螞蟻相遇時，他們不能交錯通過，只能各自反向爬回去。
對於每隻螞蟻我們有它與竿子左端的距離

$x_i$，但是不知道它們的朝向，要求所有螞蟻掉落的最短時間與最長時間。

input:
題目一開始給你一個數字

$T$^[3]，代表總共有幾筆測試資料。
接著每筆測資有兩行，第一行有兩個數字：這根竿子的長度

$L$，還有共有幾隻螞蟻

$n$；
接著第二行給你

$n$ 隻螞蟻與竿子左端的距離

$x_i$。
其中

$0\le n,x_i\le L\le {10}^6$

output:
對於每筆測資獨立一行，輸出兩個數字(以空白分隔)：最短掉落時間與最長掉落時間。

sample input:

2
10 3
2 6 7
214 7
11 12 7 13 176 23 191

sample output:

4 8
38 207

各位可以稍微想一下這題要怎麼解？
底下將簡單分析一下，並給出解答：

樸素的會想到一個暴力的模擬，也就是每一隻螞蟻的狀態都要考慮(朝左，朝右)，每個螞蟻可選

$2$ 種狀態，總共

$2^n$ 種選法。
但這樣實在是太沒效率了，稍微手算模擬一下就能感受得出來。

有沒有更好的方法？
如果仔細琢磨題目給的限制及目標，會發現螞蟻哪隻是哪隻並不重要，
意思是可以把螞蟻的碰撞背離視為交錯而行(題目騙我QAQ)
這樣，只需看哪隻螞蟻最慢最快掉落。

#include<bits/stdc++.h>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  
  while (T--) {
    int L, n;
    scanf("%d%d", &L, &n);
               
    int x, mint = 0, maxt = 0; // 最小時間和最大時間
    for (int i = 0; i < n; i++) {
      scanf("%d", &x);
      mint = max(mint, min(L-x, x));
      maxt = max(maxt, max(L-x, x));
    }
               
    printf("%d %d\n", mint, maxt);
  }
            
  return 0;
}

時間複雜度是線性的

$O(n)$^[4]。

---

1. 聯絡主編可以寄信到 yuessiahgmail.com ↩︎

2. 這是根據演算法名書 Introduction to Algorithms 的看法 ↩︎

3. 但根據原題，它說所有輸入都不超過

   ${10}^6$，
   $T$ 的話實在不太可能，此題還是有小瑕疵的。 ↩︎

4. week2 將會解釋此表示法的具體意義，不懂的同學現在先看個感覺就行 ↩︎