ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > AtCoder 黄色になるまでにしたこと！

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

AtCoder 黄色になりました！

すみません間違えました、こちらです。

色変当日に黄色になりました記事を書いたのは私が初めてでしょうか？ そうだと嬉しいです。

明日あたりには橙になっていると嬉しいですね🌸（嘘ですもうしばらくお待ちください）

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

黄色になるまでにしたことは憶えていないので、最近気をつけていることをご紹介したいと思います。
みなさんに質問です。このような経験はありませんか？

  • 「なぜかサンプルがあわない」
  • 「なぜか WA 」
  • 「どう見ても合っているのに……」

こうなってしまったとき、みなさんはどうしてますか？ いろいろかケースを試して、手計算と齟齬がないか目で見てチェックでしょうか。とりあえず long long に置換してみるのもいいですね。私はどうしていると思いますか？ 正直こうなってしまってから考えても遅いような気がします。初めに書く段階から、

  • バグらない
  • バグっても直しやすい
  • バグっても気づきやすい

コードを書いておくことが重要だと思います。

そのために私が気を付けていることをご紹介したいと思います。

  • assert を乱用する
  • 要素アクセスは at
  • メイン関数内にラムダをポン置きする
  • STL が使えるときには使えるときには使う

の 3 つです。

※ 実行速度は度外視しているので、AtCoder 以外のコンテストだとやらないほうが良いかもしれません∩(´；ヮ；｀)∩ﾝﾋｨｨｨｨｨ

AtCoder 黄色の私が気を付けていること

ごめんなさい、こちらが正しいタイトルだったかもしれません。

assert

みなさんはどういうときに assert を使いますか？ 答えが合わないときに、どこで落ちているか見るのに使うのでしょうか？ それも悪くはないのですが、初めに書く段階から積極的に assert を書いておくと穏やかです。

例

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

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!

要素アクセスは at

諸説ありますよね…… 割と劇遅なので、律速段階の要素アクセスだけ operator[] に変えるのも手かもしれませんが、今のところ AtCoder の問題で at が通らなかったことはありません。（もっと厳しい問題だと厳しいかもしれませんが、今のところ、AtCoder なら多分大丈夫なのではないかと高をくくっています。）

ラムダ

関数はラムダにしてメイン関数にポン置きすると平和です。また、関数化自体積極的にやって良いと思います。

例

例えばこちら問題
atcoder.jp

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

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

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

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 配列 を K - 1 回更新する必要があるのですが、配列を使いまわば完全に同じ作業の繰り返しです。なので、一回の更新を関数化してしまって、

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

これで良いです。

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

他にも

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

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

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

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

STL

STL の、特に algorithm ヘッダーの関数を使うことで、地球に平和が訪れることがあります。ただ、大幅にコードが削減されるなどというお話はないです。むしろ余計長くなります。

例

列があるとします。

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

まとめ

終わりです。やはり強い方のコードを拝見しても、私のような書き方している方はかなり少数派ですし、このやり方でみんながみんな強くなれるとは思いません。雑なコードを脳のメモリで補っている古株の競プロ er さんの能力には脱帽の日々です。ですが、私には私の強みがあり、弱みがあります。なので、みなさんの良いところは吸収しつつ、私は私のやり方で強くなろうと思います。次にお会いするときは赤だといいですね。ではでは！

あら、こちらは見出しでしたね。

追記(2019/07/16)

chokudai さんからご指摘がありました。

おっしゃるとおりです。「雑なコード」というのはさすがに言いすぎました。いいえ、言い過ぎではなく間違いであり、よく考えた末にそういうコードになっているので雑とは言えません。私も重々承知しているつもりだったですが、イキりたい気持ちが先に来てひどい言い方になってしまい、申し訳ないです。

実際そういう方のコードを拝見するときれいで読みやすく、一方私のコードのほうがひたすら繰り返される at など冗長で読みづらいと感じることも多いです。正直すっきり短いコードに憧れる気持ちすらあるのですが、しばらくそれで書いてみた結果私にはちょっと難しいかなと感じたので言語の力に頼ることにしたという経緯です。

私のようにバグらせてしまいがちな新人競技プログラマさんに良い選択肢を提示できたらいいなと思っての提案だったのですが、一部強い言葉遣いだったり妥当でない描写になってしまい、これは本当に申し訳なかったなと思います。インターネットに記事を掲載したのは初めてだったのですが、時間をかけて推敲することの大切さを知りました。ご批判ありがとうございます。

（ちなみにツンデレなので実は褒めてくださっていたりもします：

）