限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。

頻度高く定期的に開催されるコンテスト

• AtCoder
• Codeforces

main.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {

    return 0;
}

STL

コンテナ

map

map<ll, ll> m;
++m[0]; // 初期値 0

for(map<ll, ll>::iterator it = m.begin(), end = m.end(); it != end; ++it) { // it->first, it->second
}

m.count(0); // 存在確認 (0 or 1)

m.size();
m.erase(0);
m.clear();

multimap

multimap<ll, ll> mm;
mm.insert(make_pair(0, 1));

for(multimap<ll, ll>::iterator it = mm.begin(), end = mm.end(); it != end; ++it) {
}

ll cnt = mm.count(0);
for(multimap<ll, ll>::iterator it = mm.find(0); cnt-- > 0; ++it) {
}

mm.size();
mm.erase(0);
mm.clear();

set

set<ll> s;
s.insert(0);

for(set<ll>::iterator it = s.begin(), end = s.end(); it != end; ++it) {
    // *it (asc 0, 1, 2,...)
}
for(set<ll>::reverse_iterator it = s.rbegin(), end = s.rend(); it != end; ++it) {
    // *it (desc 99, 98, 97,...)
}

s.count(0); // 存在確認 (0 or 1)

s.size();
s.erase(0);
s.clear();

multiset

multiset<ll> ms;
ms.insert(0);

for(multiset<ll>::iterator it = ms.begin(), end = ms.end(); it != end; ++it) {
    // *it (asc 0, 1, 2,...)
}
for(multiset<ll>::reverse_iterator it = ms.rbegin(), end = ms.rend(); it != end; ++it) {
    // *it (desc 99, 98, 97,...)
}

ll cnt = ms.count(0);
for(multiset<ll>::iterator it = ms.find(0); cnt-- > 0; ++it) {
}

ms.size();
ms.erase(0);
ms.clear();

priority_queue

priority_queue<ll> pq; // 99, 98, 97, ...
priority_queue<ll, vector<ll>, greater<ll> > pq; // 0, 1, 2, ...
pq.push(0);
while(!pq.empty()) {
    ll n = pq.top(); pq.pop();
}

priority_queue<pair<ll,ll> > pq; // (first, second): (5,5),(4,4),(4,3),...
priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq; // (first, second): (0,0),(1,1),(1,2),...
pq.push(pair<ll,ll>(0,0));
while(!pq.empty()) {
    pair<ll,ll> pll = pq.top(); pq.pop(); // pll.first, pll.second
}

queue

queue<ll> q;
q.size();
q.push(0);
while(!q.empty()) { // BFS
    ll n = q.front(); q.pop();
    if(...) {
        q.push(...);
    }
}

stack

stack<ll> s;
s.size();
s.push(0);
while(!s.empty()) {
    ll n = s.top(); s.pop();
}

deque

deque<ll> dq;

dq.push_back(0);
dq.back();
dq.pop_back();

dq.push_front(0);
dq.front();
dq.pop_front();

dq.size();
dq.clear();
dq.empty();

list

list<ll> lst;

lst.sort(); // 0, 1, 2, ...
lst.sort(greater<ll>()); // 99, 98, 97, ...
lst.unique(); // 重複削除 (sort 必須、返り値なし)

list<ll>::iterator pos = lst.end();
lst.insert(pos, 0); // [0, *pos]
lst.insert(pos, 1); // [0, 1, *pos]
lst.erase(pos); // 削除された要素の次の要素を指すイテレータを返す

lst.push_back(0);
lst.back();
lst.pop_back();

lst.push_front(0);
lst.front();
lst.pop_front();

for(list<ll>::iterator it = lst.begin(), end = lst.end(); it != end; ++it) {
    // *it
}

// tolst = [tolst, lst, fromlst]
list<ll> fromlst;
list<ll> tolst;
tolst.splice(tolst.end(), lst);
tolst.splice(tolst.end(), fromlst);

