【入水】茶色コーダーによるAHC入水記事
AtCoder Heuristics Contest 054で水色コーダーになりました！
この記事では、私のAHCでの実行環境とこれまでにやったことを紹介しています。私のアルゴリズムのレートが茶色なこともあって初歩的なことしか書いていません。同じくらいの実力の方や、他の人にAHCを勧めようと思っている方の参考になればうれしいです。
環境
もともとWSL上でC++を使ってABCに参加していましたが、AHCを始めてから以下の3つをインストールしました。
Rust
配布されるローカルテスタを動かすために必要なプログラミング言語です。初めて参加したAHC045でローカルテスタがないとほとんど何もできないことに気づいて慌てて入れました。
pahcer
terry-u16さんが作成された、ローカルテストを並列して実行できるツールです。コマンド1つでローカルテストを実行して平均スコアを出せるのでとても使いやすいです。これを入れる前は自作のシェルスクリプトを使っていましたが、AHC048で痛い目を見た（WAを0点として計算したせいでバグを見落としてテストケースの半分を落とした）ので移行しました。
Git・GitHub
ファイルのバージョン管理ができるツールです。プログラムを変更してスコアが下がってしまったときに簡単に元に戻せるのでコードを書く上でのストレスが減ります。
やったこと
毎回コンテストに参加する
AHCはいくら失敗してもレートが下がる心配がないので気軽に参加していました。どの回も問題設定が秀逸で解いていて楽しかったです。一番思い入れがあるのはAHC047ですね。
コンテスト後はいつも他の参加者の参加記を読んでいました。上位の方が書いたものから自分と同じくらいの方が書いたものまでいろいろ読みましたが、どれも読みごたえがあっておもしろかったです。下位でも上位の方の参加記を理解して楽しめるのはAHCの魅力の1つだと思います。
座標を扱う構造体を定義する
以前は2次元平面上での座標を扱うときに<pair<int, int>>を使っていましたが、コードが煩雑になっていたので構造体を定義しました。もっといい方法があるかもしれません。
struct Coord {
int x, y;
auto operator<=>(const Coord &other) const = default;
};
こんな感じで使えます。
Coord target;
cin >> target.x >> target.y;
乱数を使えるようにする
uniform_int_distribution - cpprefjp C++日本語リファレンスを参考にして、ランダムな整数・小数を返す関数を用意しました。
乱数を使ってランダムな操作をするだけである程度のスコアが出ることがありますし、後述する焼きなまし法でも使うのであったほうがいいです。
random_device seed_gen;
mt19937 engine(seed_gen());
int rand_int(const int &a, const int &b) {
uniform_int_distribution<int> dist(a, b);
return dist(engine);
}
double rand_double(const double &a, const double &b) {
uniform_real_distribution<double> dist(a, b);
return dist(engine);
}
BFS・DFSを勉強する
AHC046で障害物があるときの最短経路の探索が書けなくて悔しい思いをしたので、何も見ずに書けるようにしました。多くの回で2次元のグリッドを扱うので、BFS・DFS（特にBFS）は各種アルゴリズムの中で最も勉強する優先度が高いと思います。
初めて学ぶ方はABC007Cがわかりやすくておすすめです。
焼きなまし法を勉強する
まだ勉強中ですが本番中に自分で実装できるようになりました。実行時間制限ギリギリまでリソースを使っているとヒューリスティックをやっている実感が湧きますね。ビームサーチより実装が簡単そうだったので先にこちらを勉強しました。
初めて学ぶ方は鉄則本（競技プログラミングの鉄則）の第7章かIntroduction to Heuristics Contestをやるのがおすすめです。
あわせて、配布されるローカルテスタの中のbin.rsからローカルテスタのスコア計算を盗めることを最近知りました。AHC047でスコア計算が実装できなくて焼きなまし法を断念したので、もっと早くから知っていればよかったです。
ABCに参加する
AHCにハマってからもABCには参加していました。D問題にはBFS・DFSが出ますし、短期コンではコードを書く速度も大事なのでABCも大事だと思います。最近緑色に近づいてきたので頑張りたいです！
おわりに
次は本番での青パフォ獲得を目標に頑張ります！
Discussion