はじめに

HTTF2022 本選に出場して $39,888,259$ 点、全体 8 位・ユース枠 2 位を獲得しました！
ここまで取れると思っていなかったので嬉しいです！！

f:id:Anko_nasubi:20211218200543p:plain

問題概要

できるだけ短いコマンドでお掃除ロボットを動かしてね

考察

短い・操作数が多い・多くの範囲を掃除できるの 3 つを満たすようなコマンドが入っていると嬉しいので、手作業で最初に入れる用のコマンドを探していけば良いかなーと考えてました。
結果この方針が大正解でした。

最終的な解法

① 各マスから他のマスまでの最短距離を BFS で求める(このときのマス $i$ からマス $j$ までの最短距離を $d _{i, j}$ とします)
② 答えに x(y(LrrF)y(RllF)) を入れる
③ 次に向かうマスを、まだ掃除をしていないマスの集合を $S$ として、 $d _{現在のマス, i} - \sqrt{(\sum_{k \in S} d _{i, k}^2)/|S|}$ の値が最も小さいマス $i$ にする
④ ③の操作で移動したマスのうち、移動距離が $3$ 以上である場所で分割する
⑤ ④で分割してできた塊を、山登り法で移動距離の和がより小さくなるように並べ替える
⑥ ⑤での並び順に従って、なるべく F が連続するような・最短距離を通るようなコマンドを記録していく
⑦ ⑥で連続している文字をまとめる
⑧ ⑦で連続している塊をまとめ、②にくっつける
⑨ ②～⑧ の操作を、
$y=2$ ～ $9$
$x= \lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor -5$ ～ $\lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor$ の乱数
で行った後、最も良かった $y$ に対し、
$x= \lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor -6$ ～ $\lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor$
でそれぞれもう一度②～⑧を行う
⑩ ⑨のうち最もコマンド長が短かったものを出力する

この解法に則ったコードが下のものです。(最終提出まで伸びてくれました)

atcoder.jp

f:id:Anko_nasubi:20211218212805p:plain

コンテスト中考えていたことなど

f:id:Anko_nasubi:20211218213207p:plain — AtCoder Marathon Replay さんより

0:01

とりあえず正の得点を取ろうと思い、以下のコードを投げました。

f:id:Anko_nasubi:20211218213411p:plain

Python 初心者か？？？？？

再提出はせずまともな解の実装を始めました。

~ 0:40 (36,066 点)

とりあえず「隣接するマスのうちまだ掃除されていないものがあれば移動する・なければランダムで移動する」というコードを書きました。
結果はほとんど全てのケースで掃除しきれず。
明らかに違うので別の方針で進めます。

~ 1:12 (10.06M 点)

「まだ掃除されていないマスのうち、現在のマスから最も近いものに移動する」というコードに書き換えました。要するに貪欲です。
ここで提出したところ瞬間 1 位に浮上しました。(かなりびっくり)
方針は良さそうだったのでこのコードに肉付けしていく形で実装を進めていきます。

~1:54 (10.40M 点)

上の解法の④・⑤にあたる山登り法、⑦にあたる文字数削減を実装します。
完成して提出してみると何故か点数が落ちてしまいました。
デバッグをしていたところ、現在の向きがうまく更新されていないことを発見しました。(このミスは今回何度もやりました。~~学習能力~~)

~2:31 (10.42M 点)

上の解法の⑧にあたる文字数削減を実装しましたが、(なんとなく予想はしていましたが)大きなスコア改善にはなりませんでした。

~3:06 (11.17M 点)

ここでようやく②の前身にあたる「最初に適当に埋めちゃおう作戦」を実行します。
このときの文字列は 20(3(15Flrr)) → 20(3(5Flrr))20(3(5Frll)) にしています。

~4:11 (14.29M 点)

遂に 10(30(LrrF)30(RllF)) という型を発見します。
この型で提出したところかなり伸びたので、これを少しずつ弄って伸ばしていきました。

~6:56 (18.38M 点)

上の型を一般化し、様々な乱数で最適なものを探していきました。
このとき最もスコアが出たのが、
$x=14$ ～ $17$
$y=28$ ～ $37$
という組み合わせでした。

~8:00 (39.88M 点)

順位表凍結直後、試しに $x$ と $y$ を入れ替えてみたところ、なんとスコアが倍近く伸びました。(流石に笑ってしまいました)
$y$ が小さいほどスコアが良くなるのでは？と思い、最終的に解法にも載せた通り $y=2$ ～ $9$ くらいが最適だろうという結果になりました。
凍結時点の順位表を見る限り他の人のスコア変動が無ければユース 2 位だったので、かなり興奮していました。

f:id:Anko_nasubi:20211218221149p:plain

上のグラフからも分かる通り、凍結後の一時間は出すたびに目に見えるスコア改善ができ非常に楽しかったです。

おわりに

初めてのマラソン大勝利でした。ヒューリスティックコンテストは戦略等はほとんど要らず(ほんとに？)、完全地力勝負なので勝てるとアルゴ以上に気持ちいいですね。マラソン堕ちしてしまうかもしれません。
最後に、このような問題・コンテスト・~~その他ノベルティ諸々~~ を用意してくださったフューチャー株式会社さん、ありがとうございました！来年も機会があれば～

なすびの精進日記

HTTF2022 本選　参加記