RatedのAHCに初めて参加してみました

こんにちは、regiです。

先日初めてRatedのAtcoder Heuristic Contest(AHC019)に参加してみました。

結果は786人中104位となり、初参加にしてヒューリスティック緑になることができました！

この記事では、私がAHCに初めて参加するにあたって、やって良かった点や反省点などを半ば日記形式で書きました。なお、今回の知育パズル問題の取り組み方に対してという意味合いよりも、ヒューリスティックコンテスト自体の取り組み方に対してという意味合いの方が強いため、その問題概要や具体的な解法などはあえて一旦書くのをやめておきます。

そもそもなぜAHCに参加することに？

私自身はもともと前々からヒューリスティックとそのコンテスト自体には興味がありましたが、なんやかんや学業やICPCなどで時間を取られていたため、今までなあなあにしてしまっていました。しかしながら、それらも1~3月に落ち着き始めたため、そのタイミングで試しに初めてヒューリスティックについて本格的に調べて触れてみたら…そのままハマってしまいました。その流れで、「ヒューリスティック面白いからコンテストにも参加してみたい！だから次のAHCに参加してみよう！」と強く思うようになり、AHC019に参加してみたというわけです。このようにしてAHC019に参加することを決めたのは、その開始日の2週間ほど前だったと思います。

コンテスト開始前の私はどうだったか

コンテスト開始日の2週間ほど前の私は以下のような状態でした。

「モンテカルロ法とかは大昔になんちゃって実装をしたことがある程度で、MCTSは1ミリも知らない。ビームサーチや焼きなましは薄らどういうものかは分かるけど…具体的な処理とかはよく知らないし、当然実装も1ミリもやったことない。」

(↑初心者丸出しです。)

「この状態ではAHCに参加したとしても、なんちゃって実装しか出来ないまま終わりそうだ…。」という危機感を持ったため、急いでそのビームサーチや焼きなましなどの手法について書かれた記事を読み漁ってみると、焼きなましを最初に完璧にしておくと良さそうであることが分かったので、まずはその焼きなましを真っ先に学ぶことにしました。焼きなましに関して、具体的な操作を理解することや、局所解にハマらないようにするための考え方については比較的容易に理解を進めることは出来ましたが、その焼きなましの基本的な実装方法と、「どうすればそれを実際にAHCの過去問などで上手く使うことが出来るのか？」を考えることとの2つにおいて個人的に大きな壁を感じました。

まず、焼きなましの基本的な実装方法については、私自身がC++における乱数実装やchronoについてあまり知識がない状態だったからということもあり、C++でどのように実装するべきかを知るために頑張って記事を漁りましたが、あまり私に合うものはありませんでした…。最終的には、同じ大学の方のAHCの過去提出コードを参考にする形で書くことで事なきを得ました...。

そして、それよりも遥かに問題となった「どうすればそれを実際にAHCの過去問などで上手く使うことが出来るのか？」を考えることについては、ヒューリスティックコンテストが強い方の参加記を読み漁ることで、少しずつ出来るようにしていきました。この時点ではまだ少しでしたが…。

そのように精進していった結果、コンテスト開始日の1週間ほど前にAHC012にて初めて焼きなましの実装と実行に成功しました…！

ちなみにコンテスト開始日の1週間ほど前から開始日までは、ずっとCodinGameの過去問にてMCTSの実装を頑張っていました。誰かMCTSの高速化についての記事書いてください…どうしても分からないんです…。AHCで使うことはあまり考えていなかったため、本当にちなみにです。

コンテスト中の私はどうだったか

当然ながら初日から意気揚々と問題を見にいき、その文章を隅から隅まで丁寧に読みました。しかし、何も分かりませんでした。そのまま初日は何一つ良い発想が降ってくることはなく、「ヒューリスティック初心者が長期コンの問題でまともな方針を立てられるわけありませんでした…。」と諦めそうになりました。これはまさに前述の通り、「どうすれば焼きなましを実際にAHCの過去問などで上手く使うことが出来るのか？」を考えることが全く出来なかったというわけです。そのような感じがしばらくだらだらと続き、コンテストの最初の1週間は半ば放心状態でCodinGameでMCTSの実装を進めつつ、AHCも少しずつ考察を進めていくという状態でした。