lst.size();
lst.clear();

文字列

scanf による標準入力 (cin では遅い場合、特殊なフォーマットの場合)

scanf("%d %d", &x[i], &y[i]);

printf による標準出力 (特殊なフォーマットの場合)

double d = 0.01;
printf("%.3f\n", d); // 0.010

数値と文字列の変換

ll conv(string num) { stringstream ss; ss << num << flush; ll n; ss>>n; return n; }
string conv(ll n) { stringstream ss; ss << n << flush; return ss.str(); }

文字列 split

vector<string> split(string s, string delim) {
    vector<string> res;
    int pos = 0;
    while(true) {
        int found = s.find(delim, pos);
        if(found >= 0) {
            res.push_back(s.substr(pos, found - pos));
        }
        else {
            res.push_back(s.substr(pos));
            break;
        }
        pos = found + delim.size();
    }
    return res;
}

アルファベット

int ALPH_SIZE = 26;
char ALPH_L[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char ALPH_U[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

string

int pos = str.find("xxx"); // 左から検索 (-1 or pos)
int pos = str.find("xxx", start_pos);
int pos = str.rfind("xxx"); // 右から検索 (-1 or pos)

// 非破壊的
str.substr(pos, len);
str.substr(pos); // 末尾まで

// 破壊的
str.replace(pos, len, "yyy");
str.insert(pos, "_INSERT_"); // _INSERT_xxx
str.erase(pos, len);
str.erase(pos); // 末尾まで

strcmp(s1.c_str(), s2.c_str());
// s1 < s2 -1
// s1 = s2  0
// s1 > s2  1

sstream

stringstream ss; ss.str("");
ss << "10 9" << flush;
string str = ss.str();
int a,b; ss>>a>>b;

配列

algorithm

sort(arr, arr + MAXN); // 0, 1, 2, ...  a, b, c, ...
sort(arr, arr + MAXN, greater<ll>()); // 99, 98, 97, ...  z, y, x, ...
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<ll>());
sort(v.begin(), v.end()); // (0,0), (1,1), (1,2), ...
sort(v.begin(), v.end(), greater<pair<ll,ll> >()); // (100,100), (99,99), (99,98), ...
sort(v.begin(), v.end(), greater<pair<string,string> >());

bool pls_comp(pair<ll,string> a, pair<ll,string> b) {
    return a.first < b.first; // 0, 1, 2, ...
    // return strcmp(a.second.c_str(), b.second.c_str()) < 0; // a, b, c, ...
}
sort(v.begin(), v.end(), pls_comp);

reverse(arr, arr + MAXN);
reverse(v.begin(), v.end());

fill(arr, arr + MAXN, 0);
fill((ll*)arr, (ll*)(arr + MAXN), 0);
fill(v.begin(), v.end(), 0);

copy(arr, arr + MAXN, v.begin());
copy(v.begin(), v.end(), arr);

ll arr[MAXN];
ll* ptr = find(arr, arr + MAXN, 123);
if ( ptr != arr + MAXN ) {
    // *ptr
}

vector<ll> v;
vector<ll>::iterator it = find(v.begin(), v.end(), 123);
if ( it != v.end() ) {
    // *it
}

bool find_if_comp(pair<ll,ll> pll) {
    return pll.first == 0;
}
vector<pair<ll,ll> > v;
vector<pair<ll,ll> >::iterator it = find_if(v.begin(), v.end(), find_if_comp);
if ( it != v.end() ) {
    // it->first, it->second
}

vector

v.push_back(0);
v.size();
v.clear();

よくあるアルゴリズム

二分探索

pair の配列と lower_bound の組み合わせが有用

bool pls_comp(pair<ll,string> a, pair<ll,string> b) {
    return a.first < b.first; // 0, 1, 2, ...
    // return strcmp(a.second.c_str(), b.second.c_str()) < 0; // a, b, c, ...
}

vector<pair<ll,string> > v;
v.push_back(make_pair(0, "value"));
sort(v.begin(), v.end(), pls_comp);
binary_search(v.begin(), v.end(), make_pair(3, ""), pls_comp); // 見つかれば true
// 1, 2, 3(=lb), 3, 4(=ub), 5
lower_bound(v.begin(), v.end(), make_pair(3, ""), pls_comp)->second;
upper_bound(v.begin(), v.end(), make_pair(3, ""), pls_comp)->second;

集合

要素数 1 の集合を init で MAXN 個生成して same と unite で処理

int par[MAXN];
int rnk[MAXN];
void init(int n) { for(int i = 0; i < n; ++i) { par[i] = i; rnk[i] = 0; }}
int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return;
    if(rnk[x] < rnk[y]) par[x] = y; else { par[y] = x; if(rnk[x] == rnk[y]) ++rnk[x]; }}

