概要

限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 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();

文字列