お久しぶりです。西村です。業務に追われ気味でAtCoderのアルゴにはほぼ出られておらず、ヒューリスティックコンテストもしばらく勝てていなかったのですが、AHC046にて、久々にいい順位をとれたので、記事にまとめようと思います。

ところで、先週は火曜日に新型コロナの感染が判明し、火曜水曜は高熱に苦しみ、木金は在宅でゆるめにお仕事をしておりまして、社のメンバーにはご迷惑をおかけしたことを謝っておきます。そんなこんなで脳の疲労が溜まっていない状態でコンテストに参加したのが勝因だったのかもしれません。しらんけど。

問題概要

20×20の碁盤の目があり、1～40の番号がランダムに配置されている。最初、１のセルにいるので、2→3→・・・→40の順で巡回せよ。移動方法としては、歩く、滑るがある。歩くでは4方向に接するセルに移動できる。滑るでは4方向に壁の手前まで移動できる。移動以外に、自分がいるマスの四方に接するセルに壁を作る・削るの操作もできる。

問題を見て考えたこと

まずは貪欲を考える。ひたすら歩く実装は簡単だ。滑ったほうがいい時は滑ろう。とりあえずそこまで実装だ！

歩く実装

https://atcoder.jp/contests/ahc046/submissions/65205159

ひたすら歩くだけの実装です。歩く実装を提出するのに25分もかかっているのは、ローカルの実行環境を整えたりしていたためです。pahcerはPHPの公式サポートないですが、一応プロ（業務プログラマー）なので、そのあたりを適当に書き換えてPHPでテストするぐらい簡単です。（25分かかってるけど）

この実装で、パフォ638相当です。容易な改善（↓の滑るやつ）が残っているので、パフォ辛めです。

滑る実装

https://atcoder.jp/contests/ahc046/submissions/65205516

壁をいい感じに設置して・・というのは難しいですが、元ある4辺の壁を使って手数を削るのは割と簡単です。初期壁しか存在しない世界では、上下と左右は独立して考えることができるので、まずは上下の座標を合わせる、次に左右の座標を合わせると考えるとちょっと楽です。壁まで移動してから戻る方がいいのか、直接歩いていく方がいいのか、場合分けして処理すればおっけーです。アルゴ茶色ぐらいあれば4時間以内に十分実装できるはずです。

この実装で、パフォ1119相当です。緑パフォですが、ヒュは終了直後で+150換算されるので、これぐらいの提出を継続していけばぎりぎり水色に入れるラインです。歩く実装から10分で出来てるのはさすが青コーダー（アルゴ）ですね。

BFSにする

https://atcoder.jp/contests/ahc046/submissions/65207811

滑る実装をBFSに書き換えました。この書き換えでは1点も上がりません。でもめっちゃ重要です。1つ手前の滑る実装では、壁を追加した場合の対処ができません。今いるセルを決めると次のセルは、1マス上、1マス下、1マス左、1マス右、壁に当たるまで上に行った場所、壁に当たるまで下に行った場所、壁に当たるまで左に行った場所、壁にあたるまで右に行った場所の最大8か所になります。現在地をQueueにでも入れてBFSすれば、壁を適当に追加したマップであっても、次の目的地までの最短移動距離が求まります。あとは経路復元するだけですね。面倒ですね。頑張りましょう！幸い、ヒューリスティックコンテストはAIつかってOKなので、AIバリバリ活用して実装したら1時間でBFSになりました。はい、時間かかりすぎですよ！青コーダーさん（アルゴ1607で次でたら落ちそうです・・）。

この実装でパフォは改善せず（それはそう）、パフォ1119相当です。

初手で適当に壁を足す

https://atcoder.jp/contests/ahc046/submissions/65208264

初手で壁を1個だけ足す実装をしました。厳密にいうと、最初の座標が上端でなく、最初の座標の上のセルが目的地になっていない場合に壁を設置するという処理を追加しました。壁を1個置くだけでうまくいくのか？？？？と思われるかもしれませんが、直前の提出にてBFSで最短経路を通る仕組みはできているので、適当に壁を作っとけば使えるときにいい感じにつかっていい感じになります。なりました！

これでパフォ1424相当です。1個でなく、2個、3個、と置けば上がりそうだし、いろいろやれそうな感じしますよね。もちろん改善します。

もろもろ改善する

https://atcoder.jp/contests/ahc046/submissions/65210068

上に置けなければ下に置く、14手目までは壁を置けたら置く、壁を置く場所を現在地の上下左右を試す、壁を置くのをターン数ではなく壁の個数で制御する（12個まで置く）、壁の近くには壁を置かない（マンハッタン距離で4あける）、などという小細工をがちゃがちゃやりました。いわゆる貪欲の改善みたいなやつですね。ビームとか焼きなましとかやる前に、貪欲いろいろ試しとくのは悪くないです。（そもそもどうやってビームに持ち込むのか見えてなかった・・・）

これで、パフォ1621相当まであがりました。これぐらいやれればヒューリスティック青になれます。なりましょう！

ビーム！！

https://atcoder.jp/contests/ahc046/submissions/65210376

何もわかってませんでした。上記のコードをビームサーチにできるのか理解できていませんでした。でも、ここはAI様にお祈りすれば何かやってくれそうな気がしたので、雑なお願いをしたところ、ビームサーチの実装が与えられました。神様ありがとう！

ビームサーチにしたらめっちゃ得点あがるかも？？という期待は裏切られ、パフォ1651相当のスコアになりました。渋い。

高速化！！！

https://atcoder.jp/contests/ahc046/submissions/65210831

ビームサーチはビームの太さがモノをいいます。太い方が強いです。ぶっといビーム撃ちたいです。ということで、PHPからC++へ書き換えです。o3神が3分で書き換えてくれました。ありがとう。ビームの太さは15から400になりました。太いです。

$beamWidth = 15; //before
const int BEAM_SIZE = 400; //after

高速化した結果、パフォ1882相当のスコアまで上がりました。

そういえば壁の配置が決まったらその後の手数決まるよね。得になるときだけ壁置けば？？

とか思ったけど、実装面倒だよね。面倒。1時間ぐらいつぶしそう。厳しい。

神様にお願いしたら、実装が与えられました。やったー！

https://atcoder.jp/contests/ahc046/submissions/65211321

いい感じの時だけ壁を置くように変えたところ、パフォ2131相当にあがりました。

ところで目的につくまでの途中経路で壁置いたほうがよくない？

とか思ったけど、実装面倒だよね。無理。時間内に実装できんて。

神様にお願いしたら、実装が与えられました。なんか1桁以上重くなったけど、ビームを9まで絞ったら通りそうだったので、投げました。AC！

https://atcoder.jp/contests/ahc046/submissions/65212001

えっ、30位？！パフォ2510？！

そんなこんなで、過去最高の30位、橙パフォを獲得し、GP30ポイントも0.5だけですが獲得できました。

まとめ

前半は割と手で実装していたのですが、途中からはAIとがっつりタッグを組んで改善を進めました。4時間という限られた時間でしたが、o4-miniよりはo3の方がいい結果が出るケースが多かったように思います。（同じ質問文をo3とo4-miniに同時に投げて、結果を評価したりしてました）AHCにおいて、AIはなかなか役に立たないという意見もよく聞きますし、実際にそう感じることも多いのですが、今回のAHCにおいてはAIを活用することで自らの能力を超えるレベルの成果を出せました。