競賽技巧 & 競賽介紹

實用且常用pragma

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

• 一場五小時 10~15 題
• 三人一隊 只有一台電腦
• 一份紙本試題(比賽都是英文題目)
• 可以帶 25 頁 A4單面紙本資料
• 可以印 code
• 答對一題會有一顆氣球

各種比賽

見連結

• OS: windows(NCPC), linux(ICPC)
• judge system: domjudge
• language: c/c++, java, python, kotlin(icpc)

比賽排名

先比解題數，再比penalty

那 penalty 怎麼算?
每題解出來的時間加起來，再加上多錯的次數*20

以此記分板來看 penalty 為 35 + 7 + 2*20 = 82

開場

一個人先打好 default code
通常為手速最快或者主要coder

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    return 0;
}

其他人開始讀題目
通常為英文閱讀好、題目辨識難度強的人

為甚麼要先打 default code 呢?

• 殺首殺
  

• 每題要開始寫直接複製default code就好，減少寫程式碼量

看記分板 & 看別人的氣球

比賽中記分板，記得一定要定期刷新記分板，看大家解什麼題目

每題的氣球顏色都是固定的，因為記分板只能從電腦看，但如果隊友在上機看不了記分板就要觀察其他隊的氣球顏色

印code

比賽中隨時可以印出紙本code

那什麼時候要印

• 當bug找不到的時候
• 寫到一半發現想錯時

如果你是主coder 遇到bug
可以考慮給隊友找 自己再去開新的題目

評估題目

如果一次很多題目會寫，分析一下每題需要時間，根據greedy，先挑時間短的寫

比賽只有五小時，很短所以也要隨時注意時間
剩下一小時只留2~3題，最後半小時只留1~2題

補充血糖

比賽有五小時，很長XD

