HACK TO THE FUTURE 2021 予選に参加しました。
8時間のマラソン形式のコンテストです。
結果は153,119点で、提出者866人のうち208位。
問題
問題はカードの回収。
20x20のマス内にある0～99のカードを順番に回収するというもの。
ただし回収枠はスタック形式で、一度拾ったカードを再度置くことができます。
考察
移動量のみで得点が決まるので、カードを再配置して移動量を削減する問題。
回収しながら再配置を行う戦略、10x10に再配置してから回収する戦略を考察。
後者の得点の見積もりはある程度やったのですが、
前者の見積もりが全く出来なかったのでどちらで進めるか悩みました。
悩んだ末、ある程度道が見えている後者で進めることにしました。
（が、最終的には前者になりました）
究極的にはTSPだというのは分かったのですが、
出来ると思わなくて投げ捨てていましたね…。
方策
１．最小値のカードへ順番に移動する
カード毎に座標を記録して、差の分だけUDLRの後、Iを出力しました。
この時点ではロボット座標を動かしてシミュレーションすることはしませんでした。
２．10x10の領域にカードを集める
偶数段目を右方向に全走査した後に奇数段目を左から全走査。
というのを20段続け、更に10x10の範囲に置きなおすというコードを書きました。
道中にカードがあるか判定してあったらスタックに積んでと、ひたすらに面倒臭かった。
最後まで使うつもりでしたが最終的には廃棄されてしまいました。
３．中央にカードを集める
10x10にカードを集めた後、0～99を順番に回収します。
そのとき、道中のカードを中央に寄せることが出来るなら寄せます。
上下左右のうち２方向だけでランダムに10000ルートを探索しました。
ここまで作ったところで10x10に集めない方が得点が良さそうだったので、
集めない方針に変更してタイムアップ。
感想会
公式解説（上記問題内にリンクあり）を見た感じ、
上位は10x10に集めている人がほとんどでした。
（集めない方が強い説も出ましたが、時間内に形にすることも大事）
愚直に走査せずTSPで集めること、2-optが利用できること、などなど。
反省点
- 真面目に分析できたのは良かった
・10x10集めの初歩までは公式解説と同じ分析ができた
- 本質的な部分に全く着手していない
・TSP
・なんとなく中央に集めたけど連続数値を近くする考慮はしていない
・完全乱択から選択はしたけど焼いてない
やり切った感はあるものの、今思うと時間いっぱいやったというだけで
時間があればまだやれる事はありましたね。
方針に悩みつつ進めたというのはありますが、
1日未満のマラソンでは時間が不足しがちなので
スピードアップして本質的な部分を強化していきたいところです。
