最終更新日：2019/12/15

はじめに

私は競技プログラミング（以下、競プロ）を少しやっています。この記事では、競プロで学んだことや参考にしたWebサイトなどまとめていこうと思っています。この記事が、私と同じように「競プロを始めてみたけど分からないことが多いなー」と思っている人の役に立てれば嬉しいです。

ちなみに、使用する言語はC++です。

はじめに
競プロを始めるにあたって
問題を解く前の準備
よく使うものたち
知っておくと便利なものたち
たまに使うものたち
おわりに
今日から始める競プロ日記のまとめページ
追記記録

競プロを始めるにあたって

競プロとは何か

与えれた問題を解くプログラムを、より速く正確に記述することを競うプログラミングコンテストです。競技プログラミングを略して「競プロ」と呼ぶことがあります。競技プログラミング - Wikipedia

コンテストやオンラインジャッジのWebサイト

AtCoder

毎週コンテストを開催しています。問題文は日本語と英語があります。 atcoder.jp

Codeforces

世界一参加者が多いコンテストです。問題文は英語とロシア語があります。 codeforces.com w.atwiki.jp

AIZU ONLINE JUDGE

会津大学が実施しているオンラインジャッジシステムです。勉強に最適です。 judge.u-aizu.ac.jp

yukicoder

定期的にコンテストが開催されています。誰でも問題を作ることができます。 yukicoder.me

競プロの本

ざっと読むだけでも競プロに必要となるアルゴリズムを知ることができて良いです。

螺旋本（AOJ本）。
蟻本。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆,Ozy(協力),秋葉拓哉(協力)
出版社/メーカー: マイナビ
発売日: 2015/01/30
メディア: 単行本（ソフトカバー）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

作者:秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ出版
発売日: 2012/01/28
メディア: Kindle版

AtCoderにおいて役に立つWebサイト

有志の方が作り、管理してくれているサービスです。ありがたいです。自分がこれまでどの問題を解いたのかが、簡単に確認できます。これによって自分がスキルアップするために、どの問題を解けばいいのかが分かります。

勉強になる記事（主にけんちょんさんの記事）

けんちょんさんという方が書かれている記事を読んでいくと、競プロで必要となるアルゴリズムはだいたい知ることができます。解説も分かりやすいです。

AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～ - Qiita

蟻本の内容をAtCoderの問題に対応させた記事。すごいです。

ライブラリのまとめ

けんちょんさんのその他の記事

他にもためになる記事

問題を解く前の準備

標準ライブラリをインクルード

gccだと標準ライブラリを一括で読み込むことができます。

#include <bits/stdc++.h>

C++の標準ライブラリを一行で一括でインクルードする - Qiita

std名前空間

標準ライブラリはstdという名前空間に定義されているので、以下を書いておけば楽ができます。

using namespace std;

namespaceの賢い使い方 - Qiita

最低限のプログラム

コンテストを始まる前に、とりあえずこれだけ書いておけば何とかなると思います。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    return 0;
}

時間制限と計算量の話

競プロの問題には必ず計算時間に制限が設けられています。提出したプログラムの計算時間がその制限を超えてしまうと不正解扱いになってしまいます。そのため、より計算量が少ないアルゴリズムを実装する必要があります。その話が以下の記事に分かりやすくまとまっています。

計算量オーダーの求め方を総整理！〜どこから log が出て来るか〜 - Qiita

標準ライブラリの使い方

vectorやlist、map、set、priority_queueなど、競プロでよく使われるものが、この記事に簡潔にまとめられています。競プロ向けSTL標準ライブラリ - Qiita

1000000007で割った余りを求める（modをとる）

競プロでは、「解が非常に大きくなる場合があるので、1000000007で割った余りを求めてください。」と言われる問題がまれに良く出ます。その話が以下の記事に分かりやすくまとまっています。

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - Qiita

桁数を指定して出力

「絶対誤差または相対誤差が10のマイナス9乗以下の精度で解を出力してください」というような問題がまれに良く出ます。この場合、小数点以下の桁数を指定して出力する必要があります。