所以要定期去吃點心(建議1~2小時補充一次)
而且NCPC點心很好吃，很快就被搶光要搶要快(X

平常團隊訓練

養成良好分配習慣，知道彼此工作

賽後檢討彼此疏失或策略
修正策略

並且補題，也是最重要的，不補題跟沒打比賽一樣
不會解的題目還是不會

平常個人訓練

多打比賽，增加實作經驗
多寫題單，可以跟隊友溝通各自去練什麼演算法
多看電神的code，可以看到各種有趣精湛的寫法
各自專精擅長或有興趣的比賽也才能發揮各自所長

25 頁 A4單面紙本資料

• 又叫 codebook
• 範例codebook
• 跟隊友溝通要放什麼演算法
• 或者如果語法不熟也可以考慮放

• 瘋狂輸出
• linux 指令
• 對拍
• Debugging template
• hack測資

ICPC 國際大學生程式設計競賽

https://icpc2022.ntub.edu.tw/onsite/contest-environment/

NCPC 全國大專電腦軟體設計競賽

https://ncpc.ntnu.edu.tw/environment/final.html

• 對開發者較友善
• 更多好用的東西
• 等等對拍也會用到

如果我的電腦是 Windows ?

• 雙系統
• Windows Subsystem of Linux (WSL)

Windows Subsystem of Linux (WSL)

https://zhuanlan.zhihu.com/p/47541491
https://hackmd.io/@billsun/BJByCIUHf?type=view

linux 基本指令

cd ..        回到上一層資料夾
cd ../..     回到上上層資料夾
cd test      到當前目錄的test資料夾
ls           顯示當前資料夾的檔案
cat a.cpp    印出當前檔案的內容
mkdir test   在當前目錄建立 test 的資料夾
rm  a.cpp    刪除 a.cpp 的檔案

編譯檔案

g++ solve.cpp -o main -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow

g++ solve.cpp                編譯solve.cpp的檔案成 a.out 檔
g++ solve.cpp -o ac.out      編譯solve.cpp的檔案成 ac.out 檔
g++ solve.cpp -std=c++14     編譯solve.cpp的檔案成 a.out 檔 並且編譯版本為 c++14
./a.out                      執行 a.out 檔

其他編譯參數

-fsanitize=undefined  
插入各種undefined behavior檢查，會在執行期輸出錯誤訊息
 
-Wall -Wextra
把warning都開起來，常能預防bug發生
 
-Wshadow
當有宣告了相同變數名稱的情形發生時予以警告

g++ solve.cpp -o main -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow

難道每次都要打那麼長嗎 ?

Alias

可以使用 alias 把原本要打的那串 define 掉

alias [name]='[value]'

等同於 c++ 內的 #define
#define ll long long

alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow`

使用 Alias 之後

g++ solve.cpp

等價於

g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow solve.cpp

產生質因數

factor 100

對拍

步驟

1. 寫對拍的 script
2. 寫一份暴力程式碼 ac.cpp
3. 寫一份產生隨機測資的程式碼 gen.py/gen.cpp

對拍的 script

先將兩份程式碼分別編譯成 ac, wa
不斷用 gen.py 產生測資放到 input 檔案裡面
再把 input 檔案分別為給 ac, wa 兩份執行檔
用 for 迴圈一直跑到 output 內容不同為止
set -e 可以偵測程式 RE 時會停下來

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

跑到停下來後有兩種可能

1. RUNTIME ERROR

2. WRONG ANSWER

為甚麼要用對拍

• 找不到好的 case 能讓他自己跑 先寫其他題目
• 寫暴力程式碼的時間遠比多吃一次 20 penalty 還要來的划算
• 對拍可以重複驗證程式正確性，de 完原本的 bug 可以再跑一次對拍

因此當比賽時，如果對於錯誤毫無頭緒，
不應該只是盯著程式碼看，而是開始寫對拍才是最有效率的做法

而平時練習、作業找不到bug的情況也應該要先對拍
真的找不到問題 對拍也對不到 再去問其他電神錯在哪

步驟

1. 寫對拍的 script
2. 寫一份暴力程式碼 ac.cpp
3. 寫一份產生隨機測資的程式碼 gen.py/gen.cpp

寫一份暴力程式碼 ac.cpp

聽起來好麻煩，為了 debug 還要多寫一份 code
而且不一定寫得出來還有可能錯，怎麼辦?

如果連暴力的程式碼都寫不出來 那你應該多練練你的實作能力…

如果不知道怎麼寫請參考早上 brute force 講義

善用 next_permutation 以及好好熟悉遞迴
沒有暴力寫不了的程式碼 只有你不練不夠實作能力

步驟

1. 寫對拍的 script
2. 寫一份暴力程式碼 ac.cpp
3. 寫一份產生隨機測資的程式碼 gen.py/gen.cpp

產生隨機測資 (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 順序打亂

隨機產生一組 1~n 的 permutation

from random import *
 
n = randint(3, 6)
 
arr = [i+1 for i in range(n)]
shuffle(arr)
 
print(n)
print(*arr)    #輸出 arr 的內容並且用空格隔開

隨機產生一個長度為 n 的小寫字母字串

s = ""
n = randint(1, 10)
 
for i in range(n):
    s += chr(ord('a') + randint(0, 25))
print(s)

隨機產生一棵樹

每次從比自己小的節點選一個當連接自己的邊

from random import *
 
n = randint(3, 6)
 
print(n)
for i in range(2, n+1):
    print(randint(1, i-1), i)

隨機產生無自環無重邊的一張連通圖

無自環 可以判斷兩個點不相同
無重邊 可以用 dict/map 紀錄哪些邊用過了

連通圖 = 樹 + 一些額外的邊

隨機產生無自環無重邊的一張連通圖

from random import *
 
n = randint(5, 10)
m = randint(n-1, n+3)
 
print(n, m)
 
edge = list()
 
#construct tree
for i in range(2, n+1):
    x = randint(1, i-1)
    y = i
    edge.append([min(x, y), max(x, y)])
    print(x, y)
 
#add extra edge
for i in range(m-(n-1)):
    x = randint(1, n)
    y = randint(1, n)
    while x == y or [min(x, y), max(x, y)] in edge:
        x = randint(1, n)
        y = randint(1, n)
    print(x, y)
    edge.append([min(x, y), max(x, y)])

產生隨機測資 (c++)

Don't use rand(): a guide to random number generators in C++

mt19937 是 c++ 的一種隨機產生器

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int randint(int lb, int ub)
{ return uniform_int_distribution<int>(lb, ub)(gen); }

sample code(c++)

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int randint(int lb, int ub)
{ return uniform_int_distribution<int>(lb, ub)(gen); }
 
int main(){
    int n = randint(1, 10);        //產生 0~10 之間的任意整數
    char ch = 'a'+randint(0, 25);  //產生 a-z 之間的任意字母
 
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    shuffle(ord.begin(), ord.end(), gen);
    cout << n << endl;
    for(int i : ord)    cout << i << " ";
    cout << endl;
}

練習產測資

隨便拿一場比賽練習每一題如何產測資

2023 I2CP Pretraining Final Contest

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

Debug –- Print 大法

可能有問題的那段程式碼 把變數 print 出來

cout << "Before" << endl;
for(int i = 0; i < n; i++){
    cout << arr[i] << ' ';
}
cout << endl;
.
.
.
cout << "After" << endl;
for(int i = 0; i < n; i++){
    cout << arr[i] << ' ';
}
cout << endl;

這樣會有什麼問題 ?

1. debug 完 bug 忘記註解/刪掉

2. debug 完把 printer 註解，但沒有註解乾淨

3. 好麻煩喔 先把所有 cout 都註解la 再把要輸出的反註解

4. 喔 好像多註解到要輸出的答案了

這樣會有什麼問題 ?

penalty += 80(20 * 4)

cerr

debug 時，很常會用cout輸出每個變數的值
在這邊建議輸出debug的值時使用cerr

他輸出的東西只會出現在 Standard error stream
不會輸出在 Standard output stream

答案比對是比對 Standard output stream 的內容
因此就算忘記刪也不會造成影響

// __LINE__ 會輸出呼叫的位置在程式碼第幾行
cerr << "This is debug message on " << __LINE__ << " line : " << x << endl;

cerr 問題

如果沒有刪掉可能造成 TLE

for(int i = 0; i < n; i++){
    x *= 2;
    arr[x] += v;
    for(int j = 0; j < n; j++){
        cerr << arr[j] << " ";
    }
    cerr << endl;
}

原本可能 \(O(N)\) 的程式碼變成 \(O(N^2)\)

或者常數太大 (輸出數量變成原本的兩倍)

Debugging template

讓你更好 debug 的工具

#ifdef LOCAL    // =========== Local ===========
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } 
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } 
#define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args))
#else            // ======== OnlineJudge ========
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
 
#ifdef LOCAL    // =========== Local ===========
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } 
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } 
#define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args))
#else            // ======== OnlineJudge ========
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
 
#ifdef LOCAL    // =========== Local ===========
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } 
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } 
#define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args))
#else            // ======== OnlineJudge ========
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
 
#ifdef LOCAL    // =========== Local ===========
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } 
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } 
#define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args))
#else            // ======== OnlineJudge ========
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
 

#ifdef LOCAL

如果有 define LOCAL
那就會…

#ifdef LOCAL    // =========== Local ===========
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } 
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } 
#define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args))

否則就會…

#else            // ======== OnlineJudge ========
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif

在本機 define LOCAL

g++ solve.cpp -D LOCAL

則編譯時就會 define LOCAL

但每次都要打 -D LOCAL 很麻煩…

還記得 alias

alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow`

改成

alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow -D LOCAL`

:happymention:

debug 變數

debug(x)

string x = "abc";
debug(x);
int y = 123;
double z = 1.23;
debug(y, z);

debug 範圍

orange(begin, end)

int arr[5]={2,1,4,3,5};
orange(arr, arr+5);
 
vector<string> strVec = {"Alice", "Bob"};
orange(strVec.begin(), strVec.end());

```cpp=
#ifdef LOCAL    // =========== Local ===========
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } 
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } 
#define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args))
#else            // ======== OnlineJudge ========
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
 

