このライブラリについて

各事項

動作は保証しません．
- issueを出してくださると直すかもしれません．
- ❌がついている項目は未実装です．
- ⚠️がついている項目は未実装なところが一部あります．
CTF関係のプログラムのみpython，他は全てC++です．
ドキュメントの充実さよりも項目を増やすことの方が優先度が高いので説明文は結構適当です．
全てのソースコードを私shibaken28が書いたわけではないです
- 自分が書いていないコードはCC0ライセンスで公開されているものを使用しています．
- 余談ですが，勉強のため，できるだけ自分で一度は実装するようにしています．

メモ

git subtree push --prefix docs/book/ origin gh-pages

C++の仕様や便利機能

Makefile

オプションをつけないとC++17でコンパイルされない．構造体束縛とかが使えなくて泣く．毎回オプションを付けるのは面倒なので，Makefileを作っておくと便利．

#Makefile
CC=g++
CFLAGS=-Wall -std=c++17
.SUFFIXES = .cpp
objs:=$(wildcard *.cpp)
targets:=$(objs:.cpp= )

.PHONY:all
all: $(targets)
.cpp:
	$(CC) $(CFLAGS) -o $@ $<

構造体束縛

C++日本語リファレンスよりコードを引用

std::pair<int, std::string> f()
{
  return {3, "Hello"};
}

// 関数f()の戻り値である整数と文字列の組を分解する。
// pairのfirstをid変数に代入し、secondをmessage変数に代入する。
// id変数の型はfirstの型(int)となり、message変数の型はsecondの型(string)となる。
auto [id, message] = f();

これにより，pair型などで受け取って中身をいちいち別の変数に取り出す手間がなくなる．

mapの値の取り出しでも重宝する．

map<int,int> mp;
for(auto [key,value]:mp){
    //key,valueを使う
    cout<<key<<" "<<value<<endl;
}

ラムダ式

関数に関数を渡すときに便利．構文は次の通り．

[キャプチャする変数](引数){ 関数の本体 }

型名はよくわかんないのでautoに任しておく．

auto pow = [](int a){return a*a;}; //引数aを受け取ってa*aを返す関数
cout<<pow(4)<<endl; //16

ラムダ式の中で外の変数を使いたい場合はキャプチャする．

int x=4;
auto mul = [x](int a){return x*a;};
cout<<mul(3)<<endl; //12

&を付けると参照キャプチャになる．他にもキャプチャの種類があるがここでは紹介しない．

int x=4;
auto mul = [&x](int a){return x*a;};
cout<<mul(3)<<endl; //12

`cin`と`cout`を定義

vectorとかpair，setをcoutできるようにすると便利(これをまとめて書く方法を知っている方がいれば教えてください)．

//vector
template<class T> std::ostream &operator<<(std::ostream &out, const vector<T> &A){
    for(const T &a:A){
        cout<<a<<" ";
    }
    return out;
}
//pair
template<class T1,class T2> std::ostream &operator<<(std::ostream &out, const pair<T1,T2> &A){
    cout<<"{"<<A.first<<","<<A.second<<"}";
    return out;
}
//map
template<class T1,class T2> std::ostream &operator<<(std::ostream &out, const map<T1,T2> &M){
    for(const auto&A:M){
        cout<<"{"<<A.first<<","<<A.second<<"}";
    }
    return out;
}
//set
template<class T1> std::ostream &operator<<(std::ostream &out, const set<T1> &M){
    cout<<"{";
    for(const auto&A:M){
        cout<<A<<", ";
    }
    cout<<"}"<<endl;
    return out;
}

また，cout<<a<<" "<<b<<" "<<c<<" "<<d<<endlは次の定義によってprint(a,b,c,d)で書ける(厳密には余計な空白が入るので注意)．

void print() { cout << endl; }
 
template <typename Head, typename... Tail>
void print(Head H, Tail... T) {
  cout << H << " ";
  print(T...);
}

ちょっとしたコーディングテクニック

C++の仕様や便利機能に対し，こちらは言語を問わずに使えるコーディングテクニックを紹介する．

`vector`以外のデータ構造

queueやstack，dequeを用いると，vectorよりも簡潔に書けることがある．

