問題

atcoder.jp

コンテスト中ずっとバグ修正してたので参加してたかと言われると怪しい

戦略

基本的な部分は上位の人達と一緒です

任意の山を 1つ選択する
選択した山からすべての箱を取り除く
空になった山に昇順になるように箱を置き直す

山が全て昇順になった状態であれば任意の山から常に最小の箱を選択することが可能となり実質ゲーム終了となります。

勝利盤面

自分は今回ビームサーチで選択した山から「どれだけ取得するか」「どこに配置するのか」を求めました。昇順に置き直す部分は貪欲法で実装しています。

任意の山を選択

まず最初にどこの山を選択するのかについてですが「まだ運び出されていない箱の中で最小の ID を含む山」を選択するようにしています。理由としては主に 2つあります。

確実に最小の箱を盤面から運び出すことが出来る
運び出す際に必ず最小の箱を運び出す操作が出来るので箱を空にする操作のコストが実質的に減る

時間があれば選ぶランダムに選択することも可能だとは思いますが、今回の実装だとそんなに多く回せなかったので貪欲に山を選択しています。

選択した山からすべての箱を取り除く

ソートまでの流れとしては主に以下の通りになります。

山から箱を取り出して空にする
箱を他の山に積む
空の山に箱がソートするように移動させる

これらを行いつつなるべくコストを抑えるように工夫します。

山の取り出し

山を空にした後に他の山の状態がどうなっていると嬉しいかについて考えます。理想的には「他の山の箱が降順で並べられている」のが好ましいです。（この状態であれば空いた山に昇順ですべての箱を並べることが出来るため）

ソート時の様子

実際にはこのような盤面になることはありませんが、基本的な方針としては「他の山の頂点からなるべく降順で箱が並ぶようにする」となります。そのため、ビームサーチにおける手の選択としては「箱を◯◯個取り出す」を実行する際に取り出した箱の列が降順を維持しているかどうかをチェックしています。ただ、これだけだと手の選択が狭いので確率で昇順になっていても取り出せるようにしています（ただし箱の ID の差が大きいとダメ）

箱を選択した後は任意の山の上に置きます。

山の状態の評価

今回のビームサーチの評価関数として「現在の状態でソートを行ったときに出来上がる山の高さとコスト」を利用しました。ソートを行う部分については後のほうで説明します。この評価値を使うことでソート後に出来上がる山が「高さ」「コスト」のバランスが良いものとなります。（実際には高さとコストのバランスのチューニングが難しかったので色々重みを変えながら実行しています。）

実際の評価関数は以下のようになっています。（x, y, z はそれぞれの重み）

x * 山の高さ - y * 山を取り出す時のコスト - z * ソートする時のコスト

ソート時の処理

以下の操作が出来なくなるまで繰り返し実行します。

ソート済みの山と移動先の山を除く山に対して一番上の箱の ID が一番大きいものを選択する
- 既に置かれている箱の ID より大きいものは選択されない
選択した箱をソート対象の山に移動させる。この際選択した箱より下の箱も一緒に移動できる場合は移動させる。

実際の実装では運び出せる箱が存在する場合は必ず運び出すようにしていますが（今回の例だと 1 と 2）、説明のために省略しています。

時間制限いっぱい繰り返す

1回の処理で大体数百 msec ぐらいかかりますが、これを複数回繰り返して一番スコアが良いものを選択します。実行するごとに評価関数で使っている重みを変更しています。

Score = 9516 (seed = 0)

感想

評価関数をずっと考えていたが特に良いものが思いつかなかった。各山に置くときになるべく降順を維持するほうが良いのは確かだが移動時のコストを考えると昇順になっていたほうが嬉しい場面も存在しており、そこを評価するのが難しかったので実際にソートしてみてその結果をそのまま評価値に使うと良くなった。もっと良い評価値が見つかればスコアが伸びると思う。

コンテスト後にゆっくり実装しても普通にバグらせてたので短期で実装し切るのは流石に無理があった。評価関数さえ良ければ良いスコアが出るという点ではまだ戦えるほうのコンテストだと思ったけど「箱の移動」「箱の取り出し」の処理を無限にバグらせていたので仕方ない。