AtCoder の Heuristic で入黄しました！

はじめに

こんにちは、through です。

先日行われた AHC029 にて Heuristic で黄色になりました！Algorithm ではなく Heuristic ではありますが、晴れてずっとなりたかった暖色コーダーを名乗ることが出来るようになりました。つい最近 Algorithm の方で入青を達したばかり (今は水色に落ちてしまいましたが…) で、2023年終盤に色変を 2 回も出来てとても嬉しい限りです。

入黄に至るまでのレート遷移

Heuristic 初参加は 2021.12.12 の AHC007 で、競技プログラミングを始めて 2 週間足らずの競技プログラミングを始めたての時だったようです。当時は AHC の問題を AC することすら出来ませんでした…。ただその次の 2022.02.26 の AHC008 にて青 performance を獲得することが出来、AHC にハマっていきました。

成績表を見たところ、自分の AHC の parformance 上位 5 位は全て 2023 年に参加したコンテストでした。きちんと実装力が上がっているのが垣間見えて嬉しいです。

performance 順の成績表の図

以下では、記録として黄色になるまでにしたこと、今後したい事、Heuristic の楽しいと思うところをさらしていこうと思います。

黄色になるまでにしたこと・感じたこと

自分が黄色になるまでにしたことは、時間リソースを使った手法の習得 です。

Heuristic の問題は、厳密解を求めることが出来ない問題において、条件に相応しい解法を出した人の勝ちです。その為実行制限時間内であれば出来るだけイテレーションを回して、良い解を探索するのが自明で良いです。

実際に自分が習得した時間リソースを使った手法は以下の 3 つです。

• 焼きなまし法
• ビームサーチ
• モンテカルロ法

これらが習得出来れば殆どの問題で戦うことが時間リソースを使って戦うことが出来るようになると思います。習得したと言っても練度は上位の方より遥かに劣るので、橙色になるには問題に相応しい応用の仕方を会得する必要があると痛感しています。

しかしこれらを習得しないと Heuristic で戦えないのか、というとそうでもないです。これらのアルゴリズムを知らなくても、問題の核を得たルールベースの解法を実装するだけで黄色や橙色になることは出来ると思います。実際に自分は AHC026 で的を得たルールベース解を作成しただけで黄色後半 perf を取得することが出来ました。

よって、Heuristic において結局一番大切なのは、問題における重要な要素の考察 だと感じます。実際に頑張って時間リソースを使った手法でシミュレーション出来ても、いざ感想戦になると上位の方のルールベースに完敗することが多々あります (悲しい) 。ヒューリスティックで黄色を目指すにはこういった新たな手法を習得するよりも、まず上位の方の思考プロセスを学ぶのが意外と近道かもしれません。

焼きなまし法がうまくいかない時の考察

個人的には焼きなまし法が好きで、習得したものの中では得意です。実際のコンテストで一番成績が良かった MCDigital プログラミングコンテスト2023 (AHC019) では焼きなまし法で 37 位になり 順位表 2 ページ目に入ることが出来ました。上位の実力者の方には全く及ばないですが、今自分が焼きなまし法を実装する時に心がけていることを記そうと思います。

それは 近傍・評価関数・初期解・焼きなましの温度の対応を想像する ことです。

そもそも焼きなまし法のベースに山登り法というものがあります。これは現在の解から少しずらした近傍を求めて、現在の解より近傍の評価値が良い時にその近傍に移る、という操作を時間一杯行う手法です。焼きなまし法はこの近傍に移る条件を緩和させて、評価値が良くない時でも確率的に遷移を許すことで多様性を確保しようという手法になります。

自分の場合、山登り法を実装した後に焼きなまし法に移すとスコアが落ちる or 変わらない ということが頻繁に起きます。経験的にこれは近傍・評価関数・初期解・焼きなましの温度等、それぞれ単体で良い案だったとしても対応関係が良くないです。近傍が大きすぎると焼きなました時にブレブレの解に変貌し、近傍が小さいと局所解にハマって結局山登りとスコアが変わらない、という風なことが起きます。

なので自分が焼きなまし法をする時はこれらの対応を頭の中で想像して考察を進めています。簡単な例で示してみます。例えば以下の評価関数があり、小さめな近傍で山登り法をすることを考えます。

ここで赤点から評価関数が高い方向に遷移する山登り法を実装すると以下になりそうです。

ただ右の山の方が高いのでそっちに行きたくなります。そこで右の山に移るようにするために、焼きなまし法にして良くない方向への遷移を許すと、以下の様になりそうなのが想像出来ます。

ただここで、以下のようなことが懸念されます。

• 焼きなまし法の良くない方向への採用確率が高すぎたり、近傍を大きく取りすぎたりして、一回右の山に移ったのにまた左の山に戻ってきてしまうことが多い
• 焼きなまし法の採用確率が低すぎて、そもそも一回も右の山に移れてない
• 評価関数の緩急が激しい・局所解が多すぎる等の原因で、遷移がうまく進まない
• 初期解 (最初の赤点) がはるか遠くの離れたところにあり、変な場所でスタックしている (初期解が雑過ぎるとそもそも山登り法すらうまくいかない時がある)

