RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）参加記

30代後半から競技プログラミングを始めましたhimaと言います。

RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）に参加しました。02/18〜26までの9日間の長期コンテストです。

ヒューリスティックコンテストにはこれまで何度か参加していましたが、今回長い時間じっくりと取り組み、自分のレートより大幅に良いパフォーマンスが出せました。その記録を残しておこうと思います。

綺麗な解法というよりは、参加の日記のレベルです。ヒューリスティックコンテストの参考になれば幸いです。

 

問題

atcoder.jp

 

1日目

目標は正の点数を取得することと、ビジュアライザ等の開発環境を整備することにしました。

ヒューリスティックコンテストでは問題の理解と確認のため、はじめに問題の理解とその通りの解答がかけているかとりあえずAC(Accepted)されるコードを書いています。今回はインタラクティブな問題(解答コードが出力したものに対して、ジャッジプログラムからの入力を受け取る対話形式の問題)のため、ジャッジとの対話を確認も兼ねています。

各家から一番近い水源まで、L字のルートを描きながら適当なパワーで掘っていくコードを提出して、初日の夕方にひとまず正のスコアを得ました。

コンテストのテストケースで、絶対スコアが18835039でした。

あとは、手元でインタラクティブなジャッジ含めた動作確認ができるよう提出コードでは標準入出力、テストコードではテスト用のジャッジに値を渡す形にコードを書いてgo testコマンドで動作確認ができるように整備しました。

 

2日目

硬い岩盤を掘り進めるとコスパが悪いのが掴めてきて、なるべく柔らかい岩盤を掘り進めるように修正しました。優先度付きキューを使って試行錯誤していました。

無駄な掘削をしており、絶対スコアは25319332。初回提出の方が良かったです(今回のコンテストは絶対スコアが低い方が良いので)。

この辺りから、最短経路や経路探索のアルゴリズムについて調べ始めました。アルゴリズムのコンテストでは、ダイクストラ法、ワーシャルフロイド法、まれにベルマンフォード法を使っています。A*アルゴリズムというものを勉強する機会になりました。

コンテスト後に拝見した解放の中にはA*アルゴリズムを使用している方もおり、今回の復習など、合うところに実装を試してみたいと思いました。

 

3、4日目

3日目は仕事後に少しコードを改善して提出、20698072まで微改善しました。

4日目はお休みをもらってAHCに注力していました。

方針を変えて、予め岩盤調査を行った後に経路を考える方法に切り替えました。20*20の領域に区切って特定のパワーで掘り、岩盤が壊せた付近は比較的柔らかいだろうと推測して最短経路を繋いでいきました。

まだ実装に甘いところがあり、余計な掘削も取りきれず最終スコアは26745703。まだまだ進捗が出ませんでした。順位も、400位前後をうろうろしていました。

 

5、6日目

5日目は仕事のため手付かず。

6日目は祝日のため、再びAHCに注力していました。

余計な採掘を取り除き、絶対スコア9261310、200位台まで上がれました。

7日目

お仕事のため、進捗ありませんでした。

 

8、9日目

手元でパワーをいくつか変えながらテストケースを回して良いスコアが出ているパワーを選んだりしながら細かく順位を上げていました。

入力用のファイルには岩盤の固さがわかっていますので、それで答えに近い水の通し方やそのスコアを見ながら、解答コードが硬い岩盤を選んでいる経路の改善をしていました。

あらかじめ岩盤調査をしていたところが、01BFSで解くような道と壁になっていましたが、実際はもっとなだらかなギャップを埋める方法を探していました。

いろんな解説記事には、それに合う手法があるようですが、この時思いつきましたのは単純な画像のぼかしの方法で、それを適用してみました。

あとは、グリッド状に岩盤調査していたのをダイヤ型(サイコロの5の目とも言われますかな？)にポイントをあてて掘削も試しました。


後者(5の目状の岩盤調査)の方で、絶対スコアは6721084まで達成できました。が、相対スコアは前者(グリッド状の岩盤調査)の方が良く、最終的にこちらを提出しました。

9日目は何か改善したいと思いつつ、閃きがなく8日目の提出が最終提出となりました。

 

結果

最終提出の暫定順位が213位、システムテストの結果210位に入ることができました。

パフォーマンスは1719で、ヒューリスティックで最大のパフォーマンスを出すことができ、ヒューリスティックで入水することができました。

atcoder.jp

今年掲げていた目標も1つ達成することができました(あとはアルゴの方でも達成したいと思います)。

 

いくらか考察が不十分な点もあり、方針ガチャがたまたま当たったという説もあります。

今後も安定したパフォーマンスが出せるように、ヒューリスティックの勉強、コンテスト参加を続けていきたいと思います。