競技プログラミング: C++ STL

個人メモ 競技プログラミング

E869120 さんの記事 を参考にした個人メモ

include

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

cmath

  • abs(x), sin(x), cos(x), tan(x)

    string

string S = "hoge"; 
S[i] = 'z' // i 文字目が 'z' に変わる
S += T; // 連結 (T は string または char)
S.size() // 文字数
S.substr(l, r) // l 文字目から l+r-1 文字目までの部分文字列を返す

algorithm

  • min(): 引数として 2数 または, {3,5,1,9} 形式で与える
  • *min_element(c + l, c + r): min({c[l], c[l+1], ..., c[r-1]})におなじ
    • min_elementの返却値は最小要素のイテレータ(=抽象化されたポインタのことで、コンテナの要素を指し、移動、要素を参照・変更することが出来る)
  • __gcd(a, b): 最大公約数(C++17からgcd(a,b))
  • reverse(a + l, a + r) : a[l], a[l+1], ..., a[r-1] を逆順に並び替え
    • 文字列反転: reverse(str.begin(), str.end())
  • sort(a + l, a + r) : a[l], a[l+1], ..., a[r-1] を昇順に O(NlogN)
    • sort(a + l, a + r, greater<Type>()); : 降順 も必要
  • lower_bound(a+l, a+r, x): 昇順ソートされた配列aのうち, x以上の要素のうち, 最初の要素のイテレータを返す。つまり, lower_bound(a+l, a+r, x) - a でその index がわかる。O(log N)
    • upper_bound は「x以上」ではなく, 「xよりおおきい」
  • count(a + l, a + r, x): 値がxの個数
  • find(a + l, a + r, x) : 値がxのがあれば最初の要素へのイテレータ。なければ a+r へのイテレータ
  • next_permutation(a,a+4): 部分コンテナ {a[0], a[1], a[2], a[3]} に対して, 順番的に次の a[0], a[1], a[2], a[3] の並び替えのコンテナを a に格納する?
    • a = [2,2,3] のとき, next_permutation(a,a+3) で a は [2,3,2] になる。

vector

vector<Type> a;
// 動的な配列であるが, 名前が先頭要素へのポインタではないので a.begin() を使え
sort(a.begin() + l, a.begin() + r)
a.push_back(x); // 後ろにpush。先頭はない。emplace_back のほうが一時オブジェクトを作らない分速い
a.pop_back(); // 後ろからpop
// a.size(), a[i] は配列とおなじ

stack

stack<Type> a;
// push(x), pop(), size() は vector と同機能
// top() は最終要素の値取得
// empty() は空か判定する

queue

queue<type> a;
// push(x), empty(), size() は stack におなじ
// pop() は先頭からとる。
// front() は先頭要素

queue, vector, functional

  • priority_queue
// 小さい要素のほうが優先度が高い
priority_queue<int, vector<int>, greater<int>> Q1;
// 大きい要素のほうが優先度が高い
priority_queue<double, vector<double>, less<double>> Q2;
// push(x), empty(), size() は stack におなじ
// pop(), top() は優先度の高いものから
// push, pop, top は O(logN)

map

// key: int, value: string (2^31 要素の string 型配列と同じような感じ)
map<int, string> M1;
// key: string, value: double
map<string, double> M2;
M1.clear() // 初期化
M1[2434525] = 5; // アクセスにかかる計算量は O(logN) ただし, N はアクセス数

set, multiset

  • 大体の操作は O(logN)
  • set 内では昇順に要素が並ぶ。イテレーター itr に対し itr++ で次の要素を指す
set<Type> a;
a.insert(x); // すでにある時は追加しない, multisetなら追加する
a.erase(x); // xが値の時, その要素を(全て)削除する, イテレータならその要素のみ削除
// clear(), lower_bound(x)

utility (pair), tuple

  • pair: 2つの要素を持てる値
  • tuple: pair の個数制限なしver
pair<int, string> a; // a.first, a.second で各要素にアクセス
// 大小比較は まず1つ目の要素で比較し, 同じなら2つ目
tuple<int, int, double> a;
a = make_tuple(2,4,5.5) // 引数はコピーされる
get<0>(a) // -> 2

bitset

  • ビット演算が可能
bitset<10000> a; // 10000 桁の2進数
// "110" や 6 で初期化すると 000...000110 となる
a.set(5) // 5桁目を1にする
a.reset(5) // 5桁目を0にする
a[5] // 配列的なアクセスが可能

cassert

  • assert(条件) : 条件がfalseならランタイムエラー

ctime

  • 時間測定
int start = clock(); // プログラム実行開始から何単位時間経過したかを整数で返す
...
int stop = clock();
double sec = 1.0 * (stop - start) / CLOCKS_PER_SEC; // CLOCKS_PER_SEC 1 秒が何単位時間か
  • 乱数
srand((unsigned)time(NULL));
rand() // 0~2^31-1(コンパイラによる)のランダムな整数を返す関数

ない

  • swap(a, b)
  • __builtin_popcount(x): 整数 x を二進数で表したとき、1 であるようなビットの個数を返す(__builtin_popcountll(x)はlong longに対応)