方針

操作3(置く)は一切使わず、操作2(取る)の順番だけを最適化します。

暫定解の状態として、操作2を行うカードの順列 \(p = (p_1,\ldots, p_{|p|})\) を持つことにします。 ただし、順列が実行可能（同一の番号の 2 枚目のカードを取るとき、1 枚目のカードは必ず山札の一番上にある）という制約を常に満たすようにします。

ここで、ある状態 \(p\) に対して、 \(p\) において未回収の番号の 2 枚のカードをそれぞれ任意の箇所に挿入する方法で、上述の制約を満たすもののうち、挿入後の状態の移動回数が最小であるものが実は \(O(|p|)\) 時間で計算できます。 本解法ではこれを活用します。

アルゴリズム

まず、空の \(p\) から始めて上記の挿入アルゴリズムを繰り返し適用し、貪欲に初期解を構築します。 その後、以下の手順を繰り返す山登り法を行います。

1. 現在の状態 \(p\) から長さ 15 程度の区間をランダムに選ぶ。そこに含まれる要素、およびそれらと対になる要素を全て削除した状態 \(p'\) を作る。
2. 削除された番号をランダムな順序で選び、上記の挿入アルゴリズムで \(p'\) に貪欲に再挿入する。
3. 状態 \(p'\) のコストが \(p\) のコスト以下であれば、 \(p\) を \(p'\) で更新する。

コンテスト後に再実装した提出ではこの反復を 35,000 回程度実行でき、 2,300,629 点（本番2位相当） でした。なおこの提出における BestInsertPositions() 関数が先述の挿入アルゴリズムに対応します。

ここで更に、3. における受理条件を「状態 \(p'\) のコストが『既知の最善の解のコスト \(+ \theta\)』以下ならば更新する」に変更すると探索が進みやすくなり、 \(\theta = 2\) で 2,301,784 点（本番1位相当） となりました。 余談ですが、この受理条件には学術的には record-to-record travel (RRT) という名前がついているようです [1][2]。

局所探索系のアルゴリズムのなかでも、暫定解の比較的大きな範囲を強制的に破壊 (destroy) しその後修復 (repair) を行うような近傍を採用するものは large neighborhood search (LNS) と呼ばれていて、配送計画問題などで活用されているようです [3]。 また、過去の AHC などでも「部分破壊・再構築」方針としてしばしば言及されています。 本問題は構造が配送計画問題に近く、区間削除による破壊がうまく効いたのかもしれません。

参考文献

[1] G. Dueck, “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational physics, 104(1), pp.86–92, 1993.

[2] 久保 幹雄, J.P.ペドロソ, “メタヒューリスティクスの数理,” 共立出版, 2009.

[3] S. Ropke, D. Pisinger, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows ,” Transportation science, 40(4), pp.455–472, 2006.