assert

他用來判斷一個條件是否成立，
如果條件成立則不會發生任何事

如果條件不成立，則會造成程式RE(Runtime Error)
通常用於 debug 不確定會不會錯
或者想 submit 時 不確定有沒有問題用的

assert(x <= 5);

long long fpow(int x, int y){
    long long ret = 1;
    for(;y;y>>=1, x*=x){
        if(y&1)  ret = ret * x;
    }
    return ret;
}
 
int main(){
    cin >> n;
    auto [x, y] = solve(n);
    assert(fpow(x, y) * y + fpow(y, x) * x == n);
    cout << x << " " << y << endl;
}
long long fpow(int x, int y){
    long long ret = 1;
    for(;y;y>>=1, x*=x){
        if(y&1)  ret = ret * x;
    }
    return ret;
}
 
int main(){
    cin >> n;
    auto [x, y] = solve(n);
    assert(fpow(x, y) * y + fpow(y, x) * x == n);
    cout << x << " " << y << endl;
}
long long fpow(int x, int y){
    long long ret = 1;
    for(;y;y>>=1, x*=x){
        if(y&1)  ret = ret * x;
    }
    return ret;
}
 
int main(){
    cin >> n;
    auto [x, y] = solve(n);
    assert(fpow(x, y) * y + fpow(y, x) * x == n);
    cout << x << " " << y << endl;
}
long long fpow(int x, int y){
    long long ret = 1;
    for(;y;y>>=1, x*=x){
        if(y&1)  ret = ret * x;
    }
    return ret;
}
 
int main(){
    cin >> n;
    auto [x, y] = solve(n);
    assert(fpow(x, y) * y + fpow(y, x) * x == n);
    cout << x << " " << y << endl;
}
long long fpow(int x, int y){
    long long ret = 1;
    for(;y;y>>=1, x*=x){
        if(y&1)  ret = ret * x;
    }
    return ret;
}
 
int main(){
    cin >> n;
    auto [x, y] = solve(n);
    assert(fpow(x, y) * y + fpow(y, x) * x == n);
    cout << x << " " << y << endl;
}

或者想猜測資，判斷是否大於某個值，就可以assert
再加上 TLE 一起用

每次可以把測資分三半去猜測資 複雜度 \(O(log_3N)\)

cin >> n;
if(n >= 10){       // RE
    assert(0);
}
else if(n > 5){    // TLE
    while(1){}
}
else{              // WA
    return 0;
}

Benq's submission
Who is Benq?

• 溢位
• 陣列超出範圍
• 邊界測資 n=1 n=2 n=bound