幅優先探索(queue)
深さ優先探索(stack)
括弧列の検証(stack)
逆ポーランド記法(stack)
ヒストグラムの最大面積(stack)
01BFS(deque)

番兵，余分な要素

例外処理を完結にするために，番兵と呼ばれる特殊な値を配列の先頭や末尾に挿入しておく． C言語だと，文字列におけるナル文字\0がその例である．

大きな数を使う手法

問題を言い換えると，

$N$個の正の整数$a_1, a_2, \dots, a_N$が与えられる($0\leq a_i\leq 10^9$)．
$N$個の整数のうち，偶奇が同じ$2$つの数を取り出して和を考えるとき，その最大値を求めよ．
存在しない場合はその旨を出力せよ．

奇数と偶数で分けて，それぞれ大きい方から$2$つ和のうち大きい方を出力すれば良い．ただし，奇数が$1$つしかない場合や偶数が$1$つしかない場合を考慮する必要がある．このとき，奇数や偶数の配列に$-10^{12}$を$2$つずつ入れておくことで，答えがマイナスになった場合はそのような数が存在しないことを表すことができる(実装例)．

迷路を壁で囲む

グリッドで表される迷路を探索するような問題で，盤面を囲むような壁を設置することで，グリッドの端に到達したときの処理を簡潔にすることができる．

天井関数

int ceil(int a, int b) {
    return (a + b - 1) / b + 1;
}

を用いると，$a/b$以上の最大の整数を求めることができる． C言語では，ceil関数が標準ライブラリに含まれているが，浮動小数点の計算を信用していない人はこれを使うと良いだろう．

浮動小数点型を使わない

浮動小数点型を使わないことで，計算誤差を防ぐことができる．例えば，$\frac{a}{b}$と$\frac{c}{d}$の値の比較を行う場合，$a/b<c/d$という式を書かずに，$a\cdot d<c\cdot b$という式を書くことで，誤差を防ぐことができる(オーバーフローには注意)．

他にも，ルートがつかないように変形したり，logの真数の比較であったり，整数の範囲でできる場合はしたほうが良い．

超頂点

グラフの頂点に番号がふってあり，同じ番号同士であれば行き来できるようなグラフを考える．

よくある考察

メタ読み

制約が$N=20$のときは，$2^N$通りのbit全探索
制約が$N=40$くらいのときは半分全列挙
- これは半分全列挙感がすごいABC271 F - XOR on Grid Path

線形変換

線形漸化式
行列を使って表すことができる
dpの遷移が線形変換で表せるときは高速化ができる
BasyStepGiantStepが使えるパターン(ABC270 G - Sequence in mod P)
セグメントツリーに乗るARC008 D - タコヤキオイシクナール

よくあるバグ

前提

コンパイルするファイルが間違っている
実行するファイルが間違っている
実はコンパイルに失敗していて，最後にコンパイルが成功したファイルを実行している

コンパイルできない

ヘッダがない
- 人のコードパクってきたときにfuncionalヘッダがなかった
using namespaceがない
変数名とdefineの重複
vector<vector<long>> A(N,vector<int>(0))みたいに型が一致していない
<Templete T>の書き忘れ

コーナーケース

N=1,K=0などの極端な値
A=Bのとき
同じクエリが複数回来るかもしれない
自己ループ，同じ辺
0の0乗,0の階乗の定義

実行が終わらない

入力を受け取りすぎている
- クエリの数Qと要素数Nが混同してしまう
n重for文でインクリメントする変数を間違える
n重for文で変数名が重複
計算量が多い
- setに要素を大量に入れている可能性

セグフォ

cinを忘れている
二項係数ライブラリとかの前計算した配列の範囲外参照
文字列の操作中に空文字が登場する
0,1-indexedの混同
- セグ木とかに多い

その他ハマり

modを正しく取れていない

modを取ってない
mod(法)の値が間違っている(998244353,1e9+7)
modの取り方を間違っている
- 法が素数でない，逆元が存在しない
- mod 3とかでの二項係数はルーカスの定理を使う
modを取りながら累積和したときに負の数がでる
- (A[r]-A[l-1]+mod)%modみたいな配慮
- modint構造体を使おう
最後にマイナス1などをしている(0のときに-1が出力されてしまう)

