HACK TO THE FUTURE 2024(AtCoder Heuristic Contest 027)参加記

2023/12/1〜2023/12/10に開催されたHACK TO THE FUTURE 2024(AtCoder Heuristic Contest 027)に参加しました。

ここ最近のAHCでは、ギリ水パフォか緑パフォを取ってしまうことが多く、自分の実力の無さを感じている状況です。

AHCは結果が悪くてもレートが下がらないので、なんとか青コーダーの地位を確保してますが、そろそろレート以上のパフォーマンスを出していかないとというところ。今回は青パフォ以上目指して挑んでみます。

参加します。最近、AHCの結果が悪いので、今回はレート以上のパフォを出したい。

HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027） - AtCoder https://t.co/umzqY13pNb
— devgenjin77 (@devgenjin77) 2023年12月1日

今回の結果

26.7Gの484位で終了。今回も残念な結果になりました。

パフォーマンスは、ギリ水色という結果。前回は１上がりましたが、今回は２上がりました。

何もできず終了。。

devgenjin77さんのHACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）での成績：484位
パフォーマンス：1247相当
レーティング：1619→1621 (+2) :)
Highestを更新しました！#AtCoder #HACKTOTHEFUTURE2024（AtCoderHeuristicContest027） https://t.co/XFAvNwf1gm
— devgenjin77 (@devgenjin77) 2023年12月11日

振り返り

今回も、初手の方針につまづいてしまい、スコアの改善もままならぬ状態となりました。

A問題

A - Recurring Cleaning Route

今回の方針の概要です。

#AHC027 #HTTF お疲れ様でした。
26.7Gで最終484位でした。。
サンプルで作った初期解を元に、早く１周が完了することを目標にしてみましたが、ハズレ方針だったようで、早い段階でスコアが頭打ちになってしまいました。
（添付：Seed=0 Score = 2550634）
また、次頑張ります。 pic.twitter.com/JXJplHPMPa
— devgenjin77 (@devgenjin77) 2023年12月11日

今回の問題は、ロボット掃除機を部屋中全てのマスを掃除するよう操作して、最終的に平均の汚れを少なくするという問題。

まず、部屋中全てを掃除する制約があるので、初期解を作るのも中々しんどそうだという印象。コンテスト開始より、初期解の構築に結構悩みながら実装が進まないという時間を過ごしていました。

しかし、そんなことしてるうちに、残り日数も徐々に少なくなって来たので、とりあえずサンプルのDFS実装をJavaに移植して１度提出。そして、ビジュアライザでサンプルの実行結果を観察してみると、汚れの少ないマスについてDFSの戻りターンでも清掃してるため、他の汚れが大きいマスで汚れが累積することが結果に悪影響を与えているのでは無いかという考えが浮かびました。

ということで、可能な限りDFSの戻りターンで形成される経路を省略できるような実装にし、全体として短いターンで１周回ることができるようにすればスコアが改善するのでは、と実装してみたら、予想通りスコアは改善されました。

が、、その後の改善アイデアが全くダメ。。経路を乱択にしてみたり、汚れの多いマスを２回回るようにしてみたりしてみましたが、スコアが改善の方向に向かわず、逆に悪化するばかりという状態に。。

最終日まで、このような状況から抜け出せなかったので、結局、一番スコアの良かった、なるべく早く１周する実装で最終提出とすることにしました。