グラフ

隣接リスト (重みなし)

vector<ll> G[MAXN];
G[from].push_back(to);
for(ll i = 0; i < V; ++i) {
    for(ll j = 0; j < (ll)G[i].size(); ++j) {
        // from `i` to `G[i][j]`
    }
}

隣接リスト (重みつき)

vector<pair<ll,ll> > G[MAXN];
G[from].push_back(pair<ll,ll>(to, cost));
for(ll i = 0; i < V; ++i) {
    for(ll j = 0; j < (ll)G[i].size(); ++j) {
        // from `i` to `G[i][j].first` cost `G[i][j].second`
    }
}

隣接行列

ll G[MAXN][MAXN];
fill((ll*)G, (ll*)(G + MAXN), INF);
G[from][to] = 1; // 重みなし
G[from][to] = cost; // 重みつき

幾何

グリッド上の経路探索

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int dfs(int x, int y) {
    // (x, y) に関する処理
    // ...
    for(int i = 0; i < 4; ++i) {
        dfs(x + dx[i], y + dy[i]);
    }
}

内積、外積、交差判定、距離

typedef complex<double> P;
#define X real()
#define Y imag()

P p1(0, 0);
abs(p1 - p2); // 線分の長さ

// 内積 |a||b|cos(theta)
double dot(P a, P b) {
    return a.X * b.X + a.Y * b.Y;
}
dot(p2 - p1, p3 - p1);

// 外積 (平行四辺形の面積) |a||b|sin(theta)
double cross(P a, P b) {
    return a.X * b.Y - a.Y * b.X;
}

// 線分と線分の交差判定 (線分の長さが 0 の場合 false)
//      b1
//       |
// a1---------a2
//       |
//       b2
bool intersected(P a1, P a2, P b1, P b2) {
    if(abs(cross(a2-a1, b2-b1)) < EPS) return false;
    return (cross(a2-a1, b1-a1)*cross(a2-a1, b2-a1) < EPS) && (cross(b2-b1, a1-b1)*cross(b2-b1, a2-b1) < EPS);
}

// 線分と点の距離
// a---------b
// 
//    c
double distance(P a, P b, P c) {
    if ( dot(b-a, c-a) < EPS ) return abs(c-a);
    if ( dot(a-b, c-b) < EPS ) return abs(c-b);
    return abs(cross(b-a, c-a)) / abs(b-a);
}

順列

std::next_permutation

vector<string> v;
v.push_back("xxx");
v.push_back("yyy");
v.push_back("zzz");
sort(v.begin(), v.end()); // 必要
do {
    // v が破壊的に書き換えられる
    // "xxx", "yyy", "zzz"
    // "xxx", "zzz", "yyy"
    // ...
} while(next_permutation(v.begin(), v.end()));

おおまかな制限

• 1 秒間で処理できるループ数は 10^7 まで (シンプルな処理であれば 10^8 まで可)
• 再帰 10^5 程度までならばスタック領域は不足しない
• 最大値、最小値の感覚↓