C言語の標準入出力を使う場合はprintfを使います（こっちのほうが簡単です）。

printf("%.10lf\n", ans); //10桁出力

C++のiostreamを使う場合はsetprecisionを使います。

cout << setprecision(10) << ans << endl; //10桁出力

C++で浮動小数点型を扱うときのメモ(精度比較、精度設定) - Qiita 【C++】小数点の桁数を指定する方法と注意点【cout／iostream】 | MaryCore 小数点以下n桁を表示する - minus9d's diary

よく使うものたち

ソート

標準ライブラリのsortを使えば計算量O(NlogN)でソートできるようです。

// ソート対象の数列を準備
vector<int> v = {4, 2, 5, 1, 3};

// 昇順ソート
sort(v.begin(), v.end()); // 1,2,3,4,5

// 降順ソート
sort(v.gegin(), v.end(), greater<int>()); // 5,4,3,2,1

cpprefjp.github.io

pairを用いたソート

pairは二つの値をセットにしてデータを扱うことができます。 pairはこんな感じで使います。

pair p = make_pair(1, 2);
cout << p.first << endl; //1
cout << p.second << endl; //2

sortではpairの配列などもソートできます。たとえば以下のような配列をソートするとします。

ソート前。

index : pair
0 : 1 2
1 : 3 5
2 : 2 4
3 : 1 5
4 : 3 3

pairのソートでは、まずfirstの値を元にソートが行われ、 firstの値が同じ場合はsecondの値で順番が決まります。

vector<pair<int,int>> vp(5);
vp[0] = make_pair(1,2);
vp[1] = make_pair(3,5);
vp[2] = make_pair(2,4);
vp[3] = make_pair(1,5);
vp[4] = make_pair(3,3);
sort(vp.begin(), vp.end()); //昇順にソート

ソート後の出力は以下のようになります。

index : pair
0 : 1 2
3 : 1 5
2 : 2 4
4 : 3 3
1 : 3 5

tupleを用いたソート

pairは二つの値をセットにしましたが、 tupleでは二つ以上の値をセットにして扱うことができます。また、pairと同じようにソートもできます。

tupleの使い方はこんな感じです。

tuple<int, int, string> t = make_tuple(3, 2, "abc");
cout << get<0>(t) << endl; // 3
cout << get<1>(t) << endl; // 2
cout << get<2>(t) << endl; // abc

ソートはpairのときと同じように使えます。

vector<tuple<int, int, string>> vt;
vt.push_back(make_tuple(3, 2, "abc"));
vt.push_back(make_tuple(1, 1, "abc"));
vt.push_back(make_tuple(2, 1, "bbcc"));
vt.push_back(make_tuple(1, 1, "a"));
vt.push_back(make_tuple(1, 2, "ccccc"));
sort(vt.begin(), vt.end()); //昇順にソート

出力はこうなります。

1 1 a
1 1 abc
1 2 ccccc
2 1 bbcc
3 2 abc

二次元Vectorの初期化

二次元にしたVectorを初期化したい場合があります。これはこのように書くことができます。

vector<vector<int>> v(N, vector<int>(N, value));

qiita.com

全通りの探索（ビットシフトを使ったやつ）

ABC-080のC問題などで使いました。

2のN乗通りをすべて探索することができます。コードを見ただけではどうなっているのか分かりづらいので、実際に実行してどういう出力をするのか確認するといいと思います。

ちなみに、'&'はビット演算子の一つで二つのビットが両方とも1だった場合のみ1を返します。

for(int i = 0; i < (1<<N); i++) // 0 <= i < 2のN乗
{
    for(int j = 0; j < N; j++)
    {
        if(i>>j&1) // あるビットが1(true)か0(false)かを調べている
        {
            // jに対応しているビットが１だった場合ここの処理が実行
        }
    }
}

qiita.com www9.plala.or.jp

約数の列挙

以下に示す記事を参考に約数を列挙してみました。

