simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

HACK TO THE FUTURE 2021 予選参加録

問題

atcoder.jp

方針

  • 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

過去の順位が 192149 だったので正直かなり高順位で驚いてます。(毎回フィーリングで解いてるので安定感が無いのはそう)

コンテスト終盤、方針変更するには時間がないし、テストケースが 50個なのをいいことに 1時間ぐらいひどいパラメータ調整をしてた気がする。(要反省)