競プロで役立つ（？）C++小技集

作成日: 2019年8月29日

競技プログラミングの際のC++の小技だったり罠だったりのメモです。GCC用。C++14を仮定。using namespace std;はされているものだと思ってください。

REPマクロ

#define FOR(i,l,r) for(size_t i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)

競プロをやるときに私がC++を使う理由の最たるもの。めちゃくちゃ快適。

int N; cin>>N;
vector<int> A(N);
REP(i,N){
    cin>>A[i];
}

のようにして使えます。

一応上記のように FOR マクロを経由してREPを書いているのですが、REPで対応できないようなループを書くときには私は普通にforループを書くのでFORのほうは使っていません。

bits/stdc++.h

#include <bits/stdc++.h>

GCCについている、標準ライブラリを全部includeしてくれるヘッダファイルです。あまりにも便利なので頼り切っていますが、これを使おうと思うとエディタの環境構築がちょっと面倒になったりもします（支援ツールがClang系の場合）。

intをlong longにする

#define int long long

signed main(){
    int hoge = 3; // これは long long になる
}

誰が考案したのか知りませんが広く使われているやつです。define便利。signed main()にするのがミソ。

long longの大きさも処理系依存ではあるのですが、少なくとも64ビット以上の幅であることが保証されているらしい（参照：long long型 - cpprefjp C++日本語リファレンス）ので安心です。

但し、

#define int long long
signed main(){
    auto f = [](int n){
        if(n>0) return n;
        else return 0;
    };
}

のコードが

lllambda.cpp: In lambda function:
lllambda.cpp:6:21: error: inconsistent types ‘long long int’ and ‘int’ deduced for lambda return type
    else return 0;

のエラーでコンパイルできないなんていう微妙な問題を踏んだことがあります。これはintのリテラルである0とnの型であるlong longが一致しないために型推論に失敗しているということなので、

#define int long long
signed main(){
    auto f = [](int n){
        if(n>0) return n;
        else return 0LL;
    };
}

のようにリテラルをlong longにするか、

#define int long long
signed main(){
    auto f = [](int n) -> int {
        if(n>0) return n;
        else return 0;
    };
}

のように返り値の型を明示してやればコンパイルできます。

が、コンテスト中にこういう問題を踏むのは面倒なので、

using ll = long long;
signed main(){
    auto f = [](ll n){
        if(n>0) return n;
        else return 0LL;
    };
}

のように最初からすべてをlong long前提で書いていくのが安全なのかなと思います。~~でも手癖でintを書いてしまうので難しい………~~

コンパイルオプションでデバッグ用コードをON/OFFする

$ g++ -std=c++14 -D_DEBUG -o a a.cpp

のようにコンパイルすることで、マクロ_DEBUGが定義されます。

提出した先ではこのマクロが定義されないので、このマクロの存在によって分岐するコードを書くと手元と提出先で別の挙動をさせることができます。

例えば、

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)

のようにすると、debug(a);は-D_DEBUGつきでコンパイルされた場合にのみ変数aの内容を出力します。デバッグ出力の消し忘れが起きないので便利です。

コンパイルオプションで境界チェック

C++は実行時のオーバーヘッドを嫌うので、デフォルトでは配列の境界チェックなどが行われません。しかし、コンパイラにオプションを渡してやると、デバッグに役立つ諸々の情報を出すようなバイナリを吐いてくれます。手元でこのようなオプションをつけてデバッグしても提出先ではデフォルトのオプションでコンパイルされるので、実行時間の心配もいりません。

$ g++ -fsanitize=address -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -o a a.cpp

-fsanitize=address は配列の境界外参照などの場合に詳細なエラーを吐いて落ちてくれるようなバイナリを吐くオプションです。

-D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC をつけておくと、std::vectorの[]がat()相当（境界チェックが行われる）になります。

他にもデバッグに役立つGCCのコンパイルオプションがいろいろ Catching silly mistakes with GCC - Codeforces という記事にまとめられています。この記事の結論としての全部盛りコンパイルオプションは

-Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector

のようです。

#pragma region

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
// iteration helper
#define FOR(i,l,r) for(size_t i=(l);i<(r);++i)
#define REP(i,n)  FOR(i,0,n)
#pragma endregion

これは Visual Studio Code 限定ですが、 #pragma region を使うとコードの領域を定義できます。ライブラリをこれで囲んで畳んでおくと本題のコードが見やすくなります。

std::set::lower_bound

これは私の踏んだ（誰もが踏むらしい）罠の説明です。STLには二部探索を行うstd::lower_bound等の非メンバ函数がありますが、std::set（やstd::multiset）でこれを使うと計算量がO(logN)ではなくO(N)になります。

cppreference.comのページにある

行われる比較の回数は first と last の距離の対数です (多くとも log2(last - first) + O(1) 回の比較)。しかし、 LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は線形になります。

の「LegacyRandomAccessIterator でない場合」に std::set は該当するからです。

代わりに std::set のメンバ函数の std::set::lower_bound を使ってやると、計算量がO(logN)になります。

可変引数のdebugマクロ関数

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif

このようにしてやるとdebug(x);もdebug(x,y,z);も通るようになります（参照：C言語の可変長引数マクロで擬似オーバーロード | 雑記帳）。上の例では5引数までですが、同様にしてやればもっと多くの引数に対応させることもできます。 ~~正直何やってるかよくわかってないです。~~

なぜこんなことをわざわざマクロ函数でやっているのかといえば、変数の名前を取得するという芸当が「マクロ函数で#xを使う」という方法でしかできないからです。変数名を取得する必要がなければC++11の可変引数テンプレートで実現できます。

グローバルvectorの初期化

DPを行う場合など、main函数だけで処理が完結しない場合は変数をグローバルに持っておきたくなりがちです。が、ICPCのようにデータセットが複数ある場合、配列をグローバルに置くと

int M,N;
constexpr MAX_N = 100;
constexpr MAX_M = 200;
int DP[MAX_N][MAX_M];

int main(){
    while(true){
        cin>>M>>N;
        REP(i,MAX_N){
            REP(j,MAX_M){
                DP[i][j]=-1;
            }
        }
        //略
    }
}

のように毎度初期化のコードを書かねばならず面倒です。

vectorを使えば、

int M,N;
vector<vector<int>> DP;

int main(){
    while(true){
        cin>>M>>N;
        DP = vector<vector<int>>(N, vector<int>(M, -1));
        //略
    }
}

のように簡単に初期化できます。

memset函数を使うなどして多次元配列を簡単に初期化する方法もありますが、私にはこの辺の函数は怖くてあまり使いたい気持ちにならないです……

まとめ

こんな小技を探すよりアルゴリズムを勉強して精進した方がいいと思います。