セグ木

実はモノイドではなかった
単位元が間違っている
- 更新クエリの単位元を$0$にすると壊れる場合がある
ビルドができていない

二分探索

初期値で候補から外れている値が実は答え
- 答えの上限値が10^9なのに二分探索の上限の初期値を10^9にしている

未分類

改行(flush)しないと標準出力にでてこない
cin>>a,b;みたいなことをしている
- エラーが出ないことがあるのでハマりやすい
switch文でbreak忘れ
make cleanを試す
型のパース，intをlongの計算にそのまま突っ込むのは良くない
調和級数の計算量勘違い
コンストラクタの名前を間違えている
閉区間，半開区間などの違い
- 累積和で区間和を出す場合に注意
setやmapでstd::lower_boundなどは使えない
- メソッドとして用意されている
01ナップザックで昇順にdpを回してしまった
- それは個数制限なし
bool型をint型だと思って
- bool値に2以上を入れてもサイレントに1になる
ソート後の配列をソート前の状態として扱ってしまった
格子点とグリッドマス目の関係
- 角の座標の扱い
不等式における累乗の注意
- 偶数乗した場合負の数が正になる
ビットシフト演算子の計算順序
- 四則演算のほうが早い(1<<2+2は1<<4で16になる)
long型リテラルにしわすれてオーバーフロー
- 1<<40はオーバーフローする．1L<<40が正しい．

データ構造

C++が用意しているデータ構造

競プロのための標準C++

`vector`

配列．
# include < vector >ヘッダをインクルードすることで使用できる．

初期化

vector<int> A(10,0); // 10個の要素を持つint型の配列．初期値は0．
vector<int> B = {3,1,4,1,5}; //要素を指定して初期化．
vector<int> C;// 空の配列．

要素の取得

ランダムアクセスが$O(1)$で可能．

vector<int> A = {3,1,4,1,5};
cout << A[0] << endl; // 3
cout << A[1] << endl; // 1
cout << A[2] << endl; // 4
cout << A[3] << endl; // 1
cout << A[4] << endl; // 5
cout << A.size() << endl; // 要素数を返す．

要素の追加と削除

vector<int> C;// 空の配列．
C.push_back(2); // Cの末尾に2を追加．
C.pop_back(); // Cの末尾の要素を削除．

ソート

$O(N\log N)$かかる．

vector<int> B = {3,1,4,1,5};
sort(B.begin(),B.end()); // Bを昇順に並び替え．
sort(B.begin(),B.end(),greater<int>()); // Bを降順に並び替え．

`set`

重複なしの集合．
# include < set >ヘッダをインクルードすることで使用できる．

初期化

set<int> A = {3,1,4,1,5}; //要素を指定して初期化．
set<int> B;// 空の集合．

要素の取得

ランダムアクセスはできない．
range based for loopが使える．
要素が含まれているかは$O(\log N)$でcountメンバ関数で判定できる($0$ならば含まれていない，$1$ならば含まれている)．
イテレータの使用して次に大きい要素や次に小さい要素を取得することもできる(詳細)．

set<int> A = {3,1,4,1,5};
cout << A.size() << endl; //4．要素数を返す．
for(auto x:A){
    cout << x << endl; // 1,3,4,5の順に出力される．
    //勝手に昇順になっている．要素は重複しない．
}
cout << A.count(1) << endl; // 1がAに含まれているか．

要素の追加と削除

set<int> B;// 空の集合．
B.insert(2); // Bに2を追加．
B.erase(2); // Bから2を削除．

`map`

キーと値のペアを格納する．
# include < map >ヘッダをインクルードすることで使用できる．

初期化

map<int,int> A = {{1,2},{3,4},{5,6}}; //要素を指定して初期化．
map<int,int> B;// 空のmap．

要素の取得

ランダムアクセスはできない．
range based for loopが使える(キーと値がpair型でもらえる)．
イテレータの使用して次に大きい要素や次に小さい要素を取得することもできる(詳細)．

map<int,int> A = {{1,2},{3,4},{5,6}};
cout << A.size() << endl; //3．要素数を返す．
cout << A[1] << endl; // 2
cout << A[3] << endl; // 4
cout << A[5] << endl; // 6
for(auto x:A){
    cout << x.first << " " << x.second << endl; // 1 2,3 4,5 6の順に出力される．
    //勝手にキーの昇順になっている．
}

