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

いろんな人のテンプレートを観察

この記事はCompetitive Programming Advent Calender(その2) 23日目の記事です。

はじめに

競技プログラミングでいろんな人のコードを読んでみると、前半部分には人によって色々なマクロや関数が定義されていたりいなかったりします。(参考: Quora)

この部分にはその人が快適にコーディングするための工夫が見られて面白いので、今回いろんな人のテンプレートを眺めてみることにしました。

実際に見たテンプレートはここ(Codeforces)ここ(KUPC)にまとめました。時間の都合上、それぞれ約50人、約30人しか見ていません。しかも途中で疲れてコメントがかなり雑です。すいません。

これらを見てどのような機能がテンプレートにあったか挙げていきたいと思います。

※この記事は競技プログラミングにある程度参加している人が読者であることを想定しています。そうではなくて、どうしてこんなものを使うの?と疑問がある方は、インターネットで検索するとQuoraにある質問等がヒットしますので、そちらを御覧ください。それでも尚分からない方にとっては、記事の内容が不健全に見えるでしょうから、注意して下さい。


よく見かける定番機能

指定回数ループして現時点の回数も分かるrepマクロ

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

定番のrepマクロです。マクロなので作法として大文字にする人がいたり、よく使うし最早rep文なので小文字にする人がいたりします。

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

これはnatsugiriさんのテンプレートから引用しました。repを使う時はほとんどの場合で第二引数の値が変わらないことを前提として使われますが、第二引数が何らかの関数(vectorのsize()とか)である場合にいちいち呼ぶと、例えそれがO(1)のsize()であっても、ループ回数が非常に多い場合はTLEしてしまう事が過去にありました。 これを避けるのが上記のマクロで、二重repの場合でもrepの第一引数に同じ名前の変数を使わない限りは変数名が被っていると怒られることはありません。

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

こちらはrepマクロではないですが、機能が似ているのでここで紹介します。pythonのrangeみたいなものをC++でも扱うことができます。これはir5先生のテンプレートから引用しました。repマクロですが、冷静になると変数の宣言を一切してない点が気持ち悪いです。rangeクラスを使えば、変数を宣言していない問題は解決されます。

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

こちらは可変長引数のrepマクロです。repの引数が2つの場合と3つの場合で_overload3のnameが変わって挙動が変わります。(すごい) stqnさん、evimaさんのテンプレートにありました。

もう全部だしallマクロ

#define all(x) (x).begin(),(x).end()

sortやlower_boundする時に先頭と末尾のイテレータを渡すことはよくありますが、あまりにも頻出なためマクロで一纏めにしておくと便利です。

型名長杉、省略させて

using ll = long long;
typedef long long ll;
typedef long long int64;
typedef long long lint;
typedef long long lli;

long longはあまりにも頻出なので、もっと打ちやすく見た目もよい型名にエイリアスしている人が多いです。C++11から一番上みたいな記法もできるようになりました。 私事ですいません、自分はlint派なのですが、skyさんもlint派で感激しました。国内外問わずll派が圧倒的に多く、海外ではint64派も存在します。lintにしてるのは打ちやすさとintっぽさを残したかったからです。

size()がunsignedでつらい

#define SZ(x) ((int)(x).size())

unsignedなので加減算して思わぬバグを踏むことがあったり、intが絡む計算をするといちいち警告が出たりするので、それらを防ぐ目的のマクロです。

好みが分かれる機能

memsetマクロ

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define clr(ar,val) memset(ar, val, sizeof(ar))
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))

いろんな人がいろんな名前でmemset絡みのマクロを作っています。 配列を何かで埋めたい場合に使う事が多いmemsetですが、第一引数と第三引数に大抵同じものを書くことになるので、マクロにするのも一つの手です。 埋める内容も大抵0, -1, 0x3fの3通りなので、それら毎にマクロを作ってもいいかもしれません。

デバッグ出力マクロ

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

手元の環境でのみLOCALをdefineしておいて、上のように書くと手元ではデバッグ出力が見えて、ジャッジサーバーでの実行時には(LOCALが定義されていない限り)出力されません。 コンパイルオプションに-Dhogehogeとするとhogehogeがdefineされます。 海外勢のテンプレートでは上のようなeprintfをよく見かけましたが、それ以外にも手元の環境でのみデバッグ出力用の関数が書かれたヘッダをインクルードして使う人もいます。

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

最大値、最小値を更新する関数

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

sune2さんのテンプレートからの引用です。

if(hoge < fuga + piyo) hoge = fuga + piyo;

みたいなコードを書くと同じ部分が2箇所出てきて、配列の添字などが絡んでくると同じものを2つ書きたくないので、更新用の関数があると便利です。 また、値が更新された時に限りtrueを返すようにしておけば、例えばDPの経路を復元したい場合にきれいに書けます。

名前も色々付け方があり、umax(update?), amax(assign) とかにしている人がいます。

長いのは全部短く

#define pcnt __builtin_popcount

#define buli(x) __builtin_popcountll(x)

#define pb push_back
#define mp make_pair

#define F first
#define S second

いろんな人からの引用です。 この辺はかなり好みが分かれますが、長いと打つのにも時間がかかるので、短く省略するのも一つの手です。

名前が被るのが嫌

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev

いろんな人からの引用です。 y0等は標準ライブラリ関数として存在しているので、変数名にy0等を使うと怒られます。それを避けるためにy0等を別の名前に置き換えます。

自前の入出力関数

AOJだと、readで全部入力を読んで自分でパースすると、入力が非常に大きい時には実行速度が結構速くなります。 getcharなどを使って入力を読んでパースしている人も少数ですが存在します。こだわりが垣間見えます。

