はじめに
アルゴ、ヒュ共に水色コーダーの私が、トヨタ自動車プログラミングコンテスト2024#6(AtCoder Heuristic Contest 034)にて、割と単純な解法で12位を取ることができたので、思考の変遷と解法を書いておこうと思います。(こんな高順位を取ることはもう無いと思うので…)
ヒューリスティックコンテストはアルゴリズムコンテストと毛色が違い、何となく敬遠している人も多いと思うので、単純な実装でも筋の良いロジックを見つけることが出来ると案外戦えるぞ!という事が伝われば嬉しいです。
※この記事では焼きなましもビームサーチも最小費用流も出てきません。ただの貪欲です。
問題について
詳細はAtCoderのサイトから読んでいただきたいですが、簡単に説明すると地面を出来るだけ最小の手間で平らにすることが目的です。
高い所の土をトラックに積み込んで、抉れている所を埋め立てる、というのを繰り返します。
以下のようなマス目上で赤色ほど地面が高く、青色ほど地面が抉れているイメージです。(余談ですが、問題を読んだ時に子供の頃巨人のドシンでひたすら地面を平らにしていた事を思い出しました)
解法の変遷
ここからは時系列順に解法を記載していきたいと思います。
15:05(コンテスト開始5分)
AHCが開催されていることに気づき、参加登録。
15:10(コンテスト開始10分)
ひとまず問題文を読み終わる。(これって「なにもしない」をすることでも点が貰えるのか?)と思いprint()とだけ書いたコードを提出、正の得点をとりあえずゲット。
問題文を自分の中で落とし込むも、どう移動するのがコスト最適か?と考えても方針が全く思いつかない。
積み込み上限も無い事だし、とりあえず時計回りに回って、足りなければ前方のマスから貰ってくるようにしてみるか、と実装開始。
15:51(コンテスト開始51分)
実装完了、提出。3.74Gのスコアを獲得。(この時の順位はあまり覚えていませんが60位前後だったような気がします)
ビジュアライザで動きを眺めていると、低いエリアでは何度も前方から土を積み込んでいるため、やたらと前後の往復をしているな、と気づく。
16:00(コンテスト開始60分)
何度も前方から貰ってくるために往復するのは無駄な気がしたので、前方と、右手側(時計回りで内側)どちらか都合の良さそうな方から土を貰ってくるように修正。
6.24Gのスコアを獲得。この時点で9位だったので、どうせその内落ちるし今の内だ、と嬉しそうにスクショを撮る。
16:18(コンテスト開始78分)
移動には定数分のコストがかかるが、積み降ろしには定数分のコストがないな、とふと思う。
手持ちが足りない場合で前方か右手側から取ってくる場合、とりあえず手持ちを降ろしてから取りに行くように修正、加えてどちらか判定するロジックを微修正。
6.27Gへスコア微増。
16:30前後(コンテスト開始90分)
あまり手持ちの重量が多いまま移動すると移動コストが無駄にかかるかな?と思い、150以上持っている場合内側に捨てる処理を追加するも、ローカルでのスコアが明らかに悪化したので提出すらせずにこの方針は棄却。
17:03(コンテスト開始123分)
開始地点が左上だけど、とりあえず四隅のどこかに移動してそこから処理を開始したほうが良い場合もあるかな?と思い実装。ついでに時計回りと反時計回りどちらにも対応。四隅スタート×2(時計回り、反時計回り)の8通りからの最善を選択する。6.95Gのスコア獲得。
17:32(コンテスト開始152分)
反時計回りにしたときの判定の最適化など軽微な修正をして7.25Gまでスコアを微増させる。
ビジュアライザを眺めてスコア改善できそうなエリアを探す。
以下心の声
(高い所と低い所を交互に移動するのが理想だよな~…時計回りか反時計回り固定だと、エリアの形状的に高い場所、低い場所、それぞれがしばらく続いてしまいがちか?角にぶつかる度、時計回り、反時計回りをランダムに切り替えるようにしてみればスコアが上がる気がする。)
18:47(コンテスト開始227分)
元の実装が悪いため、動的に時計周り、反時計回りを切り替えるにはどうしたらいいか1時間程悪戦苦闘する。普通に時間かけ過ぎでは?
1.7秒間ランダムに切り替えるパターンを探索し続けて、最もスコアが良かったものを提出するように修正。8Gのスコアを獲得。
18:58(コンテスト開始238分)
探索時間を1.87秒にする修正と、判定の最適化など軽微な修正をして8.4Gまでスコアを微増させ12位を獲得。
解法について
結局、ポイントは内側から取ってくるようにしたことと、曲がり方をランダムにしたことぐらいです。非常にシンプルですね。
ここからは妄想でしかありませんが、焼きなましやビームサーチなどのアルゴリムでは区間を決め、その区間内での最適化をする必要があるかと思いますが、区間の最適を全体の最適と結びつけるのが難しかったのかな、という気がします。
上位や、私より下位の方の解法でも、区間の最適化アルゴリズムが到底思いつけそうにない物ばかりで皆頭が良すぎる…と慄いています。
何も思いつけず、最初から最後まで乱数に身を任せた私が取って良い順位ではない気がしますが、ヒューリスティック初学者の方でも、運よく筋の良い解法が実装できれば高順位が取れる!という事を知っていただければと思います。