AtCoder青になったので競技プログラミングの話

この記事はKMC Advent Calendar 2020 - Adventarの6日目(12/6)の記事です。

5日目の記事は、id:pelkさんの好きなカードデザインの話 - pelkのふわふわもこもこ次元でした。

TCGというと、シンクロが出るより前の遊戯王くらいしかまともに遊んだことがないです。デザイン違いですが、当時はレアカードの装飾が好きで主にシークレットレアカードを好んで収集していた気がします。

はじめに
競技プログラミング遍歴
コーディング環境
テンプレートコード
まとめ
次回のKMC Advent Calendar

はじめに

KMC8年目のdamaです。 Twitter等ではDNEKと名乗っています。

毎年12/6にKMC Advent Calendarの記事を書き続けて6年目ですが、昨年まではスマホアプリやWebサイトのリリース・アップデート記事しか書いていませんでした。

しかし今回は~~宣伝するものが無かったので~~趣向を変えて競技プログラミングの話をします。

競技プログラミング遍歴

ここはただの自分語りなので適当に読み飛ばしてください。

競プロ以前

そもそも私がプログラミングを始めたのは小5くらいの頃です。ゲームを作りたいと父親に言ったら何故かExcel VBAを勧められ、暫くは短いスクリプトを書いて遊んでいました。環境構築等のハードルがなく、プログラミングを始めるきっかけとしては良かったと思います。

中学生になって初めて英単語を覚えることになった際に、一問一答形式でランダムに英単語を出題するプログラムをExcel VBAで作りました。これが初めて作った実用的なアプリケーションだったと思います。

中3辺りでよりアプリケーションらしいものを作りたくなり、VB.NETに移行しました。高校進学後も特に変わりはなく、HTMLやJSをちょっと触るくらいだったと思います。ちなみに言語学を専攻したかったので文系に進んでおり、数学力も京大文系としては平均的だったと思います。

初めての競プロ

2013年に京都大学文学部に入学し、KMCに入部したときに、初めて競プロの存在を知りました。言われるがままにC++を使いながら、1年半くらい勉強会に参加し続けていました。多分緑くらいの実力は付いていたと思います。 KMC外部では主にTopCoderとCodeForcesに参加しており、出来て間もなかったAtCoderには参加していませんでした。

また、1回生の前期に宮崎修一先生の全学共通科目：アルゴリズム入門を受講していました。アルゴリズムの基本的な考え方に慣れる上でとても役に立ちました。来年度以降も開講されていれば、是非受講してみることをお勧めします。

競プロ再開

時を隔てて2018年初め頃に競プロを再開しました。再開した理由は覚えていないですが、仕事を辞めて休学していた大学院も中退を決め、（金銭面以外は）色々と余裕ができたからだと思います。

日本語ベースでUIも分かりやすかったので、とりあえずAtCoderだけ参加することにしました。また、VSCodeが普及していてローカルの環境構築がだいぶ楽になっていた印象があります。ただ、再開して2年ほどは参加頻度が低くて大して勉強もしておらず、1200前後で停滞していました。

水から青に

今年の春頃、別サークルで一緒に精進する仲間ができたのを機に、真面目に勉強してコンテストもほぼ毎回参加するようになりました。

主にAtCoder Problemsを使って過去問を埋めていき、新しいアルゴリズムが出るごとに再利用性を意識しながらスニペット化していきました（後述）。常に満遍ない難度を練習できるように、なるべくコンテスト単位でまとめて解くようにしています。そのため、ratedコンテストを概ねMax diffが低い順に解いています。

そして11/1のAtCoder Beginner Contest 181 - AtCoderで、なんとか青色になることができました。

dnek - AtCoder

……まだ青色ですね。

コーディング環境

基本

iMac (Retina 4K, 21.5-inch, 2017) 上でVisual Studio Codeを使っています。画面左半分にChrome、右半分にVSCodeを置いています（更に49インチのディスプレイでVTuberの配信を垂れ流しています）。

以下、個別に紹介します。

atcoder-tools

atcoder-toolsを使わせていただいています。主に以下の機能を利用しています。

テンプレートコードの自動生成
ローカルテスト
コード提出

また、以下のシェルスクリプトでコードの自動生成&問題ページの表示&生成したcppファイルの表示を一括で行っています。 A問題から順に解けるよう降順で開くようにしています。

