# 競程介紹 S1154005 李育林 ---- # 甚麼是競程  ----  ---- ## 競程=程式競賽 就是一群人在同一時間去解同一組題目比誰解的快  [What is CP](https://www.youtube.com/watch?v=ueNT-w7Oluw&ab_channel=WilliamLin) --- # 所以競程在幹嘛? ---- ## 競程的練習方式: 不斷寫題目練習+學新算法 <center> * 練題 * 補題 * Virtual </center> ---- ## 一些Online Judge平台 可以練習寫題目 提升各種算法的熟練度 及學到各種新算法 ---- ### Leetcode 主要以求職面試方向為主  ---- ### Codeforces/Atcoder 不定時會有線上競賽可以練習提升rating | | | | --- | --- | ---- ### CSES 主題式的各種基礎到進階資節及算法 聽說全部都會寫可以到國手等級(?  ---- ## 如何入門?  ---- 網路上有很多資源和電神分享的各種教學和經驗 * 從零開始的演算法競賽入門教學 * 演算法筆記 * Algorithms for Competitive Programming ---- # 各種競程比賽&活動 ---- ## 大學主要比賽 * NCPC * ICPC * TOPC * 中區程式設計競賽 ---- 除了這些比較正規官方辦的大型比賽 也有些企業或社團辦的交流賽 |HP Codewars|海洋盃/東華盃...| |--------|---------| || | ----  --- # 競賽技巧 ---- ## 隊員選擇 * 程式設計師 * 數學家 * 通靈王 * 英文好/打字快/不會讀錯題目... * ~~負責吃~~ ---- ## 時間複雜度 * 判斷一個做法會不會TLE * 從側資的範圍去反推演算法 * 通常會預設1s可以跑$10^8$ ---- 給$K(K<2X10^5)$找AxBxC<=K且A,B,C為正整數  TL=2 ---- 暴力解法($K^3$) ```cpp= #include<iostream> using namespace std; void solve() { int K; cin >> K; long long ans = 0; for(long long A = 1; A <= K; A++) { for(long long B = 1; B <= K; B++) { for(long long C = 1; C <= K; C++) { if(A * B * C <= K) ans++; } } } cout << ans << endl; ``` $8*10^{15} <= 10^{16}$ 可行 ---- 若今天TL給1秒呢? =>TLE 重新思考$O(K)<=10^8$解法 ---- ## debug技巧 練習遇到bug不能及時找到時: * 把code印出來自己到旁邊debug * 把code印出來給隊友debug * 寫對拍 ---- ## 對拍  ---- 1.寫對拍的 script 2.寫一份暴力程式碼 ac.cpp 3.寫一份產生隨機測資的程式碼 $\text{gen.py/gen.cp}$ ---- 大學比賽環境OS通常以linux為主 linux good ``` alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow` ``` ``` set -e g++ ac.cpp -o ac g++ wa.cpp -o wa for ((i=0;;i++)) do echo "$i" python3 gen.py > input ./ac < input > ac.out ./wa < input > wa.out diff ac.out wa.out || break done ``` ---- 生成亂數(python) ```python= from random import * n = randint(1, 100) # 隨機產生 1~100的整數 ch = chr(ord('a') + randint(0, 25)) # 隨機產生 'a'~'z' 其中一個字元 choiceSet = sample(s, 4) # 從s選出 4 個不同的元素 choiceSet = sample(range(1, n+1), 4) # 從整數 1~n 選出 4 個不同的元素 shuffle(arr) # 把序列 arr 順序打亂 ``` 生成亂數(C++) ```cpp= mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); int randint(int lb, int ub) { return uniform_int_distribution<int>(lb, ub)(gen); } ``` ---- ### 對拍的好處 * 可以重複驗證程式正確性，de完原本的bug可以再跑一次對拍 * 寫對拍的時間遠比多吃一次penalty還划算 * 記得錯的地方 ---- ## 其他有用的技巧 * 挑比較多人對的先寫 * 善用codebook * 放鬆&休息 * 多問電神 --- # 打競程有甚麼幫助? ---- ## 競程打得好 ≠ 容易找工作 ---- ## 找到接觸競程的目標 * 交朋友 * 打好玩的 * 培養打code和思考的習慣 * ~~吃免費點心~~ * ~~喜歡被電神虐~~ --- # Thank You