競技プログラミング勉強用リスト

世の中にはよくまとまっている記事がたくさんあるので、自分用リンク集＋メモ書き。

STLチートシート

迷ったら結局リファレンスを見るのが一番速い説

vector

#include <vector>
using namespace std;
// a = {0, 0, 0, 0, 0}
vector<int> a(5, 0);
// a = {1, 1, 1}
a.assign(3, 1);
// a = {1, 1, 1, 2}
a.push_back(2);
// a = {1, 3, 1, 1, 2} O(N)!!!!!!
a.insert(a.begin() + 1, 3);
// 3
a[1];
// 1
a.front();
// 2
a.back();
// 5
a.size();
  • insertはO(N)なので、使わない

remove duplications

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

priority_queue

// declaration, default comparer is less: top is the largest element
priority_queue<pair<int, int>> que;
auto p = make_pair(1, 2);
que.push(p);
que.emplace(2, 1);
// t = {2, 1}
auto t = que.top();
que.pop();
// specify comparer to get smallest element
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que2;
que2.emplace(1, 2);
que2.emplace(2, 1);
// u = {1, 2}
cout << u.first << " " << u.second << endl;
// choose the element which has smallest pair.second
auto comp = [](pair<int, int> l, pair<int, int> r) { return l.second > r.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> que3(comp);
que3.emplace(1, 3);
que3.emplace(3, 2);
que3.emplace(2, 1);
// que3: top = {2, 1} < {3, 2} < {1, 3}
  • テンプレート引数に与える比較関数でもっとも優先度が低い要素がtopになるので注意
  • 自作クラスを要素にする場合、比較演算子を作成するか、ラムダ式で比較関数を作成する
    • 普通はpairかtupleを使ってしまうのが便利

string

#include<string>
// s = "AAAAAAAAAA"
string t(10, 'A');
// s = "ABC"
string s("ABC");
// 'B'
s[1];
// s = "ABCD"
s += "D";
// erase i-th element (0-indexed)
s.erase(s.begin()+i);
// erase from i to i+n-1
s.erase(i, n);
// erase elements in [begin, end)
s.erase(s.begin(), str.end());
// initPos is the position we start to look it up
int pos = s.find("E", initPos);
if (pos == string::npos) cout << "not found" << endl;
// get substring from start to start+num-1
s.substr(start, num);
// cast to int
s = "123";
int a = stoi(s);
// cast to long long
long long b = stoll(s);
// cast numbers to string
string u = to_string(a);
  • []演算子で取り出した1文字はcharなので、char literal ('0'など)と比較する

セグメント木

参考

プログラミングコンテストチャレンジブック [第2版] p.153-

セグメント木について - beet's soil

遅延評価セグメント木について - beet's soil

初心者の初心者による初心者のための典型segment tree - DEGwerの競技プログラミングと時々数学

セグメント木をソラで書きたいあなたに - hogecoder

遅延評価セグメント木をソラで書きたいあなたに - hogecoder

セグメント木

  • どういう写像が合成されていくか意識するのが大切

RMQセグメント木

#include <vector>
#include <climits>
using namespace std;
const int INF = INT_MAX;

// 0-indexed RMQ segment tree
class SegTree {
  private:
    int n;
    vector<int> dat;

  public:
    SegTree(int n_) {
        n = 1;
        while (n < n_)
            n *= 2;
        dat.assign(2 * n - 1, INF);
    }
    void update(int k, int a) {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)
            return INF;
        if (a <= l && r <= b)
            return dat[k];
        else {
            int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
            int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
    // get min in [a, b)
    int query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

競プロ用出入力メモ

参考

kyoupro_on_cpp.md · GitHub

c++ - Significance of ios_base::sync_with_stdio(false); cin.tie(NULL); - Stack Overflow

C++ の iostream フォーマット指定早見表

iostream

#include <iomanip>
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    cout << N << "\n";

    double x;
    cin >> x;
    cout << fixed << setprecision(10) << x << "\n";

    string s;
    cin >> s;
    cout << s << endl;
}
  • 遅いが、出入力の行数が少ない場合には十分
  • 型を自動判別してくれるため楽
  • 小数点以下の桁数を指定する場合、iomanipをincludeしてfixed << setprecision()
  • 速度を気にする場合
    • endlではなく改行文字\nの方が速い
    • mainはじめの二行を追加すると高速化できる場合がある
      • sync_with_stdio(false)を使用した場合stdioを使用してはいけない
      • cin.tie(0)はcinとcoutの連携を切ってしまい、出力が出る前に次の入力が行われる危険がある。競プロの形式では問題ないはず