確かに、scanfはやや長いし、cinは速度面で不満があるので、このような関数を自前で準備するのは一つの手です。

repの変種

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

zerokugiさんのテンプレートから引用です。名前は異なりますが同じようなマクロはそこそこ見かけました。zerokugiさんの場合は頭にRつけると逆向き、最後にSつけると1-originになるみたいです。

#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

これは私のテンプレートからの引用です。順列を全通り試したい時に使います。

あると便利な機能は一応入れる

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

jcvbさんから引用、冪乗計算やgcdやdxdyが必要な時にいちいち書かなくて済むという利点があります。

void precalc() {

    /*for (int i = 2; i < C; ++i) {
       if (!least_prime[i]) {
           least_prime[i] = i;
           for (li j = i * 1LL * i; j < C; j += i) {
               least_prime[j] = i;
           }
       }
   }*/

    /*fact[0] = revfact[0] = 1;
   for (int i = 1; i < 100500; ++i) {
   fact[i] = fact[i - 1] * i % curMod;
   revfact[i] = binpow(fact[i], curMod - 2, curMod);
   }*/

    /*for (int w = 0; w < 2; ++w) {
   powers[w][0] = 1;
   for (int j = 1; j < C; ++j) {
   powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w];
   }
   }*/

    /*catalan[0] = 1;
   for (int n = 0; n < 200500 - 1; ++n) {
   catalan[n + 1] = catalan[n] * 2 * (2 * n + 1) % MOD * binpow(n + 2, MOD - 2, MOD) % MOD;
   }*/

    /*for (int i = 0; i < 5010; ++i) {
   c[i][i] = c[i][0] = 1;
   for (int j = 1; j < i; ++j) {
   c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
   }
   }*/

    /*for (int i = 0; i < 100; ++i) {
   doubleC[i][i] = doubleC[i][0] = 1.0;
   for (int j = 1; j < i; ++j) {
   doubleC[i][j] = doubleC[i - 1][j - 1] + doubleC[i - 1][j];
   }
   }*/
}

Kostromaさんから引用です。precalcの中に素数篩、階乗とあるmodでのその逆元、カタラン数、二項係数などがあり、アンコメントすることで使えるようになっています。

突き詰めるとライブラリを全部貼るのが一番便利なのかもしれません。

マイナーだけど面白いと思った機能

cauto

#define cauto const auto&

climpetさんのテンプレートからの引用です。結構使うのであると便利そうです。

bit(x)

#define bit(n) (1LL<<(n))

Mi_Sawaさんのテンプレートからの引用です。ビット演算の優先順序は正直覚えてなくて、書くといっつも括弧だらけになるし、たまにLLを忘れるので、あると便利そうです。

uniqueどうやるんだっけ?

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

zerokugiさんのテンプレートからの引用です。 長いし、(私は使い方を忘れるので、)マクロにしておくのも一つの手です。

打ち間違えても安心

#define itn int

Golovanov399さんから引用です。打ち間違いを直す時間すら惜しい。

最後は神頼み

f:id:ehafib:20151223165244p:plain

引用元

提出したコードにバグがないことを祈り、バグを踏むケースがないことを祈りましょう。 hackしようとして開いていきなりこれが表示されると、なかなかインパクトを受けます。

その他

たまに見かけるおまじない

#pragma comment (linker, "/STACK:256000000")

スタック領域を拡張するおまじないだそうですが、MSVC++でしか効果がないそうです。

#define _CRT_SECURE_NO_WARNINGS

これもMSVC++だとscanf等のセキュリティが弱い古い関数を使った時の警告を抑制する効果があるそうですが、GNU g++ではおそらく無意味です。

#define _USE_MATH_DEFINES

これもMSVC++だとM_PIが使えるようになるらしいです。

ヘッダ

#include <bits/stdc++.h>

GNU g++でのみ使えるヘッダで、中はこうなっています。

大抵のマシンでは<bits/stdc++.h>で全部インクルードしても問題ないのですが、ICPC等でマシン環境がポンコツだった場合にこれをするとコンパイルに時間がかかるので注意が必要です。

やや脱線しますが、gnu g++では__gcd()stl_algo.h内で定義されているから自分でgcdは書かなくてもよいことはよく知られていますが、__lg()という関数もあります。こちらは例えばセグメントツリーを作る時の配列のサイズを計算する時などに短く書けたりします。ここで挙げた機能は全てC++標準の機能ではありません。

main関数より先に呼びたい関数がある場合

例えばcin高速化などをしたい時など、main関数の冒頭部で必ず呼ぶ関数は別の箇所にまとめて記述することもできます。

struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

こういう構造体を実際に作ることでコンストラクタが呼ばれ、main関数より先に実行されます。

テンプレートが長すぎて見た目によくない場合

大抵のエディタには折りたたみ機能がついているのでそれで畳んであげると見た目はよくなります。

テンプレートの中身をあまりに常用するのでシンタックスハイライトで色を付けたい場合

私と同じエディタを使っている場合、私の設定がこちらにありますので、参考になるか分かりませんがご自由にお使い下さい。

デバッグ出力の見た目をよくしたい場合

f:id:ehafib:20151223165303p:plain

私は(こんな感じ1), (こんな感じ2)デバッグ用出力関数を書いてますが、まだ試行錯誤している段階です。便利そうなデバッグ出力の方法をご存知の方はどうか教えて下さい。

おわりに

明日はuvarimeronさんによる「実際に日常生活で役立った競技プログラミング」です。伊東家の食卓もびっくりなやつを期待しています。

2/24追記: コード片を着色・注意書きを追加