C++を用いてプログラミングコンテストの問題を解く際に、覚えておきたい点を勉強がてらまとめてみます。
実行時間の見積もり
算出方法
ランダウのO-記法による計算量内の変数に、最大の場合の数値を代入する。
目安
実行時間制限を1[s]とする。
| 実行時間($10^n$形式) | 実行時間(一般形式) | 実行時間制限に間に合うかどうか |
|---|---|---|
| 〜$O\left(10^6\right)$ | 〜$O(100$万$)$ | 余裕で間に合う |
| 〜$O\left(10^7\right)$ | 〜$O(1,000$万$)$ | おそらく間に合う |
| 〜$O\left(10^8\right)$ | 〜$O(1$億$)$ | 非常にシンプルな処理でない限り、間に合わない |
型の範囲
範囲を桁数で示す(正確な範囲に関しては、参考文献に記載されているサイトを参照)。
| 型名 | 範囲($10^n$形式) |
|---|---|
(long) int |
$-10^9$〜$10^9$ |
long long (int) |
$-10^{18}$〜$10^{18}$ |
ヘッダーファイル
bits/stdc++.hをインクルードすることで、全ての関数が使用可能となる。
名前空間
C++には名前空間があり、基本的に標準ライブラリはstd名前空間に含まれている。
そのため、プログラミングコンテストにおいては、(std::の)入力の手間を省くために、using namespace std;を入れることが多い。
※この方法は、一般的なプログラミングにおいては推奨されていないので注意が必要。
CストリームとC++ストリーム
C++では、Cストリーム(scanfやprintf)とC++ストリーム(std::cinやstd::cout)の両方を使用することができる(混在させて使用することも可能)。
使い分け
両ストリームには、以下のような特徴がある。
- C++ストリームは、フォーマットを指定することができない。
- 一般に、C++ストリームはCストリームよりも動作速度が遅い。
以上を踏まえた上で、どちらのストリームに属する関数を使うかを判断するときには、以下の基準に従うと良い。
| 条件 | ストリーム |
|---|---|
| フォーマット指定子を使用したい または 最大呼び出し回数が10万回以上 |
Cストリーム |
| それ以外 | C++ストリーム |
同期や掃き出しの無効化
両ストリームでは、次のような処理が行われている。
- 両ストリームでは同期が行われている。
-
std::cinは実行される度に、std::coutの掃き出しを行っている。
しかし、これらの動作が動作速度を落としてしまう場合もあるため、以下のような命令を加えると良い。
| 条件 | 命令 |
|---|---|
| どちらかのストリームしか使わない | std::ios::sync_with_stdio(false); |
std::cinの実行時に、std::coutの掃き出しを行う必要がない |
std::cin.tie(0); |
STL(標準テンプレートライブラリ)
一般的なクラステンプレートとアルゴリズムの集合である。
主要なデータ構造とメソッド
| データ構造 | 先頭に挿入 | 先頭を見る | 先頭を削除 | 末尾に挿入 | 末尾を見る | 末尾を削除 | 挿入 |
|---|---|---|---|---|---|---|---|
std::list |
push_front() |
front() |
pop_front() |
push_back() |
back() |
pop_back() |
|
std::deque |
push_front() |
front() |
pop_front() |
push_back() |
back() |
pop_back() |
|
std::vector |
front() |
push_back() |
back() |
pop_back() |
|||
std::queue |
front() |
pop() |
push() |
back() |
|||
std::stack |
push() |
top() |
pop() |
||||
std::priority_queue |
top() |
pop() |
push() |
優先順位付きキュー
std::priority_queueは、データを一定の規則に従って、自動的に並び替えるデータ構造である。
宣言方法
Tを型、nを変数名とする。
| 並び順 | 宣言 |
|---|---|
| 降順 | std::priority_queue<T> n |
| 昇順 | std::priority_queue<T,vector<T>,greater<T>> n |
二分探索
二分探索を行う関数として、std::lower_bound()とstd::upper_bound()が用意されている。
配列形式
aを昇順にソートされた配列、nをaの要素数とする。
| 関数 | 返り値 |
|---|---|
std::lower_bound(a,a+n,k) |
aの中で、k以上の値が初めて現れる位置へのポインタ |
std::upper_bound(a,a+n,k) |
aの中で、k超の値が初めて現れる位置へのポインタ |
STL形式
aを昇順にソートされたSTLのデータ構造とする。
| 関数 | 返り値 |
|---|---|
std::lower_bound(a.begin(),a.end(),k) |
aの中で、k以上の値が初めて現れる位置へのポインタ |
std::upper_bound(a.begin(),a.end(),k) |
aの中で、k超の値が初めて現れる位置へのポインタ |
ある列における、ある数の個数
二分探索を用いて、ある列aに含まれる数kの個数を求める際には、次のように記述する。
std::lower_bound(a,a+n,k)-std::upper_bound(a,a+n,k)
std::lower_bound(a.begin(),a.end(),k)-std::upper_bound(a.begin(),a.end(),k)
Union-Find木
グループを管理する、木構造のデータ構造である。
操作
初期化
使用する要素数分ノードを用意する。
この際、辺はない(つまり、どのノードも親は自分となる)。
併合
2つのUnion-Find木があったときに、木の高さ(rank)が小さい方の根から大きい方の根に辺を張る(すなわち、木の高さが小さい方の根の親を大きい方の根にする)。
判定
調べたいノードを起点として、Union-Find木を上向きに辿って行き(すなわち、ノードの親を辿って行き)、木の根を調べる。2つのノードについて、属している木の根が一致するならば、2つのノードは同じグループに属していると言える。
縮約
判定を行う際に、辿った各ノードから木の根に辺を張り直す(すなわち、各ノードの親を木の根にする)ことで、次回からの判定を効率化させることができる。
テンプレート
//Union-Find木で扱うデータの最大要素数
#define MAX 100
//xとyが同じグループに含まれているか
#define same(x,y) (find_root(x)==find_root(y))
//Union-Find木の各ノードの親
int parent[MAX];
//各グループのUnion-Find木の高さ
//『rank』という変数名にすると、名前の衝突が起きるため注意
int myrank[MAX];
//要素数nとして、Union-Find木の初期化を行う
//myrankは、グローバル変数として宣言した際に0で初期化されているため、初期化処理を省いている
void init(int n)
{
for (int i = 0; i < n; ++i) {
parent[i]=i;
}
}
//ノードxが含まれるグループのUnion-Find木の根を見つける
int find_root(int x)
{
//辺の縮約を行う
if (parent[x]!=x){
parent[x]= find_root(parent[x]);
}
return parent[x];
}
//ノードxが含まれるグループとノードyが含まれるグループの併合を行う
void unite(int x,int y)
{
x= find_root(x);
y= find_root(y);
if(x!=y){
if(myrank[x] < myrank[y]){
parent[x]=y;
} else{
parent[y]=x;
if(myrank[x] == myrank[y]){
myrank[x]++;
}
}
}
}