モーダルを閉じる工作HardwareHub ロゴ画像

工作HardwareHubは、ロボット工作や電子工作に関する情報やモノが行き交うコミュニティサイトです。さらに詳しく

利用規約プライバシーポリシー に同意したうえでログインしてください。

工作HardwareHub ロゴ画像 (Laptop端末利用時)
工作HardwareHub ロゴ画像 (Mobile端末利用時)
目次目次を開く/閉じる

競技プログラミングの基本処理チートシート (C++)

モーダルを閉じる

ステッカーを選択してください

モーダルを閉じる

お支払い内容をご確認ください

購入商品
」ステッカーの表示権
メッセージ
料金
(税込)
決済方法
GooglePayマーク
決済プラットフォーム
確認事項

利用規約をご確認のうえお支払いください

※カード情報はGoogleアカウント内に保存されます。本サイトやStripeには保存されません

※記事の執筆者は購入者のユーザー名を知ることができます

※購入後のキャンセルはできません

作成日作成日
2017/12/17
最終更新最終更新
2021/10/04
記事区分記事区分
一般公開

目次

    アカウント プロフィール画像 (サイドバー)

    情報系の学生

    0
    ステッカーを贈るとは?

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

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

    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 程度までならばスタック領域は不足しない
    • 最大値、最小値の感覚↓
    最大値 最小値
    int (32) 2147483647 -2147483648
    long long (64) 9223372036854775807 -9223372036854775808
    double (64) 10^(-308) から 10^308 (有効桁数 15) -10^(-308) から -10^308 (有効桁数 15)
    0
    詳細設定を開く/閉じる
    アカウント プロフィール画像 (本文下)

    情報系の学生

    記事の執筆者にステッカーを贈る

    有益な情報に対するお礼として、またはコメント欄における質問への返答に対するお礼として、 記事の読者は、執筆者に有料のステッカーを贈ることができます。

    さらに詳しく →
    ステッカーを贈る コンセプト画像

    Feedbacks

    Feedbacks コンセプト画像

      ログインするとコメントを投稿できます。

      関連記事

      • ダウンキャスト (C++をもう一度)
        実行時型情報 RTTI #include <iostream> #include <typeinfo> using namespace std; class MyClass { public: virtual ~MyClass() {} // typeid で正しい RTTI // (RunTime Type Information; 実行時型情報) ...
      • 構造体と列挙体 (C++をもう一度)
        構造体 #include <iostream> using namespace std; struct MyStruct { char charval; int intval; }; void Show(MyStruct* obj) { cout << obj->intval << endl; } int main() { ...
      • Valgrind による C/C++ メモリリーク検出
        JVM メモリリークでは JDK の jstat や jmap で原因を調査できます。C/C++ では valgrind の Memcheck ツールが利用できます。valgrind には複数のツールが含まれており既定のツールが Memcheck です。他のツールを利用する場合は --tool オプションで指定します。 [簡単な利用例](h
        あおいねずみあおいねずみ2/27/2022に更新
        いいねアイコン画像0
      • クラスの基本/初期化 (C++をもう一度)
        構造体のように初期化する (非推奨) #include <iostream> using namespace std; const int MAX_STR = 16; class MyClass { public: int m_integer; char m_str[MAX_STR + 1]; void Show(); }; void MyClass::Show...
      • Union-Find サンプル
        『プログラミングコンテストでのデータ構造』で紹介されている Union-Find 木で集合を表現すると、以下のクエリを高速に実行できます。集合一つが一つの木となるため、複数の集合がある場合は全体として森になります。 ある要素 a_i と a_j が同じ集合に属しているかどうかの判定 二つの集合を一つの集合にまとめる サンプル [POJ 1182](https://translat