この記事は、Competitive Programming (1) Advent Calendar 2020 - Adventarの18日目の記事です。

はじめに

本格的に競技プログラミングをはじめてから3年近く経ったので、実装の際に意識していることについてまとめることにしました。自分はどちらかというと競技プログラミングに特化した方法というよりはある程度汎用的に使えるような手法を模索してきたつもりですが、その中でも競技プログラミングでC++を書く際に意識していることに限定して書いていきます。

以下参考資料です。方針が違う部分もあると思うので、複数の記事などを参考にそれぞれのコーディングスタイルを確立して貰えればと思います。

自分が最も重視しているのは、バグの沼にハマるのを防ぐために、多少時間をかけてでもバグを埋め込みにくい&バグってもデバッグしやすいコードを書くことです。以下、そのために自分が取り入れている手法を紹介していきます。

★★★：かなりおすすめ ★★：やった方が多少良さそう ★：個人の好みの域かも

コードはできるだけ簡潔に！(★★★)

問題自体の考察が終わっても実装に移る前に実装の方針をまとめる
コピペしようとしていたら要注意！同じ操作はできるだけfor文で書けないか考える
- 逆から同じ操作するときは2回ループ回してstd::reverseするなど
- 入力がa,b,cなどであってもstd::vectorを検討
番兵などを適切に用いて境界の場合分けを減らす
できるだけC++の機能を使う
- std::accumulate、std::findなど
- この記事に一度目を通しておくとよい競技プログラミングとC++のアレコレ - koturnの日記
簡単な処理はできるだけ短く書くと、アルゴリズム的に本質的な部分がわかりやすくなる
コンテストなどで複雑な実装になってしまった場合は他人のコードなどを読んでみると勉強になる。個人的にはrisujirohさんやarmeriaさんのコードがおすすめです

フォーマッタを使う(★★★)

見やすくなるのももちろんだが、コーディング中にスタイルに関して脳を全く使わなくて良くなるのが大きい
別の記事参照

未初期化の変数を作らない(★★)

気づきにくいバグの原因になるので避ける
初期化する値が特にない場合は-1などありえない値に初期化しておいてassertする

意見が分かれるかもしれないが、

int x;
if (flag) {
    x = -1;
} else {
    x = 1;
}

よりは c++ int x = flag ? -1 : 1;

C++の入力は独特なので、std::cinのwrapperの中に未初期化の変数宣言を押し付ける
```
#include <iostream>
#include <string>
struct in {
    template <class T> operator T() {
        T t;
        std::cin >> t;
        return t;
    }
};
int main() {
        int x = in();
        std::string s = in();
        std::cout << x << " " << s << std::endl;
}
```
- input関数、関数返り値でtemplateが推論されないのが面倒で使ってなかったけどキャスト演算子でいけることに気づいてしまった
  struct input {
  input(){};
  template <class T> operator T() {
  T t;
  cin >> t;
  return t;
  }
  };
  int main() {
  Int n = input();
  }
  — けんしん (@knshnb) November 24, 2019
どちらも単純な処理がより短い行数で書けるという副次効果もある

変数のスコープは小さく(★★)

グローバル変数はできるだけ使わない
- マルチテストケースなどでバグらせやすい
- 定数倍高速化でグローバル静的配列などを使うのは仕方ないが、一旦普通にコーディングしてテストした後に逐次的に変更していくのが望ましい
- 再帰は
```
auto dfs = [&g](auto&& self, int v, int prv) -> void {
    for (int s : g[v]) {
        if (s == prv) continue;
        self(self, s, v);
    }
};
```
などの様にラムダ式で書く - そもそも関数は意味のある単位で定義したいのに、再帰の実装という都合だけで関数をグローバルに定義したくない（？）
ラムダ式の参照キャプチャはすべての変数が見れてしまうので、丁寧にコーディングするときは変数を指定してキャプチャする

ローカルの実行環境(★★★)

g++の-includeオプションでローカルで常に読み込むファイルを指定できる
- 例えば、提出ファイルには
```
#ifndef dump
#define dump(...)
#endif
```
だけ書いておき、ローカルのこういうファイルをインクルードすることでdumpマクロで手元のみデバッグ出力するといったことができる
他には、-O0 -std=c++17 -Wshadow -Wall -Wno-sign-compare -D_GLIBCXX_DEBUGといったオプションを付けている。これは環境や個人の好みにも依存すると思うが、配列外参照などを検知してくれる-D_GLIBCXX_DEBUGの優先度は高そう
online-judge-toolsによるサンプル実行の自動化などは別記事参照

巨大な生配列ではなく、std::vectorで使いたい丁度のサイズを確保する(★★)

思考停止でサイズが決定できることよりも、想定外の挙動の検知しやすさを優先
0がたくさんついた生の数字よりもnなどの方が間違えにくい

便利マクロ・関数など(★★)

単純なループのときにfor文を手打ちするのはややリスクがあると思う。2引数と3引数を両方扱えるREPマクロが便利

#include <iostream>
#define REP_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
int main() {
    REP(i, 5) std::cout << i << std::endl;
    REP(i, 10, 13) std::cout << i << std::endl;
}

慣れるとfor文に比べて可読性も上がる。人によって命名が違うので定義見に行かないといけないのがやや面倒だが…

入出力高速化。標準入力と標準出力の同期やCの入出力とC++の入出力の同期を切ったりする。AtCoderでは少ないが、Codeforcesではこれをせずにstd::cin,std::coutを使うとTLEすることがたまにある
```
std::cin.tie(nullptr), std::ios::sync_with_stdio(false);
```

以下は便利なので使用している

template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; }
template <class T> using V = std::vector<T>;

その他宗教(★)

可読性のため、テンプレートはできるだけ短くしてsnippetなどエディタの機能を使う
#define int long longしない
- どうやらgccでは未定義動作ではないようだが、他人にコードを見せる際などにあまりに紛らわしいわりにテンプレートとして入れておくメリットは少ない
- Topcoderではコンパイルが通らなかった気がする
- 代わりに、using Int = long longとしてIntの型を簡単に変えられるようにしている
using namespace std;しない
- 実装が数秒遅くなるというデメリットがあるが、現実世界とのバランスをとって(競プロにおいては)妥協している

終わりです。そういえば、この記事は競技プログラマのためのC++作法がそこそこアクセスされていることに対する反省で書きました。

knshnbのブログ

Categories

競技プログラミングでC++を書くときに意識していること