HACK TO THE FUTURE 2021 予選参加録
問題
方針
- 1 - カードをすべて回収する。
- 全部のカードを持っていたほうが後にカードを再配置する際に自由が効きそう。
- 2 - 集めたカードを再度配置し直す。
- 後で 0 から 99 のカードを集めるときの移動コストが小さくなるようにする。
- 3 - 0 から 99 のカードを回収する。
この方針だと以下の状況で移動が発生します。
- カードを全回収するとき
- カードを再配置するとき
- 0 から 99 のカードを回収するとき
最後のパートについては回収する順番が固定なので、回収する順番については考えなくて良いです。 1つ目と 2つ目については連動していて、山札がスタック構造なので最初に回収した順番の逆順でカードの再配置を行います。 なので、全体の移動回数は以下の 2つの要素で決まります。
- 初期配置のカードの回収の順番
- カードの再配置場所
これらを焼きなましを行って最適化を行いました。（それぞれを独立ではなく同時に）
遷移は以下の 5つです。
- 回収順番の 2点swap
- 回収順番を 1点だけ入れ替え(insert)
- 回収順番を 2-opt
- 再配置場所の 2点swap
- 1つカード選んで再配置場所をランダムに変更
最終スコアは 168440 で予選 3位でした。（後で試してみたら回収順番の遷移は 2-opt だけのほうがスコア良かったです 168531）
過去の順位が 192、149 だったので正直かなり高順位で驚いてます。（毎回フィーリングで解いてるので安定感が無いのはそう）
コンテスト終盤、方針変更するには時間がないし、テストケースが 50個なのをいいことに 1時間ぐらいひどいパラメータ調整をしてた気がする。（要反省）