こういうことが起きないように適切な近傍・評価関数・焼きなましの温度の対応が重要だと思っています。実際の評価関数や近傍は例のような簡単な関数では表せず複雑なので、具体的に想像することは難しいです。しかし焼きなまし法がうまくいかない時は、根底にこれに似た現象が起こっている可能性があるという推測が必要だと思っています。自分は大まかにこういう想像をして、出来るだけ評価関数の最高地点に到達する為にはどういう近傍や評価関数等が必要かを考えて調整するとうまくいくことが多いです。

「焼きなまし法が全然出来ない…」という方はこういう意識をするとうまくいくことがあるかもしれません。

今後したいなと思った事

クラウド上でのテスト並列実行

自分はテストケースを回す時、ローカル環境で適当にシェルスクリプトを書いて 20 ~ 30 分かけて数百ケースを回すというとても非効率なやり方で行っています。しかもローカルの処理性能がジャッジ時の性能より遥かに劣るので提出したらスコアが想定より上下することが多く結構戸惑います。クラウド上でテストを回すと数千ケースが数十秒ほどで終わるらしいので、今後橙色を目指すうえでやっておくべきかなと思います。

Optuna を用いたハイパーパラメータ最適化

現在は手動でお気持ちパラメータ調整をしています。これはダメですね…。世には便利な Optuna というハイパーパラメータを効率よく探索してくれるフレームワークがあるので、今後はこれを利用して空き時間にパラメータ調整を行うようににしたいと思いました。

https://optuna.org/

Heuristic のどこが楽しい？

自分は競技プログラミングを始めてからほとんどの Heuristic のコンテストに参加していますが、何が楽しくてハマったのかをまとめてみました。

ビジュアライザ

Heuristic と言ったらビジュアライザです。最近の問題では自分の解法を視覚的に見ることが出来るビジュアライザを問題と一緒に提供してくれているので、気軽に自分のプログラムの挙動を確認することが出来ます。特に web 版のビジュアライザは多機能 & 使い方が簡単で、自分がプログラムを作ってその出力を張り付けるだけです。ビジュアライザを見て想定通りの挙動を示してくれた時の楽しさはひとしおです。上位の方はよくコンテスト中に自作している方がいて、いつかは自分も自作ビジュアライザを作ってみたいなーと思っています。

個人的には Seed = 0 の結果だけ共有 OK というルールの時のコンテストがとても楽しかったので、またそういうコンテストが生えることを祈っています。

歴代の Visualizer 達

感想戦・公式解説放送

Heuristic のコンテストが終わると、X のタイムラインで色々な方が解法を出し合う感想戦が活発になります。Heuristic は自由度が高いコンテストであるが故に、人それぞれの解法があって他の方の考察を見るのがとても楽しく、色々な気付きがあります。

また公式解説放送では思考の順を追って説明してくれたり、度肝を抜く解法を解説してくれたりします。特に印象深いのは以下の AHC016 の解説放送で、実際にこの放送を見られた方は満場一致で度肝を抜かれたと思います。楽しいです。

誰でも参加記を書いて解説に残せる

通常 Algorithm のコンテストでは解説の作成にレートの条件が課されています。例えば AtCoder Beginner Contest ではレートが 2000 以上にならないと解説作成が出来ないようになっています。

しかし AtCoder Heuristic Contest の場合はレートの制限が一切なく、様々な順位帯の参加者の記事を見て考察を知ることが出来るので凄く面白いです。是非皆さん参加記を書いて下さい！(他の人の参加記を沢山読みたい人)

誰でも解説作成が出来、色々な人の参加記事を見ることが出来る

スポンサーからのグッズや景品

他のコンテスト同様に、企業さんがスポンサーをしているコンテストの場合は大体順位に応じてグッズや賞金が用意されています。そして Heuristic は参加人数が少ないこともあり、それらを取得出来る可能性が他のコンテストより遥かに高いです。

通常自分のレベル帯では、賞金やグッズは一度も取得出来てなくてもおかしくないですが、Heuristic のおかげで今まででグッズや賞金をそこそこ頂いています。嬉しい限りです。景品は T シャツとかタオルとか、Algorithm コンテストではあまり提供されないものもあります。競プロer が集まる場でこういうコンテストの景品を持っていくと結構うけます。

終わりに

数理最適化とか、機械学習とかを大学で研究しているぐらい強くないと黄色にはなれないんだろうなーと 1 年前に入青した時点では思っていましたが、結果的にそんなことはなく、無事黄色になることが出来ました。とても嬉しいです！

個人的には貪欲法を突き詰めるより、コンピュータの計算能力を活かしたシミュレーション、期待値計算等によって自分の想定を超える挙動を示した時に『Heuristic 最高！』となります。Algorithm とは違った嬉しさが込み上げてくるので、Heuristic に抵抗がある方も一度自身の考察をプログラムに起こせるまで粘って参加してみてください。

次は橙色ですが、ここからは流石に何か尖った武器が無いと修羅の道になりそうです。しかし Heuristic は単調非現象型のレートシステムなので、少しづつ上げていつかは橙に届くように精進していこうと思います！

ここまで読んでくださりありがとうございました！