`queue`

LIFO(First In First Out)のデータ構造．
# include < queue >ヘッダをインクルードすることで使用できる．

初期化

queue<int> A;// 空のqueue．

要素の操作

queue<int> A;
A.push(1); // Aの末尾に1を追加．
A.push(2); // Aの末尾に2を追加．
A.push(3); // Aの末尾に3を追加．
cout << A[0] << endl; // 1
cout << A.front() << endl; // 1
A.pop(); // Aの先頭の要素を削除．
cout << A.front() << endl; // 2
A.pop(); // Aの先頭の要素を削除．
cout << A.front() << endl; // 3
A.pop(); // Aの先頭の要素を削除．

`stack`

FIFO(First In Last Out)のデータ構造．

初期化

stack<int> A;// 空のstack．

要素の操作

stack<int> A;
A.push(1); // Aの末尾に1を追加．
A.push(2); // Aの末尾に2を追加．
A.push(3); // Aの末尾に3を追加．
cout << A.top() << endl; // 3
A.pop(); // Aの末尾の要素を削除．
cout << A.top() << endl; // 2
A.pop(); // Aの末尾の要素を削除．
cout << A.top() << endl; // 1
A.pop(); // Aの末尾の要素を削除．

`deque`

queueとstackのキメラ．ランダムアクセスも可能である．
# include < deque >ヘッダをインクルードすることで使用できる．

初期化

deque<int> A;// 空のdeque．

要素の操作

deque<int> A;
A.push_back(1); // Aの末尾に1を追加．
A.push_back(2); // Aの末尾に2を追加．
A.push_back(3); // Aの末尾に3を追加．
A.push_front(4); // Aの先頭に4を追加．
A.push_front(5); // Aの先頭に5を追加．
A.push_front(6); // Aの先頭に6を追加．
cout << A[0] << endl; // 6
cout << A[1] << endl; // 5
cout << A[2] << endl; // 4
cout << A[3] << endl; // 1
cout << A[4] << endl; // 2
cout << A[5] << endl; // 3
A.pop_back(); // Aの末尾の要素を削除．
A.pop_front(); // Aの先頭の要素を削除．
cout << A[0] << endl; // 5
cout << A[1] << endl; // 4
cout << A[2] << endl; // 1
cout << A[3] << endl; // 2

`priority_queue`

優先度付きキュー．
# include < queue >ヘッダをインクルードすることで使用できる．

初期化

priority_queue<int> A;// 空のpriority_queue．

要素の操作

大きい方から出てくる．

priority_queue<int> A;
A.push(2); // Aの末尾に2を追加．
A.push(3); // Aの末尾に3を追加．
A.push(1); // Aの末尾に1を追加．
cout << A.top() << endl; // 3
A.pop(); // Aの末尾の要素を削除．
cout << A.top() << endl; // 2
A.pop(); // Aの末尾の要素を削除．
cout << A.top() << endl; // 1
A.pop(); // Aの末尾の要素を削除．

`list`

双方向連結リスト．
# include < list >ヘッダをインクルードすることで使用できる．

初期化

list<int> A;// 空のlist．

要素の操作

list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_front(3);
ls.push_front(4);
for_each(ls.begin(),ls.end(),[](int a){
    cout<<a<<" "; // 4 3 1 2
});
cout<<endl;
auto it = ls.begin();
it++;
ls.insert(it,5);
for_each(ls.begin(),ls.end(),[](int a){
    cout<<a<<" "; // 4 5 3 1 2
});
cout<<endl;

UnionFind

概要

UnionFindは、グラフの連結成分を管理するデータ構造．次の操作がそれぞれ高速(ほぼ定数時間)に行える．

root(x) : xの根を返す．
unite(u,v) : u,vをマージする
same(u,v) : u,vが同じ連結成分に属するかを判定する．
getGroup(x) : 現在の連結成分のリストを返す．
getWeight(x) : xが属する連結成分の重みを返す．
changeWeight(x) : 頂点xの重みを変更する．

shiba's Library