この記事は AtCoder Heuristic Contest (以下 AHC) などの heuristic 型のプログラミングコンテストに参加したことがなかった 私 が AHC 初参加までにやったこととやっておけばよかったことをまとめた記事です。AHC に興味があるけれど、どうやって始めたらいいかわからない方の参考になれば幸いです。
やったこと
AtCoder Clans の入門者・初心者向け記事を読む
競技プログラミングに関することを調べるには AtCoder Clans が便利です。幸い、AtCoder Clans には ヒューリスティック問題を解く というページがあり、heuristic 型の問題に関する記事が列挙されています。
手始めに以下の 2 つを除いた入門者・初心者向け記事を軽く読みました。
この 2 つについては実際に問題に取り組みながら読んだ方がよいだろうと思って、とばしました。
入門者・初心者向け記事に目を通して、なんとなく heuristic 型のコンテストの雰囲気を掴んだつもりになりました。
Introduction to Heuristics Contest をやってみる
Introduction to Heuristics Contest をやってみました。初めにこの問題を選んだのはコンテストのページの「Introduction to Heuristics Contestとは」を読んで初めて取り組むコンテストに良さそうと思ったためです。
最初にこの問題に取り組んだのは正解でした。入門者向けのガイド付き問題である B 問題と C 問題があるため、A 問題で手が止まっても、B 問題や C 問題の誘導に従って正の得点を得るプログラムを提出しやすいと思います。また、解説も入門者向けに単純な解法から順に記載されているため、少しずつ読み進められて消化しやすいです。
以下では問題の解法について少し言及します。Introduction to Heuristics Contest を初見で楽しみたい方は飛ばしてください。
この問題に対して私がやったことを時系列順に列挙します。
- A 問題に取り組む (1 日ずつ貪欲法) 。
- A 問題に取り組む (3 日先まで深さ優先探索 + 貪欲法) 。
- B 問題に取り組む。
- C 問題に取り組む。
- A 問題に取り組む (山登り法、変形操作の改善はできなかった) 。
- 解説の方法でプログラムを改善してみる (ビームサーチと巨大近傍法は読むだけ) 。
初めに B 問題や C 問題を見ずに思いついたことをやってみて、B 問題 C 問題を読んだ後、再び A 問題に取り組み、最後に解説の方法を真似してみました。
前述した感想の他には以下の感想を持ちました。
- 処理が速いと解の探索範囲が広がり点数が上がる可能性が高まるため、ABC と比べて速度の改善を追求し続ける必要がありそう。
- バグがあっても答えは出てしまうため、プログラム全体の設計や単体テストの実装など、バグを埋め込まない工夫が必要そう。
- 貪欲法の評価関数や局所探索法の解の更新方法など問題特有の性質を見極めることはまだ全然できなさそう。
やっておけばよかったこと
初めて参加したコンテストは AHC014 です。AHC014 に参加した際にやっておけばよかったと思ったことを列挙します。
Rust のビルド環境の準備
AHC014 で提供されるビジュアライザは Rust で実装されていました。Introduction to Heuristics Contest では Python 実装のビジュアライザが提供されたこともあり、Rust のビルド環境が手元になく、コンテスト開始後にインストール作業を行いました。
調べてみると少なくとも AHC011 から AHC014 までは Rust 実装のビジュアライザが提供されているようです。
今後も Rust 実装のビジュアライザが提供される可能性が高いと考えて、事前に準備してもいいと思います。
AHC 用開発環境
AHC014 のプログラムが ABC などの algorithm 型のコンテストのプログラムに比べて長くなりました。私の ABC のプログラムは 100 行程度ですが、AHC の最終提出プログラムは 700 行ぐらいでした。
競技プログラミングでは items2 で vim を呼び出してプログラムを書いています。デバッグも iterm2 から lldb を呼び出して行っています。ABC などでは特に問題はないですが、700 行ぐらいになるとプログラム全体の把握やデバッガの実行が大変でした。
また、制限時間内に良い解を探索するのが重要なため、定数倍の速度改善も行いたいのですが、AHC だとプログラムが複雑でボトルネックの発見も難しいです。プロファイラを準備していればなあとコンテスト中に思いました。
AHC014 中は環境を変えずに乗り切りましたが、次に AHC に参加するまでには開発環境を整えたいと思います。
結局のところ何を準備すればいいのか
大前提としてコンテストへの取り組み方は人それぞれだと思います。とはいえ、コンテスト中に全く手も足も出ない状態だとつまらなく感じる可能性があります。スコア改善のための何かしらの取り組みができるように以下の 3 つをお勧めします。
- (プログラミング未経験者の場合) レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 などに従って競技プログラミングのプログラムの書き方を身につける。
- Introduction to Heuristics Contest
- ABC の少し複雑な全探索やシミュレーションの問題や比較的簡単な貪欲法の問題を解く。
全くプログラミングをやったことがない方が AHC にいきなり参加するのは無謀だと思うため、競技プログラミングのプログラムの書き方を身につけることを 1 つめに挙げました。
Introduction to Heuristics Contest については前述しましたが、入門者向けのガイド付き問題があることや、段階を踏んで手法を説明してくれる解説があるため、お勧めです。また、AHC014 参加後に思ったこととして問題設定もシンプルで入門によいと思います。
ABC の問題を解くことについて補足します。
AHC014 に参加した感想として、コンピュータに実行させたいことを実装する力が必要だと感じました。その力を鍛えるために ABC の問題を解くのがいいのではと考えています。とくに少し複雑な全探索やシミュレーションの問題や比較的簡単な貪欲法の問題が AHC に近いと思うため、これらの問題を中心に解くことをお勧めします。
ただ、「少し複雑な全探索やシミュレーションの問題や比較的簡単な貪欲法の問題」というのは私の感覚をなんとか言葉にしたもののため、イメージしている問題を正しく表現できていない恐れがあります。そこで、以下に ABC272 以前の ABC からいくつか私のイメージに合致する問題を列挙しました。
- B 問題
- C 問題
- D 問題
解く問題を決める指針になれば幸いです。
上記の 3 つのお勧め以外にもやったこと・やっておけばよかったことを挙げていますが、それらはコンテスト中に必要になってから調べながらやればいいかもと思っています。
AHC に 1 回しか参加したことがない人間が勧める方法ですが、参考になれば幸いです。
