AtCoder 黄色になるまでにしたこと！

例

例えば出力が 個ある時には、

std::cout << n << std::endl;
std::for_each(ret.begin(), ret.end(), [](auto& x){std::cout << x << std::endl})

サイズチェックを欠かしません。

assert(ret.size() == n);

#define int itn が一世を風靡するこの世の中、ここまで assert マクロを多用する競技プログラマも珍しいかもしれませんが、相応のリターンが得られていると思っています。簡単に言うとバグりづらく、またバグっても直しやすくなります。

実装している途中で

• 「このデータの持ち方は良くないなぁ、変えよう」
• 「あら、ここが間違っています。修正しましょう」

などとなるときがあると思います。そういうときはコードがつぎはぎになって間違えやすいですし、運が悪いと気づかずに最後まで書いてしまって

• 「あれ？あれ？合わないです……」
• 「この配列のインデックスは 0-based ですか？1-based ですか？」
• 「最初に書いたときに成り立っていた条件がいつの間にか壊れていました（泣）」

なんてことに。こうなったらもう遅いです。そうなるまえに、Let's assert!

例

例えばこちら問題
atcoder.jp

「個の整数 を選んで消し、新たに 個の整数 を書く」という操作をシュミレートする必要がありますが、私ならまずは徐ろに、こちらのラムダを入力の次あたりに書きます。アルゴリズムを書いていくのはそれからです。

auto sub = [&] (int i, int j) {
  assert(a[i] != inf && a[j] != inf);
  ret.emplace_back(a[i], a[j]);
  a[i] -= a[j];
};

このように切り分けていると、処理が切り分けられて分かりやすいだけでなく、] と ] を入れ替えたときにきちんと動くかななど、確かめることがで出来ます。

sub(2, 3);
debug(a); // 定義省略

例例

逆辺の挿入にも使えます。例えばこちらの問題。一列に並んだ人々がじゃんけんをして勝ち抜けするゲームです。入力が行列なのですが、半分しか与えられず、もう半分は自分で入れる必要があります。それだけでなく、両端に番兵も入れたいので、入力がちょっと面倒です。
atcoder.jp

2次元配列を用意します。

constexpr size+t max = 2002;
auto a = std::vector<std::bitset<max>>(n + 2);

まずは最弱のじゃんけんプレイヤー、番兵ちゃんを入れてあげましょう。

for (size_t i = 1; i <= n; i++) {
  a.at(i).at(0) = a.at(i).at(n +1) = true;
  a.at(0).at(i) = a.at(n + 1).at(i) = false;
}

そして、入力に従って要素を編集して、逆辺も忘れずに入れます。

  for (size_t i = 2; i <= n; i++) {
    for (size_t j = 1; j < i; j++) {
      char x; std::cin >> x;
      a.at(i).at(j) = (x == '1');
      a.at(j).at(i) = (x == '0');
    }

そう、逆辺も忘れずに……

忘れます！！ 忘れますし、忘れなくても true / false など、ごっちゃになってしまうことが多いので、私はこうです！ まずは逆辺も同時に入れてくれる関数を作ります。

auto insert = [&] (size_t i, size_t j, bool k) {
  a.at(i).at(j) = k;
  a.at(j).at(i) = !k;
};

すると、このように安心して入力を捌くことができます。

for (size_t i = 1; i <= n; i++) {
  insert(i, 0, true);
  insert(i, n + 1, true);
}
for (size_t i = 2; i <= n; i++) {
  for (size_t j = 1; j < i; j++) {
    char x; std::cin >> x;
    insert(i, j, x == '1');
  }
}

嬉しいですね。
コード自体が見やすいというのもあるのですが、後から変えたくなった時などに対応しやすいです。

例例例

次にこちらの問題です。（提出：Submission #6237522 - AtCoder Beginner Contest 132）
atcoder.jp

DP 配列 を 回更新する必要があるのですが、配列を使いまわば完全に同じ作業の繰り返しです。なので、一回の更新を関数化してしまって、

auto renew = [&] {
  // implementation
};

これで良いです。

for (int i = 0; i < k - 1; i++) renew();

他にも

• 面倒な assert を一括でできる
• メインのアルゴリズムよりも先に書くことができる（ボトムアップ）
• フリー関数と違ってラムダキャプチャーが使えるから手数が増えない

ど、数えきれない量のメリットを享受することができます。難しい問題になればなるほど効いてくる戦略なのかなと思っています。

※ 余談ですが、この問題の構造はけっこうおもしろいと思うので、後日それについて記事を書いてみたいとも感じております。

こちら、やっと原理がわかりました。i を n/i に対応させる写像 φ は反変関手になっていて、しかも自分自身と随伴（ガロア接続）なので φ は像の上で involutive です。https://t.co/16QSlpgI6o pic.twitter.com/ybwRVDn0fP

— ながたかな (@ngtkana) 2019年7月4日

はい、では assert, lambda に続いて 3 つ目行ってみましょ～う！

例

列があるとします。

std::vector<int> a(n);
for (size_t i = 0; i < n; i++) std::cin >> a.at(i);

隣接差を取る時に、このような間違いを犯したことはありませんか？ 私はあります。

for (size_t i = 1; i < n; i++) { // ループを逆順にしないといけません！
  a[i] -= a[i - 1];
}

しかし、STLを使うと間違えようがないと思います。

std::vector<int> b;
std::adjacent_differnce(a.begin(), a.end(), std::back_inserter(b));

例例

先ほどご紹介した重み付き累積和もこうです。

auto ret = std::inner_product(dp.begin(), dp.end(), w.begin(), mint(0));

例例例

（ソートしたいなど）諸事情によりペアで受け取ってしまった変数も……

std::vector<int> xa(n);
for (size_t i = 0; i < n; i++) std::cin >> xa.at(i).first >> xa.at(i).second;

このように簡単に分解することができます。

std::vector<int> x, a;
std::transform(xa.begin(), xa.end(), std::back_inserter(x), [](auto p){return p.first;});
std::transform(xa.begin(), xa.end(), std::back_inserter(a), [](auto p){return p.second;});

例例例例

vector の入力もこうすれば間違えなくて済みます。

std::vector<int> xa(n);
for (size_t i = 0; i < n; i++) std::cin >> xa.at(i).first >> xa.at(i).second;

このように簡単に分解することができます。

std::vector<int> v;
std::for_each(v.begin(), v.end(), [](auto& x){std::cin >> x;});

STLは特にシーケンス関連のアルゴリズムにかなり強いので、自分で書いて間違えてしまう前に、積極的に利用していくと良いのではないかと感じています。

まとめ