競技プログラミングに関連するメモ

各種関連サイト

典型的な問題パターン

TODO

基本的なデータ構造の操作

スタック

see: queue - cpprefjp C++日本語リファレンス

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<string> s;
    s.push("a");
    s.push("b");
    cout << s.top() << endl; //=> b
    s.pop();
    cout << s.top() << endl; //=> a

    return 0;
}

キュー

see: queue - cpprefjp C++日本語リファレンス

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    queue<string> q;
    q.push("a");
    q.push("b");
    cout << q.front() << endl; //=> a
    q.pop();
    cout << q.front() << endl; //=> b

    return 0;
}

優先度付きキュー

see: queue - cpprefjp C++日本語リファレンス

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    // 大きな整数を pop 側に配置するするキュー
    priority_queue<int> q;
    q.push(4);               //=>  push -[4]-> pop
    q.push(2);               //=>  push -[2, 4]-> pop
    q.push(5);               //=>  push -[2, 4, 5] -> pop
    cout << q.top() << endl; //=> 5
    q.pop();
    cout << q.top() << endl; //=> 4
    q.pop();
    cout << q.top() << endl; //=> 2
    q.pop();

    return 0;
}

整数の場合、デフォルトは大きい順にキューイングされるが、小さい順にキューイングしたい場合は下記のような記述となる

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    // 大きな整数を pop 側に配置するするキュー
    priority_queue<int, vector<int>, greater<int>> q;
    q.push(4);               //=>  push -[4]-> pop
    q.push(2);               //=>  push -[4, 2]-> pop
    q.push(5);               //=>  push -[5, 4, 2] -> pop
    cout << q.top() << endl; //=> 2
    q.pop();
    cout << q.top() << endl; //=> 4
    q.pop();
    cout << q.top() << endl; //=> 5
    q.pop();

    return 0;
}

連想配列（マップ）

see: map - cpprefjp C++日本語リファレンス

#include <iostream>
#include <map>

using namespace std;

int main()
{
    map<string, int> m;
    m["taro"] = 100;
    m["jiro"] = 200;

    cout << m["jiro"] << endl; //=> 200
    cout << m["taro"] << endl; //=> 100

    return 0;
}

対（ペア）

see: pair - cpprefjp C++日本語リファレンス

#include <iostream>
#include <utility>

using namespace std;

int main()
{
    pair<int, int> p1 = {1, 2};
    pair<int, int> p2 = {3, 4};
    pair<int, int> p3 = {1, 2};

    cout << "x: " << p1.first << ", y: " << p1.second << endl;
    //=> x: 1, y: 2
    p1.swap(p2);
    cout << "x: " << p1.first << ", y: " << p1.second << endl;
    //=> x: 3, y: 4

    cout << "p1 == p2: " << (p1 == p2) << endl;
    //=> p1 == p2: 0
    cout << "p2 == p3: " << (p2 == p3) << endl;
    //=> p2 == p3: 1
    return 0;
}

可変長配列（ベクタ）

see: vector - cpprefjp C++日本語リファレンス

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> as = {1, 2, 3, 4};
    as.push_back(5);            // O(1) => 1, 2, 3, 4, 5
    as.pop_back();              // O(1) => 1, 2, 3, 4
    as.erase(++as.begin());     // O(n) => 1, 3, 4
    as.front();                 // O(1) => 1
    as.back();                  // O(1) => 4
    as.at(1);                   // O(1) => 2
    as.insert(++as.begin(), 2); // O(n) => 1, 2, 3, 4
    as.clear();                 // O(n) => []
    return 0;
}

両端キュー（Double Ended Queue）

see: deque - cpprefjp C++日本語リファレンス

vector は先頭への挿入・削除が O(n) だが両端キューの構造をとることにより先頭・末尾双方への挿入・削除を O(1) にできる

#include <deque>

using namespace std;

int main()
{
    deque<int> as = {1, 2, 3, 4};
    as.push_back(5);  // O(1) => 1, 2, 3, 4, 5
    as.pop_back();    // O(1) => 1, 2, 3, 4
    as.push_front(0); // O(1) => 0, 1, 2, 3, 4
    as.pop_front();   // O(1) => 1, 2, 3, 4
    return 0;
}

基本的なアルゴリズム

二分探索

N 個の要素を持つ整列済み配列 $A_{i}$ のなかから $X$ が何番目にあるか調べたい状況で全探索は O(N) の計算量が必要。整列済みという特性を活かし、配列の真ん中の値が確認したい値より大きいか小さいかをチェックし、それぞれ値があるエリアに対してこれを繰り返す 二分探索(binary search) を用いると $O(log N)$ で計算できる。

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int pos;
    const int len = 9;
    int a[len] = {10, 20, 30, 40, 50, 60, 70, 80, 90};

    //=> lower_bound は 80 以上の値の iterator を返却する
    pos = lower_bound(a, a + len - 1, 80) - a;
    cout << pos << endl; //=> 7

    //=> lower_bound は 80 より大きな値の iterator を返却する
    pos = upper_bound(a, a + len - 1, 80) - a;
    cout << pos << endl; //=> 8
    return 0;
}

数学に関する問題

素数を判定する

以下のようなフローで素数判定可能

n が素数でないと仮定すれば、整数 a, b (a <= b)を用いて n = a x b となる a, b が存在する。n が素数でないのであれば、2 から a がとりうる最大値: b までの間に n を割り切れる整数が存在する。a がとりうる最大値は n = b^2 => b = sqrt(n) ということになる。

最大公約数を求める

# 疑似コード:
int gcd(int a, int b) {
  return (a == 0 || b == 0) ? max(a, b) : gcd(max(A, B) % min(A, B), min(A, B))
}

割り算の余りを計算する

以下のような分配法則が成り立つのでこれを利用するケースが多い