読者です 読者をやめる 読者になる 読者になる

競技プログラミングで見かけた実装(C++)

Competitive Advent Calenderにもテンプレ考察ということでありましたが、今まで競プロをやってきて面白いと思った実装、自分が実際に使っている実装を書いていこうと思います。

#define

定番。どの程度まで使うかはその人次第。

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eps 1e-15

といいながら自分は基本はこれは使いません。push_backとかはエディタが補完してくれるので楽なんです。
rep系は発展形も多くて便利です。
因みに定数は#define派とconst派に別れるようです。自分はconst派なんですが。

typedef

型名長い→省略。

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef tuple<int,int,int> ti3;

自分はダイクストラやDPの時に長めの型の変数をよく使うので先程のと合わせて便利です。priority_queueをpqと省略してもいいのかもしれませんが、自分は変数名としてpqを用いているのでそれはしていません。

#include <bits/stdc++.h>

気になった人は
libstdc++: stdc++.h Source File
へ。内容通り1行で全部インクルード出来ます。結構コンパイルが重くなるので注意。

地味に便利なやつ

const int inf=1<<30;
const int INF=INT_MAX;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int d[]={0,1,0,-1,0}//int nx=x+d[i],ny=y+d[i+1]と使用。

INT_MAXは普通にそのまま使っています。というより書いたのはINT_MAXなんでみんな使わないんだろう…と思ったからです。

foreach

C++11以降の実装です。

vector<int> a(N,12345);
for(int i=0;i<a.size();i++)    cout<<a[i]<<endl;

vector<int> a(N);
for(int i:a)    cout<<i<<endl;

と書けます。自分も最近知ったのですが、かなり便利で、わざわざiteratorを用いていたところを

map<int,int> a;
//中身を適当に入れる
for(auto i:a)    cout<<i.first<<" "<<i.second<<endl;

とループが扱えます。


余談ですが、C++11でChronoという時間計測のプログラムが入っているようです。今までtimeでは1秒単位、clockはCPU依存でまともに計測が出来なかったので助かった…
というついでにかなり雑にC++11の機能を見てみたのですが、beginとendはメンバ関数よりbegin(a)と使うことが推奨されているらしいです…
iteratorのnextとprevも使ったことは無いけれどもランダムイテレータで無いため困ったことは何度もあるので便利そう。