2023/2/18〜2023/2/26に開催されたRECRUIT 日本橋ハーフマラソン 2023冬(AtCoder Heuristic Contest 018)に参加しました。
前回AHCでは、あまり大した考察もできずで中途半端な結果で終了となりました。今回は、前回の反省を踏まえて、早めに提出することと、諦めずに考察に取り組むことを心がけて臨みました。
参加します。今回で水色になれるように頑張ります。#AHC018
— devgenjin77 (@devgenjin77) 2023年2月18日
RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018） - AtCoder https://t.co/wtKv6jO4j0
今回の結果
確定176位でした！ヒューリスティックコンテストでは自己ベスト順位です。
さらに、今回のパフォーマンスは、なんと青色に到達！余裕で入水を達成できました。
青パフォ出ました😂
— devgenjin77 (@devgenjin77) 2023年2月28日
devgenjin77さんのRECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）での成績：176位
パフォーマンス：1801相当
レーティング：1148→1308 (+160) :)#AtCoder #RECRUIT日本橋ハーフマラソン2023冬（AtCoderHeuristicContest018） https://t.co/km0sx0lI6c
振り返り
今回は、結構時間を取って色々と試行錯誤しました。
A問題
実は、今回のAHCに備えて焼きなまし法の予習なんかをしていたのですが、問題をみてみると焼きなまし全然関係なさそうな雰囲気で、ちょっぴりショックでした。
しかしながら、こんなことでしょげててもどうしようも無いので、真面目に考察に取り組みます。
基本方針
10マス×10マスの範囲を１ブロックとし、マップ全体を縦20×横20の全体で400ブロックに分割します。因みに、各水源及び家同士は、マンハッタン距離で最低25以上は離れているという制約があるので、各水源及び家はそれぞれどこのブロックに入るかは一意に決まります。
次に、各水源から、水が到達していない家全ての組み合わせについてBFSで最短経路を求めます。そして最もコストがかからないと判断した水源、家のルートを繋ぎに行きます。
移動はブロック単位で行うこととし、かかるコストは各ブロックに属するマスの硬さの平均（壊れたマスに与えたパワーの合計÷壊れたマスの個数）とします。１度も壊していないブロックについては、中心マスを試掘することで硬さを推定します。
こんな感じの実装で、Seed=0の結果はご覧の通り。スコアは163636です。
工夫した点としては以下の通りです。
工夫１：掘り進めるパワーの上限を設定
最初いろいろ試してた段階では、水源と家の間に分厚い岩盤があると、ぶち抜いてしまい、大きなロスをすることが結構ありました。対策として、経路をBFSする時に使うパワーの上限をあらかじめ設定しておき、ルートが見つからない時だけ徐々に緩めていくという方式をとりました。
ただ、やり直しが続くとTLEの可能性もあるということで、上限は多くて9段階程度としています。
工夫２：Cの値によって、試掘するときのパワーを調整する
の値が上がると、叩く回数をどれだけ減らせるかがスコアに大きく影響すると考えたので、
の値に応じて試掘する際のパワー調整を行うようにしました。
ざっくりいうと、の値が小さい場合は、できるだけ小さいパワーで少しずつ試すように叩き、
の値が大きい場合は、初回から大きなパワーで叩きにいくという感じです。
この修正を加えてみると、相対スコア的には結構伸びがあったので、結構有効な方法なのかなというところです。
ただ、今回作ったパラメータは大分適当に手作業で決めたので、大きな改善の余地がありそうです。
工夫３：最初に家と水源の周辺を試掘する
水源と家の周りは、比較的弱い岩盤になるはずということで、初回に各水源と家の周り、ブロックにしてマンハッタン距離３つ分を試掘しました。
実装を進めていくうちに、この工夫が結果にどの程度影響するか不明だったので、途中何回も消してテストしたりしたのですが、どういうわけかスコアが悪化したので、結局残しています。
工夫４：水源と家を掘り進める場合、初回に使うパワーをブロック内平均に近づける
場所が近い所の地盤硬さはほぼ同じかなという発想から、岩盤を掘り進めていく場合のみ、初回に使うパワーをブロック内平均に近い値を採用することにしました。
これで、叩く回数自体は減ったかというところでしたが、結果的には大した伸びはありませんでした。
最終提出コード
https://atcoder.jp/contests/ahc018/submissions/39276814
振り返り
コンテスト終了後、他の解法などを確認してたら結構改善点が見えてきました。
ブロックのサイズを10×10とすることに固執しすぎてました。上位陣の解法ではもっと大きいサイズで切っているやり方もあったので、もう少しブロックのサイズを変えながら試してみた方がよかったかもしれません。
上位の解法と比べて、試堀する場所が無駄に多いような感じがします。BFSで全ブロックを探索し最短経路を求めるようにすることで、かなり迂回しないと最善経路に行けないケースには対応できたようですが、他のケースでは結構無駄な試掘も行っているので、探索の精度を上げる余地はあるかと。
パワー調整のパラメータは、かなり改善の余地がありそう。あとはどうやって改善すればいいのかなあ？Optunaなんてのも使えるようだが、よくわかってません。
これまでの実績
ヒューリスティックの方は入水達成！ここで満足せず、引き続き上の色を目指してきます。
総括
今回は、ある程度時間をかけて試行錯誤したことで、これまでより良い結果が出せたのかなあというところですが、反面上位陣のレベルの高さも思い知らされた回でした。
ここから、どうすれば上に行けるか。とりあえず、AHC過去問の上位解法などを勉強して、上位を狙える実力をつけたいと思います。
ということで、また次回も頑張ります。
