RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)に参加しました！

こんにちは。今回、RECRUIT 日本橋ハーフマラソン 2023冬に参加し、暫定261位、ac-predictorの計算ではパフォーマンス1613とギリギリ青パフォを取ることができました。
(2/28追記)システムテスト360位と大幅に下がってしまいました。
初めてのヒューリスティックコンテストということで振り返りも兼ねてやったことや感想などを書いていきたいと思います。

アルゴリズム

まず、それぞれの家について最も近い水源を全探索します。その後、最短距離が最も短いものから繋いでいきます。掘り方はまずx方向に直進し、その後y方向に直進していくというシンプルなものです。このとき、掘るマスがそれぞれの家の現在の最短距離より短ければ、そのマスを最近傍のマスとして更新します。これをすべての家に対して行い、すべて繋がるまで掘ります。
掘るパワーに関しては、何も情報がない場合は初期値をCとし、n倍しながら掘っていきます。周辺の情報がある場合はそれらの情報を使って硬さの推定を行います。
具体的には、まず4近傍のうち、すでに掘られたマスの推定値の平均を取ります。その後、進行方向に対して1つ後ろのマスと2つ後ろのマスがすでに掘られていた場合、それらの差を平均値に足し、推定値とします。
この推定値より少し小さめの値で一度掘り、掘りきれなかったら更に小さい値で壊れるまで掘ります。最終的に壊れたときの値をそのマスの推定値として保存しておきます。

seed=2, W=4, K=10のときのビジュアライザーの様子は以下のとおりです。

反省

その硬さ以上のパワー、つまり無駄になってしまったパワーはだいたい全消費体力の5%、1つのマスを壊すのに2回以上かかってしまったときのC、つまり無駄になってしまった体力はだいたい全消費体力の3%でした。よって、全てのマスを完全に無駄なく1度で壊せたとしても、8%程度の短縮にしかならないということです。
そのため、これ以上スコアを向上させるためにはルートを工夫する必要があったのですが、うまく改善できる具体的なアルゴリズムが思いつきませんでした。
一応コンテスト中には主に以下の２つの方向で改善できるのではないかと考えていました。

最短経路にする

今回実装したアルゴリズムでは全体で見たときに最短経路にはなっていませんでした。例えば赤丸で囲んだところのように無駄な経路になっているところがあります。

ここを最適な経路にすることができればもう少し改善できたのではないかと思われます。

遠回りでも柔らかいマスを通る

今回は硬さは無視して最短経路を通っていました。しかしCの値にもよりますが、硬さが4000のマスを1回通るのと、10のマスをたくさん通るのでは大抵の場合後者のほうが消費体力が少なくすみます。ただ、今回柔らかいマスを通る方法がわからず、結局できるだけ短い経路を通るようにしました。
アイデアとしては、真っ直ぐ掘りながら硬そうなマスに当たったら逸れる、硬さはパーリンノイズで生成されていることを利用して適当な点をサンプリングして全体の硬さを推定するといったことを考えましたが、どちらもうまくいきませんでした。

(2/28追記)
システムテストで大幅に順位が下がってしまった原因ですが、恐らくたまたま本番データにあったパラメータを引けていただけのようです。
手元のデータとサーバーのデータどちらを信じるか迷ったのですが、そもそも手元でも100件のデータでテストしていただけなので、どちらにせよいい結果は取れていなかったように思います。次回からはもっと大量のデータを用意してテストするようにしたいと思います。

時系列順でやったこと

ここからは時系列順でどういったことをやっていたのか、考えていたのかを詳しく書いていこうと思います。

2/18 得点:16107494

まず、問題を読んでテスト環境を整えました。
その後、まず各家から最も近い水源にx方向に直進→y方向に直進で掘り進めながら最近傍のマスを更新していくという方法を実装しました。このときのパワーは毎回Cを初期値に、どんどん2倍にしていくという方法を取りました。
意外と高い順位を取れてワクワクしていました。

2/19 得点:10014342

家から水源まで繋げるのを順番にやっていたのを、最短距離順にソートして最も近い家からやるように変更しました。また、壊すのにかかったパワーを記録し、その情報を使って硬さを推定するようにしました。
これにより得点を2/3程度にまで改善することができました。

2/20 得点:9298027

この辺りから停滞し始めます。
壊れるギリギリのパワーを記録して推定に用いたり、パラメータ調整をしたりして少し得点は伸びましたが、大きく改善することはできませんでした。

2/21 得点:9260889

どんどん順位が落ちていきます。
直進するのではなく、直前のマスの硬さに応じて確率的に曲げたりしていましたが、いい結果が出ず、結局パラメータ調整をしていました。

2/22 得点:8759910

グリッド系のアルゴリズムを調べたり、最短距離が短い順ではなく長い順にやってみたり色々やりましたが全く改善できませんでした。
ただここでいいパラメータを見つけちょっとだけ得点が伸びました。

2/23 得点:8759910

少しアルゴリズムを変え、各家から一番近い水源または家に繋げるようにしました。ただしこのアルゴリズムでは水源とつながらない場合があるので、繋がっている家同士をグループ化し、水が通っていないグループから一番近いグループに向けて繋げて終了というアルゴリズムを実装しました。
その結果手元では4%ぐらい改善したのですが、提出したら結構悪いスコアが出てしまいました。掘るマスは減っていたのですが、スコアが悪化したのはやはり硬さを考慮していなかったからであると思われます。

2/24 得点:8759910

今更ですがテストツールを改造し、掘るマス数、無駄になったパワー、Cよって消費された体力、2回以上かかったために無駄になった体力、壊したマスの硬さも見れるようにしました。このときの最善の結果が以下のとおりです。

総コスト: 21686956
総距離: 47905
超過したパワー: 1163860
Cによる消費体力: 2343458
2回以上かかって無駄になった体力: 673202
総硬さ: 18179638
WA: 0

これを見て、無駄になっている体力は全体の8%程度であり、推定の精度を高めたとしても最大で8%しか改善できないことに気づきました。
ここで硬いところに当たったら曲げるなどをしてできるだけ柔らかいところを通るようにしたのですが、全く改善できませんでした。
また、ここでOptunaでパラメータ調整したら得点が上がったというブログを見て回し始めました。

2/25 得点:8759910

できるだけ柔らかいところを通れるように、適当にサンプリングしてマップ全体を推定できないかと色々やってみましたが、結局難しくてうまく行きませんでした。
そして前日から回していたOptunaの結果を代入して提出してみましたが改善しませんでした。恐らく過学習を起こしているのと、そもそもアルゴリズムが悪くパラメータを変えた程度では本質的な改善にはならないからであると思われます。
また結局システムテストでいい得点を得られるとも限らないため、細かいパラメータ調整がどれほど有効かはわかりませんが、やることもないのでとりあえず回していました。しかし最終的に手作業で調整したパラメータを超えるものはありませんでした。

2/26 得点:8759910

一応なにかできないか考えていましたが、何も思いつかず諦めムードでした。
そして最終的にこの記事の下書きを書きながら順位が落ちないように祈っていました。

感想

ヒューリスティックコンテストは初参加だったのですが、めちゃめちゃ楽しくて四六時中解法を考えていました。後半に失速してしまいどんどん順位が下がっていったのは悔しかったですが、逆に勉強のモチベーションがめちゃめちゃ上がりました。次回のAHCに備えてしっかり勉強しようと思います。