for(int i = 1; i*i <= N; i++)
{
    if(N % i == 0)
    {
        v.push_back(i);
        if(i*i != N) v.push_back(N/i);
    }
}

参考記事。 ei1333.github.io

素数判定

ある値が素数かどうか判定したいとき。

yyatsuo.com

modをとる二項係数の計算

ABC145のD問題でn+mCnの計算を行うときに、どうmodをとればいいのか分かりませんでした。

これは知っておかないと厳しそう。

drken1215.hatenablog.com

知っておくと便利なものたち

切り上げ

小数点を切り上げたいときがたまにあります（結構ある）。例えば7 / 3 をしたときに答えは3になり、 8 / 2の場合はそのまま4になってほしいとき。

A/Bの結果において小数点を切り上げたいとき、

( A + B - 1 ) / B

で実現できます。

四捨五入する

3.4は3に、3.5は4になります。

double a = round(3.4);
double b = round(3.5);

四捨五入する | Programming Place Plus C++編逆引き

順列（next_permutation）

C++ では簡単に順列を求められます。

vector<int> v = {1, 2, 3}; //昇順にする
do
{
    // 処理
} while(next_permutation(v.begin(), v.end()));

二進数へ変換

1024(10)を32桁の二進数の文字列に変換してみます。

stringstream ss;
ss << bitset<32>(1024);
string s = ss.str();

C++ 数値を 2進数 8進数 10進数 16進数文字列に変換する方法 | MaryCore

最大公約数と最小公倍数

最大公約数（GCD）の求め方はこうです。

int gcd(int a, int b) # a > b
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

最小公倍数（LCM）の求め方はこうです。

a * b / GCD

しかし、a, bが大きい値の場合、a * bをするとオーバーフローする可能性があります。そのため以下のように実装します。

a / GCD * b

コードは以下のように書きます。

int main()
{
    int A, B;
    cin >> A >> B;    # A > B
    int G = gcd(A, B);    # 最大公約数
    int L = A / G * B;    # 最小公倍数
}

qiita.com

vectorの最大値と最小値

イテレータ = max_element(v.begin(), v.end());
イテレータ = min_element(v.begin(), v.end());

ちなみに*を付ければイテレータが指す値を取得できます。

qiita.com

vectorの合計値

第三引数でその型でのゼロを指定します。

long long sum = accumulate(v.begin(), v.end(), 0LL);

cpprefjp.github.io

たまに使うものたち

処理にかかった時間を知りたい

処理の前後で時刻を取得します。

clock_t start = clock();
//処理
clock_t end = clock();

最後に処理にかかった時間を計算します。

double t = (double)(end - start) / CLOCKS_PER_SEC * 1000.0;

C++ 高速化処理時間の計測

0埋めして出力

変数Xを桁数を固定して出力したいときがあります。

例えばX=12のとき、6桁の値000012として出力したいとき。 X=256になれば出力は000256になり、 X=12345だったら012345になるようなとき。

cout << setfill('0') << right << setw(6) << 12; //000012
cout << setfill('0') << left  << setw(6) << 12; //120000

【C++】左詰め／右詰め／ゼロ埋めの方法と注意点【cout／iostream 文字揃え】 | MaryCore

パネルの回転

1 2 3
4 5 6
7 8 9

これを右に90度回転させたいとき。

7 4 1
8 5 2
9 6 3

こんな感じにやるとできます。

// サイズ
int N = 3;

// 回転前
vector<vector<int>> v(N, vector<int>(N));
v[0][0] = 1; v[0][1] = 2; v[0][2] = 3;
v[1][0] = 4; v[1][1] = 5; v[1][2] = 6;
v[2][0] = 7; v[2][1] = 8; v[2][2] = 9;

// 回転後
vector<vector<int>> nv(N, vector<int>(N));

// 回転
for(int i = 0; i < N; i++)
{
    for(int j = 0; j < N; j++)
    {
        nv[i][j] = v[N-1-j][i];
    }
}