競賽導論 - HackMD

# 競賽導論 by 資研社教學莊明達 ### 沒錯，資研社的教學方式又升級了:) 每天的投影片都會有連結丟到fb群組 麻麻再也不怕我沒拍到code了! ——(hopefully今後的)社員 --- # C++ vs Python 競賽給不給Python用都是個問題。 今後社課的code也會以C++為主 ---- | Python | C++ | | --------------- | -------------- | | 編寫時間快 | 執行時間快 | | 好寫 | 比較不好寫 | | 變數型別可更動 | 變數型別不可更動 | | 必須換行、縮排 | 使用「;」區隔statement 「{}」區分scope | ---- ```cpp= [|1-2|4-14|5|6-7|8-9|11-14|16-17|19-20|22] #include <iostream> using namespace std; //這是comment int main() { ios_base::sync_with_stdio(false); cin.tie(0); //加速! int x, y=0; //宣告變數要固定型別 string z = "harbinger"; cin >> x >> z; //基礎輸入、輸出 cout << z << ' ' << x; for (int i=0; i<10; i++) { //i++ = i+=1 x += i; y += 998224353 / ((i+1)*i); } scanf("%d%d", &x, &y); //另一種輸入輸出 printf("hello! %d%d", x, y); int array[105]; //陣列有固定大小 cout << arr[7]; return 0; } ``` --- # 如何練習? 就是各種刷題。 把常用的東西練成肌肉記憶 ---- ### 學習資源 [AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) - 號稱APCS 3 to 5 [ntnu~algo](http://web.ntnu.edu.tw/~algo/) - 台灣師範大學的 [Algorithms for Competitive Programming](https://cp-algorithms.com/) 如果看得懂英文 去網路找!!!!! ---- ### 刷題網站 (網路找也能找到更多) | 簡稱 | 簡介 | | ------------------ | ------------------- | |[ZJ](https://zerojudge.tw)|大家最熟的，但品質...| |[TIOJ](https://tioj.ck.tp.edu.tw)|建中的，題目較難| |[CF](https://codeforces.com)|體驗比賽的地方| |[AtCoder](https://Atcoder.jp)|另一個體驗比賽的地方| |[CSES](https://cses.fi)|一堆經典題|  --- # 時間複雜度 隨著輸入增加，所花時間的增長趨勢 不代表實際運算時間的快慢 用於估計程式是否會TLE ---- ## 如何計算? 事情做多次 → 乘起來 不同的變數 → 加起來  取最糟糕的情況(大$O$符號)  ---- ```python= array = [i for i in range(1000)] #array = [0, 1, 2, 3...] test = int(input()) if test in array: #複雜度? ... ``` $O(n)$，所以拜託不要用  找其他的方法檢查  ---- 對於一個陣列內所有的元素$A$，找到陣列內另一個元素$B$，令$A+B$ 為最大，又不超過$K$ 答：對每個元素，都檢查整個陣列找出答案 ---- ```cpp= const int SZ = 2000, K = 19937; int A[SZ], B[SZ]; for (int i=0; i<SZ; ++i) { int best = -998244353; for (int j=0; j<n; ++j) { if (j == i) continue; if (A[i]+B[j] > A[i]+best && A[i]+B[i] <= K) best = B[j]; } //best即A[i]的最佳搭配 } ``` 複雜度 $O(n^2)$  ---- 對於一個陣列內所有的元素$A$，找到陣列內另一個元素$B$，令$A+B$ 為最大，又不超過$K$ 答：先排序，再對陣列二分搜  ---- ```cpp= [|3|5-10] const int SZ = 2000, K = 19937; int A[SZ], B[SZ]; sort(A, A+SZ); sort(B, B+SZ); for (int i=0; i<SZ; ++i) { int left=0, right=SZ; while (left < right) { int mid = (left + right) / 2; if (A[i] + B[mid] > K) right = mid; else left = mid+1; } //B[left] = B[right] = A[i]的最佳搭配 } ``` 複雜度 $O(n \log n)$  ----  輸入一個長度$N$的陣列$V$ 進行$Q$次的查詢，每次輸入兩個數字$p,\ k$ 輸出$V[p],V[p+1],...,V[p+k]$的最大值 答：每次都比較$V[p],V[p+1],...,V[p+k]$  ---- ```cpp= const int SZ = 50000, Q = 200000; int V[SZ]; for (int i=0; i<Q; ++i) { int p, k; cin >> p >> k; int best = -2000000000; for (int j=0; j<k; ++j) best = max(best, V[p+j]); //best即為本次查詢的答案 } ``` 複雜度 $O(N + QK) = O(QK) ≈ O(QN)$  ---- 輸入一個長度$N$的陣列$V$ 進行$Q$次的查詢，每次輸入兩個數字$p,\ k$ 輸出$V[p],V[p+1],...,V[p+k]$的最大值 挑戰：能不能達到 $O(N + Q \log N)$?  [$\rightarrow \text{a041}$ 奇怪的老闆](https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a041)  ---- 常見複雜度對應的演算法 | Time Complexity | Algorithm | | --------------- | ----------------- | | $O(\log n)$ | 二分搜 | | $O(n)$ | 遍歷(所有元素跑一遍) | | $O(n\log n)$ | 排序法、樹狀結構 | | $O(n\sqrt n)$ | 分塊法(如莫隊) | | $O(n^2)$ | 雙重迴圈、DP | | $O(n^3)$ | Floyd-Warshall | | $O(2^n)$ | 枚舉 |  ---- 時間複雜度 vs 輸入大小(一秒時限下) | Time Complexity | Input Limit | | --------------- | ----------- | | ≤ $O(\log n)$ | INF | | $O(n)$ | ≤ $10^9$ | | $O(n\log n)$ | ≤ $10^6$ | | $O(n\sqrt n)$ | ≤ $10^5$ | | $O(n^2)$ | ≤ $10000$ | | $O(n^3)$ | ≤ $400$ | | $O(2^n)$ | ≤ $25$ |  ---- ![](https://raw.githubusercontent.com/pusapphire/R3_Gitbook/master/.gitbook/assets/Time%20Complexity%20Graph.png?token=GHSAT0AAAAAACU65IF7JPEQZG5FPTJ6VCUWZWMIUZQ) ---- ## 主定理 Master Theorem 定義一個遞迴式$T(n)$ 並定義$f(n)$為合併複雜度 $T(n) = aT(n/b) + f(n)$ ```r= 定義一個遞迴函式pseudo-code a≥1, b>1, k; function T(n): if (n < k): solve(); else: 製造a個T(n/b)並以f(n)的複雜度合併 ``` ---- $T(n) = aT(n/b) + f(n)$ 令$c = \log_b{a}$，則有以下關係式(簡化版) \begin{equation} T(n)= \begin{cases} O(n^c) & f(n)=O(n^{p<c})\\ O(n^c\log^{k+1} n) & f(n)=\Theta(n^c\log^kn)\\ O(f(n)) & f(n)=\Omega(n^{p>c})\land\\ & \ \ af(n/b) \leq f(n) \end{cases} \end{equation} $$ O \rightarrow 上界，\Theta \rightarrow 上+下界，\Omega \rightarrow 下界 $$ --- ## 各類排序法複雜度 ---- ### 泡沫 Bubble Sort ```python= [|2-3] A = [rand()] * 10000 for loop in range(len(A)): for i in range(len(A)-1): if A[i] > A[i+1]: A[i], A[i+1] = A[i+1], A[i] ``` 雙層迴圈 $\rightarrow O(n^2)$  ---- ### 插入 Insertion Sort ```python= [|2,4] A = [rand()] * 20000 for i in range(len(A)): j = i while j > 0 and A[j-1] > A[j]: A[j-1], A[j] = A[j], A[j-1] j -=1 ``` 依然是雙層迴圈 $\rightarrow O(n^2)$  ---- ### 選擇 Selection Sort ```python= [|2,4] A = [rand()] * 20000 for i in range(len(A)): cur, idx = 9e18, -1 for j in range(i, len(A)): if A[j] < cur: cur, idx = A[j], j A[i], A[idx] = A[idx], A[i] ``` 依然依然是雙層迴圈 $\rightarrow O(n^2)$  ---- ### 謝爾 Shell Sort ```python= [|2,4,7] A = [rand()] * 50000 gap = 50000 // 2 while gap > 0: for i in range(gap, len(A)): if A[i-gap] > A[i]: A[i], A[i-gap] = A[i-gap], A[i] gap //= 2 ``` $O(n^2) \sim O(n\log n)$  關鍵在於`gap`的計算方式  ---- ### 快速 Quick Sort ```python= A = [rand()] * 200000 def part(l, r): idx, pvt = l, A[r] for j in range(l, r): if A[j] < pvt: A[idx], A[j] = A[j], A[idx] idx += 1 A[idx], A[r] = A[r], A[idx] return idx def qsort(l, r): if l != r: pos = part(l, r) qsort(l, pos-1) qsort(pos+1, r) ``` 最糟$O(n^2)$，平均$O(n\log n)$  ---- ### 分治 Merge Sort ```python= A = [rand()] * 200000 def merge(l, r): mid = (l + r) // 2 merge(l, mid); merge(mid+1, r) i, j, tmp = l, mid+1, [] while i <= mid and j <= r: while i <= mid and A[i] < A[j]: tmp.append(A[i]) i += 1 tmp.append(A[j]) j += 1 if i < mid: tmp += A[i:mid+1] if j < r: tmp += A[j:r+1] A[l:r+1] = tmp ``` $$c=\log_b(a)=\log_2(2)=1;\ \ f(n)=O(n^c)=O(n^1) \\ \text{主定理}\rightarrow O(n\log n) $$  --- # 常數 影響比複雜度小，但仍然存在 Python在這方面就有很大的弱勢 梗：鴨腸→壓常→降低常數 ---- ## 一般來說： 1. 除法、取模(%)比乘慢，乘比加減慢 2. 小數比整數慢，需要記憶體小的比較快 3. 對`const`取模比較快 ---- ### a10 聖經密碼: 0.9s(上) / 0.2s(下) ```python= while 1: try: s, x, y = "", map(int, input().split()) if not x and not y: break for i in range(x): s += input().strip() for i in input().split(): print(s[int(i)-1], end='') print() except EOFError: break ``` ```python= from sys import stdin for l in stdin: s, x, y = "", map(int, l.split()) if not x and not y: break for i in range(x): s += stdin.readline().strip(); for i in stdin.readline().split(): print(s[int(i)-1], end='') print() ``` ---- ### C++ 0.4s ```cpp= #include <iostream> using namespace std; int main() { int n, m; while (cin >> n >> m && n) { string s, t, ans; for (int i=0; i<n; ++i) cin >> s, t += s; for (int a,i=0; i<m; ++i) cin >> a, ans+=t[a-1]; cout << ans << '\n'; } return 0; } ``` ---- ### C++ 80ms ```cpp= [|4] #include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; while (cin >> n >> m && n) { string s, t, ans; for (int i=0; i<n; ++i) cin >> s, t += s; for (int a,i=0; i<m; ++i) cin >> a, ans+=t[a-1]; cout << ans << '\n'; } return 0; } ``` ---- ### `ios_base::sync_with_stdio(false)` 讓兩種`IO`變得不同步用這行之後不要兩種同時使用 ---- ### `cin.tie(0)` 要把所有`endl`都改成`'\n'`，不然無效讓`cin`與`cout`之間的聯繫被切斷 ---- 如果要顯示東西，把東西丟到buffer一次輸出，會比直接從輸出流跑到顯示還快 ```graphviz digraph flush { rankdir=LR; node[shape = rectangle, fontsize=14]; fontsize=18; out[label="cout"]; dis[label="顯示"]; buf[label="buffer"]; subgraph cluster_flush{ label="會造成buffer flush的東西\n"; A[label="cout \<\< flush"]; B[label="cout << endl"]; C[label="沒.tie(0)的cin"] A->B[style=invis] B->C[style=invis] } out->buf[label="\n儲存"][minlen=2] buf->dis[label="flush"][minlen=2] } ``` --- # Macro 一些減短code的東西 ---- ### `#define nickname original` `#define`後`C++`會把所有的`nickname`當成`original` 前者不可包含空格 ```cpp= #define F first #define S second #define example ios_base::sync_with_stdio(false); cin.tie(0); int main { example //C++會把它當成ios_base::sync_with_stdio(false); cin.tie(0); pair<int, int> p; std::cout << p.F; //C++會把它當成p.first } ``` 梗：`#define`自己的`IO`優化是個人特色! --- # 壓常毒瘤 正常人不會需要的東西 但某些時候能唬爛AC 由於比較「非必要」，因此僅快速帶過 ---- ## TL; DR 把這兩行加你的`code`前面 ```cpp= [1-2] #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include <iostream> using namespace std; int main() { ... ``` ---- ### `#pragma GCC` ```cpp= #pragma GCC optimize("O3","unroll-loops") #include <iostream> using namespace std; int main() { ... ``` 在所有程式碼(包含`#include`)前加入用於調整程式編譯的設定這些設定「可能」讓你的程式加速 [參考資料](https://codeforces.com/blog/entry/96344) ---- 賽中通常會預設開啟`O2`優化在`O2`上還有`O3`、`Ofast`，但不一定較快 `target`更複雜，詳細可以自行搜尋 ```cpp= //以下皆是正確的寫法 #pragma GCC optimize("O3","unroll-loops") #pragma GCC optimize("O3,unroll-loops") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") ``` ```cpp= #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") ``` ---- ### 錯誤的寫法: 不要亂加空格、「省略」大小寫是`optimize`不是`optimization`! ```cpp= #pragma gcc optimize("O3") #pragma GCC optimize(" unroll-loops") #pragma GCC optimization("O3") #pragma optimize(O3) #pragma GCC target("avx2 ") #pragma GCC target("avx2, bmi") ``` ---- ### 毒瘤輸入數字 ```cpp= inline int R() { //讀取數字輸入 int neg=0, x=0, c=getchar(); while (c!=EOF && c!='-' && (c<'0'||c>'9')) c=getchar(); if (c=='-') neg=1, c=getchar(); for(; '0'<=c&&c<='9'; c=getchar()) x = x*10 + (c^'0'); //考慮'0'~'9'的ASCII，想想看為什麼能用xor return neg? -x : x; } //使用方法: int a = R(); ``` ---- ### 超級毒瘤輸入數字把上面的`getchar()`改成以下函式： ```cpp= inline char readchar() { const int S = 1<<20; // buffer size static char buf[S], *p = buf, *q = buf; if(p==q && (q = (p=buf)+fread(buf,1,S,stdin)) == buf) return EOF; return *p++; } ``` [(抄蛋餅的)](https://omeletwithoutegg.github.io/2019/12/06/Fast-IO/)