これはなに

実装力で戦える！～競プロにおける実装テクニック14選～ - Qiita に触発された

競技プログラミングでコーディングの際気を付けていること - うさぎ小屋を強く参考にしている

効果が高い or 一般性がありそう　なことから書いたつもり

重要なこと

「競プロのきれいなコードと業務のきれいなコードは違う」と定期的に唱える。未来の自分 or 他の人が読む必要がないことを仮定できるため、様々なバッドノウハウ(業務)が正当化される。(あえて過激なことを書くと、)「using namespace stdを使わない」などは逆にバッドノウハウ(競プロ)だと思っている。

-fsanitize=undefined,address / -D_GLIBCXX_DEBUG

#include <iostream>

using namespace std;

int main() {
    int a[10];
    cout << a[100] << endl; 
    return 0;
}

このコードは当然未定義動作だが、これを g++ main.cpp -g -fsanitize=undefined,address とコンパイルして実行すると

A.cpp:7:13: runtime error: index 100 out of bounds for type 'int [10]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior A.cpp:7:13 in

などと出てくる。他にも様々な未定義動作をキャッチできる。速度に影響があるが、手元で使わない理由はないと思う。他にも-D_GLIBCXX_DEBUGをコンパイルオプションに入れると色々検知するようになるが、macで使えない…

当然ながら g++ main.cpp -g -fsanitize=undefined,address などといちいち打つのは時間の無駄なので、aliasなどの機能を適時使うと良い。

コーディングスタイル

コーディングスタイル(インデント, space/tab, ...)は揃ってないより揃ってたほうがいい。有名規約で言うと Google C++ Style Guide に従っている人が身近では多い気がする。

インデントを手で整えるのは時間の無駄なので、エディタの自動整形に任せるべき。自分は以下の.clang-formatでvscodeに全部任せている。

BasedOnStyle: 'Chromium'
IndentWidth: 4
AccessModifierOffset: -2

# for competitive programing
AllowShortFunctionsOnASingleLine: All
AllowShortIfStatementsOnASingleLine: true
AllowShortLoopsOnASingleLine: true
AlwaysBreakTemplateDeclarations: false

いわゆる「きれいな」コーディングスタイルが(競プロで)常に正しいかというと怪しい。例えば1 * 2 + 3 * 4と1*2 + 3*4なら後者のほうが読みやすいと思う(自分はもう手癖で入れてしまうが…)。

using namespace std

575とも呼ばれる。std::があらゆるところから消せるのでコードがスッキリする。名前空間が汚染されるというデメリットがあるが、引っかかるのは無視できるぐらいの確率なので圧倒的にメリットのほうが大きいと思う。

マクロ / スニペット

マクロは俗に言う

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

みたいなやつ。僕はマクロは使っていないがfori / all でこれらが出てくるスニペットを登録している。マクロを使っても競プロなら何のデメリットもない。

とりあえず手でいちいちfor (int i = 0; i < n; i++)を書いているならば見直したほうがいい。

printfデバッグ /デバッガ

個人的には多くの場合でデバッガよりprintfデバッグのほうが速いと考えているが、デバッガのほうが強いときもある。assertで落ちたときにスタックトレースを確認するなど。僕は雑にlldbを使うが、これは改善の余地がある気がする。

printfデバッグするにしろ、printfをいちいちつけたり消したりするのは時間の無駄、僕は以下のようなマクロ(を強化したもの)を使っている。

また、vector / mapなども簡単に出力できるようにするといい。operator<<をオーバーロードするなど

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

goto

競プロでもgotoを使ってメリットが有るタイミングは少ないと思うが例外もある、有名な例は多重ループの大域脱出がある。

bool ok = false;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (solve(i, j)) {
            ok = true;
            break;
        }
    }
    if (ok) break;
}

が

bool ok = false;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (solve(i, j)) {
            ok = true;
            goto loop_out;
        }
    }
}
loop_out:

のように書けるというやつ。2重だとありがたみが薄いが、競プロでは平然ともっと多重のループが出てくるので、そういう時に強い。

bool ok = [&]() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (solve(i, j)) return true;
        }
    }
    return false;
}();

このようにも書け、自分はこちらをよく使う。

再帰ラムダ

普通にdfsを書こうとすると

vector<vector<int>> g;

void dfs(int v, int parent) {  
    for (int u: g[v]) {
        if (u == parent) continue;
        dfs(u, v);
    }
}

int main() {
    dfs(0, -1);
}

となるが、これを

int main() {
    vector<vector<int>> g;

    auto dfs = [&](auto self, int v, int parent) -> void {
        for (int u: g[v]) {
            if (u == parent) continue;
            self(self, u, parent);
        }
    };
    dfs(dfs, 0, -1);
}

と書ける。独特な記法を覚える必要があるが、処理を上から下へと書けるのは大きい。なお、ラムダ式は覚えると便利な事が多いので慣れると吉。

vector<vector<>>を短く書けるようにする

個人的おすすめ。V<int> / VV<int>でそれぞれvector<int> / vector<vector<int>>になるようにしている。便利。

よすぽの日記

競プロ実装テクニック