なんとかしてこの状態から抜け出すために、過去のAHCの上位の方々の参加記を更に読み込むことにしましたが、これをしたことが後々かなり役立ちました。具体的には、例えばterryさんのAHC013の参加記から「近傍を複数採用する」や「破壊してから再構築する」というアイデアを得ることで、大きくスコアを伸ばすことができました！その過程の中で「こういうふうに今の解と近傍解との評価値の差がなだらかになっていって、焼きなましが局所解にハマりにくくなるのか…。」ということを直感的ではありましたが実感することが出来たので、焼きなましにおいてそれを意識することの大切さを私自身のコードからも学ぶことができました！

また、他にも多くの参加記を通して得た更に大事なこととして、「どんなに強い方でも100%理論のみで勝負しているわけではなく、理論でははっきり分からない部分はとりあえず書いてみることに重きを置いている傾向にありそう」ということを知ることができました。実のところ、この部分は私自身かなり誤解していまして、「強い方々はもう初日から理論的に確実な手法を採用して、残りの期間では微調整などに専念しているのだろう」と無意識に考えていたため、「最初の1週間で理論的に確実だと思われる方針が何も立たない自分はなんて情けないんだ！」という気持ちに支配されていました。ヒューリスティックにおいて、この考えは命取りだったと…今は思います。もしかすると、初参加から順調にスコアを伸ばすことができたのは、この考え方に改めることができ、それを意識してコンテストに取り組むことができたおかげなのかもしれません。

結果は良かったとはいえ、それでも反省点の方が多かったのも事実で、私のローカル環境は今回のAHC019において、スコアを効率良く上げていくための環境とはとても言える状態ではありませんでした…。具体的には、サンプルは一括処理することが出来ないからいちいち全部手打ち、optunaが使えないからハイパーパラメータは全部雰囲気で決定、ローカル環境のCPUが遅いからAtCoderのコードテストでデバッグ、プロファイラも無いうえに私自身もC++はどの処理が遅いのかが把握出来ていないので、それをちまちま調べていくところから開始、などと…もしかしたらヒューリスティックコンテストの強い方々が見たら失神してしまうかもしれません…。ここを徹底するとスコア改善に掛ける時間も大幅に削ることができるだろうと思うので、ここもできる限り最適化していきたいですね…！

それに、bitboardによる高速化を知っていたのに試さなかったのは明らか怠慢であったため、その点も反省したいです…。

やって良かったと思うこと

・他の方の焼きなましなどの実装方法をコードを見て回ったこと

・ヒューリスティックコンテストが強い方々の参加記を、解法からその解法へと行き着いた過程までしっかりと読み込んだこと

・焼きなましの性能を上げるうえでの考え方について、しっかりと様々な記事を参考にしたこと

やっておけば良かったと思うこと

※コンテストまでに時間がたくさんあったわけではないので一部は仕方ないものもありますが、挙げるとしたら以下のようになります。

・optunaを使えるようにしておくこと

・高性能CPUを使えるようにしておくこと

・サンプルの一括処理を出来るようにしておくこと

・プロファイラを使えるようにしておくこと

・bitによる高速化の威力を知っておくこと

・実装法による実行時間の差異をある程度把握しておくこと

・ビームサーチ辺りを完璧にしておくこと

感想

正直、初参加では上位50%に入れればいいな程度に思っていたため、まさかパフォ1908を取って一気にヒューリスティック緑色になれるとは思っていませんでした…。このような結果となったのは、間違いなくしっかりと自分なりにヒューリスティックに継続して向き合えたからだと感じるため、本当に嬉しく思います。しかしながらヒューリスティックは奥が深く、やっておけば良かったことを考え始めると結構出てきてしまいました。これらにも向き合うことで、よりヒューリスティックの奥深さを堪能することができ、もっと実力も上げていくことが出来ると考えているため、これからもヒューリスティックを学んでいきたいです！良い問題をありがとうございました！