TOYOTA Programming Contest 2023 Summer final 延長戦の解法

TOYOTA Programming Contest 2023 Summer final における 297,762,906,271 点の解法を紹介します。延長戦の解法であり、実装に2日ほど要しました。コンテストは3時間30分しかないため、この解法をコンテスト中に実装しきるのは難しいと思います。

優勝者である terry さんの解説記事と一部内容が被ります。あらかじめご了承ください。

www.terry-u16.net

前提知識

幅優先探索
low link
モンテカルロ法
木上のビームサーチ

木上のビームサーチについては rhoo さんの記事が参考になると思います。

qiita.com

問題概要

$D \times D$ マスの倉庫にコンテナを運び込み、その後コンテナを運び出します。

運び込み・運び出しでは、出入り口から空きマスを辿って到達できる空きマス・コンテナにしか操作が行えません。

コンテナを運び込む順番はインタラクティブに与えられます。

運び出すコンテナ番号の転倒数を最小化してください。

詳細は公式の問題文を参考にしてください。

atcoder.jp

制約

$D = 9$

解法の概要

運び込みパートと運び出しパートで分けて考えます。

運び込みパートではモンテカルロ法を使用し、評価関数に従った貪欲法を改善します。

運び出しパートでは木上のビームサーチを使用します。

運び込みパート

貪欲法

各コンテナがどのあたりに配置されるとよいかを定めておき、その周辺に運び込むことを考えます。

番号が小さいコンテナから運び出したいので、番号が小さいコンテナを出入り口の近くに、番号が大きいコンテナを出入り口から遠いところに置くとよいと考えられます。そこで、幅優先探索を用いて出入り口からの各マス $i$ までの距離 $a_i$ を求め、距離の配列 $a$ をソートしたものを $b$ としたとき、コンテナ $t$ は出入り口からの距離が $b_t$ 程度になるマスに置くのがよさそうです。

また、空きマスの連結性を確保するために、端のマスからコンテナを詰めていくとよさそうです。

そこで、次のような貪欲法が考えられます。

運び込むコンテナ番号 $t$ を読み込む。
low link で関節点を列挙する。
各非関節点 $i$ について評価値 $f(t, i)$ を計算し、評価値が最も高いマスにコンテナ $t$ を運び込む。評価値 $f(t, i)$ の定義は以下の通り。

$f(t, i) = - (2 \times |a_i - b_t| + (iと隣接する空きマスの数))$

ここで簡単な考察をします。運び出すときの転倒数を0にするにはコンテナ0は出入り口と接している必要があります。一方で、番号が最大のコンテナは出入り口から遠いところにあるとよいというだけで、置ける場所の自由度は比較的大きいです。自由度の違いに着目すると、番号が大きいコンテナを出入り口から遠くに置くことよりも、番号が小さいコンテナを出入り口の近くに置くことを優先するとよさそうです。

そこで、コンテナ $t$ を運び込むときはコンテナ $t + 3$ の位置に運び込むようにします。すなわち、評価関数の $b_t$ を $b_{t + 3}$ に修正します。ただし、コンテナ0についてはコンテナ0の位置に運び込むようにします。

出入り口から近いマスを3つほど確保しておき、必要になったときに使うというようなイメージです。

もしかしたら、出入り口から遠いところに置くことを優先し、空きマスの連結性を確保しやすくなるというメリットもあるかもしれません。

モンテカルロ法

上記の貪欲法をモンテカルロ法で改善しました。アルゴリズムは以下の通りです。

評価値が高いマスを候補点として4つ選ぶ。
一定回数または一定時間のプレイアウトを行う。プレイアウトは以下の手順。
1. 候補点にコンテナ $t$ を運び込む。
2. 残りのコンテナの順番をランダムに生成する。
3. 上記の貪欲法で運び込みをシミュレートする。
4. 貪欲に運び出しを行い（後述）、スコアを求める。
平均スコアが最も高いものを採用する。

補足

貪欲に運び出すとは、運び出しが可能なコンテナのうち、番号が最小のものを取り続けることを表すものとする。優先度付きキューを用いて時間計算量 $O(D^{2} \log{D})$ で計算可能。（Dijkstra 法とよく似ている。）
プレイアウトの乱数列は全ての候補点で同じものを使用する。同じ条件でプレイアウトを行わないと比較しづらい。
残りのコンテナ数が6個以下の場合、順番を全探索する。厳密なプレイアウトの期待値が求まる。

各ターンのプレイアウト回数を揃えた場合、毎ターン1000回ほどのプレイアウトを行うことができました。候補の数が4つの場合、各候補について250回ほどのプレイアウトが行われます。

二次元配列を平坦化して一次元配列で置き換えるなど、定数倍高速化に注意して実装しました。（low link の結果を保存し、同じ盤面が現れたときに結果を使い回すというようなことも行いましたが、あまり速くならなかったです。）

運び出しパート

ビームサーチをします。履歴のコピー回数を減らすために木上のビームサーチを使用しました。

既に運び出したコンテナの集合と、直後に運び出せるコンテナの集合を状態としてもち、差分計算を行います。

評価関数は以下のように設定しました。

$-2 \times (確定転倒数) + (直後に運び出せるコンテナの数)$

確定転倒数とは、（連結性を無視して）未処理のコンテナを昇順に運び出した場合の転倒数のことです。既に運び出したコンテナの集合を bitset などで管理することにより、ビットシフトと popcount を用いて確定転倒数の差分計算を高速に行うことができます。

基本的には直後に運び出せるコンテナの数だけ、1つのノードから分岐します。ただし、番号が最小のコンテナを取り出せるときは、それが最善手であることから、それ以外の遷移を枝刈りしました。

既に運び出したコンテナの集合が一致するノードが複数出現した場合、確定転倒数が最小のものだけを残し、他のノードを削除します。既に運び出したコンテナの集合を bitset で管理することで、重複ノードの検出を厳密に行えます。（通常のビームサーチではハッシュ値を使用して重複探索を削除するのですが、今回はハッシュ値を使わなくてもよいということです。）

ビーム幅は1000にしました。ビームサーチの実行時間は0.1秒程度です。モンテカルロ法に時間を使うのが得策だと判断しました。

スコアへの寄与

プログラムを一箇所変えたものをいくつか用意し、それぞれについて100ケースの平均得点率と平均実行時間を測定しました。

変更点	平均得点率（%）	平均実行時間（秒）
なし	99.400	1.94
運び込みを貪欲法にする	98.221	0.11
モンテカルロ法のプレイアウト回数を半分にする	99.327	1.02
運び込みの評価関数において+3を行わない	98.992	1.95
運び出しを貪欲法にする	99.375	1.85

ビームサーチの寄与は比較的小さいことがわかりました。

使用した典型まとめ

今までのコンテストで身につけた典型的な手法をいくつか使用しました。典型手法とそれを使える代表的なコンテストを列挙しておきます。

考察

複数の問題に分けて考える。（完全に分離するとよくない場合もある。）
- AHC011
オブジェクトの自由度の違いに着目する。
- AHC021

手法

貪欲法
- 評価関数を工夫する。
モンテカルロ法
- 貪欲法でシミュレーションする。
- 終盤は全探索して厳密な期待値を求める。
- AHC015
ビームサーチ
- 木上のビームサーチ
  - AHC021
- 重複探索の削除
- 明らかに無駄な探索を枝刈りする。
- 評価関数は確定スコアに状態のよさを加えたものにする。