#!/bin/zsh
atcoder-tools gen $1 --config .atcodertools.toml
if [ -e $1 ]; then
  cd $1
  array=()
  for dir in *
  do
    if [ -e $dir ]; then
      array=($dir "${array[@]}")
    fi
  done
  for dir in ${array[@]}
  do
    p=$(cat $dir/metadata.json | jq -r .problem.problem_id)
    open https://atcoder.jp/contests/$1/tasks/$p
  done
  for dir in ${array[@]}
  do
    code $dir/main.cpp
  done
  cd ..
fi

テストと提出はVSCodeのタスクにまとめてショートカットキーを割り当てて使っています。

ちなみにAtCoderの言語アップデートに対応する際に、レビューで1行だけcontributeしました。

github.com

ただ、今となっては過去問の提出言語も統一されていて意味のないものになっています。

VSCodeスニペット

ある程度汎用的で頻繁に使いそうな関数等はテンプレートコードにまとめていますが（後述）、多くのアルゴリズムはVSCodeのスニペットにまとめています。

snippet generatorを使ってC++コードからJSONに変換しています。

ちなみに私はスクラッチでアルゴリズムを書く気力が無いので、ほとんどはei1333さんのLuzhiled's Libraryから拝借して適宜カスタマイズしています。こちらのライブラリはUnlicenseでライセンスされています。

テンプレートコード

テンプレートについては自力で書いたものが多く、その中でもマイナーそうなものを紹介します。ちなみに雰囲気でC++を書いているので、変なことをしている可能性があります。

#define int ll

私はintをlong longで上書きしています。利便性に比べれば副作用は微々たるものだと思っています。勿論実務でこういうことはしません（実務でC++を使っているわけではありませんが）。

ただし、よくある#define int long longではなく、以下のようにllを挟んで使っています。

#difine int ll
using ll = long long;

これにより、int(hoge)のようなキャストがlong long(hoge)と2語に展開されて構文エラーになるのを防いでいます。そもそも(int)hogeとすれば済む話ではありますが。

ちなみに今度はunsigned intなどが構文エラーとなるので、#define uint unsigned long longとしてuintを使うと良いでしょう。

可変長入出力関数

入出力の際にいちいち>>と<<を書くのが面倒なので関数化しています。また、可変長引数を取れるように再帰させています。

void CIN() {};
template <class T, class... U>
void CIN(T &&x, U &&...y) {
  cin >> x;
  CIN(forward<U>(y)...);
}
void _COUT() { cout << '\n'; }
template <class T, class... U>
void _COUT(T &&x, U &&...y) {
  cout << ' ' << x;
  _COUT(forward<U>(y)...);
}
void COUT() { _COUT(); };
template <class T, class... U>
void COUT(T &&x, U &&...y) {
  cout << x;
  _COUT(forward<U>(y)...);
}

例えば以下のように使えます。

int a, b;
string s;
CIN(a, s, b); // cin >> a >> s >> b;
COUT(b, s); // cout << b << ' ' << s << '\n';
COUT(a); // cout << a << '\n';

丸め方向別除算

C++では、普通に整数を割ると0に向かって丸められます。一方、組み込みのceil()及びfloor()は、それぞれ正方向と負方向に浮動小数点数を丸めます。

整数除算においてこのような丸めを正しく行えるようにそれぞれ関数化しています。

// 正方向
int ceil_div(int x, int y) {
  int d = x / y;
  return d * y == x ? d : d + ((x > 0) ^ (y < 0));
}
// 負方向
int floor_div(int x, int y) {
  int d = x / y;
  return d * y == x ? d : d - ((x < 0) ^ (y < 0));
}
// 0と反対方向
int out_div(int x, int y) {
  int d = x / y;
  return d * y == x ? d : ((x > 0) == (y > 0)) ? d + 1 : d - 1;
}

（2021/7/27 constexpr などを除去）

#pragma region

VSCodeでは、以下のようにregionで囲んでおくとコードブロックと同じように折り畳むことができます。

#pragma region header

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

#pragma endregion header

実はheaderの部分は無くても良いですが、分かりやすいので付けています。

ちなみに以前この折り畳みを自動で行う拡張機能を作ったのですが、逆に鬱陶しく感じるようになったので今は使っていないです。

ファイルを開いたときにregion（C++で言う#pragma region〜#pragma endregion）をすべて自動で折り畳むVSCode extensionを作りました（主に競技プログラミングのため）。
これでマクロ書きまくりでもいちいちスクロールせずに済みます。https://t.co/eEl6mC0uNF
— DNEK(でぃーねっく) (@dnek_) 2020年4月14日