操作 3 (置く)を使わずに、拾う順番を焼きなましすることにします。

まず操作 3 を使わないことで、この問題は整数の組 \((0, 0), (0, 1), (1, 0), (1, 1), (2, 0), \dots , (199, 0), (199, 1)\) を適切な順番で並び替えた列 \(p\) を作る問題だと言えます。

初期解

あまり寄与しないと思いますが、以下のようにして作りました。

\(p\) を空の状態から始めて、\(i = 0, 1 , \dots, 199\) の順に、以下の操作を行う。

• \((p_{0}, \dots, p_{k}, (i, a), (i, b), p_{k + 1}, \dots, p_{2i - 1})\) と表せる数列のうち、最もコストの小さいものを選ぶ。

計算量は \(O(N^4)\) で、後に影響しないくらいに高速です。

遷移

\(0\leq n < 200\) を満たす \(n\) を一様ランダムに選んだ後、\(p\) から \((n, 0), (n, 1)\) を抜き、適切な箇所に挿入するという遷移を繰り返しました。

適切な箇所に挿入する操作としては例えば以下の \(2\) 通りが考えられます。

• 遷移 \(1\) : 整数 \(i\) を一様ランダムに選び、\(\dots, p_{i}, (n, a), (n, b), p_{i + 1}, \dots\) となるように挿入する
• 遷移 \(2\) : \(\{p_{i}, p_{j}\} = \{(x, 0), (x, 1)\}\) を満たす \(i < j\) を一様ランダムに選び、\(p_{i}\) の前に \((n, a)\) を \(p_{j}\) の後に \((n, b)\) を入れる。

基本的にはこれら \(2\) つを適当な確率(\(4 : 6\))で選び、遷移を行いました。しかしこれでは以下のように挿入するものが網羅されていません。

• 差が \(2\) 以上の単調増加列 \((I_{0}, \dots, I_{m})\) であって、「任意の \(0\leq i < m\) について、\(p[I_{i}]\) と\(p[I_{i + 1} - 1]\) の最初の要素が等しい」を満たすものを選び、\(p[I_{0}]\) の前に \((n, a)\) を、\(p[I_{m}]\) の後に \((n, b)\) を挿入する。

このように挿入することで例えば、

\(\dots,(x,0),\dots,(x, 1), (y, 0),\dots,(y, 1),\dots\)

となっているものに対して、

\(\dots,(n, a), (x,0),\dots,(x, 1), (y, 0),\dots,(y, 1),(n, b),\dots\)

と挿入する遷移が網羅できます。

これらをある程度の確率で遷移させるために、遷移 \(2\) では、\(x\) を一様ランダムに選ぶことで \(i, j\) を決めた後に、以下の操作を繰り返すことで \(i\) を変更させました。(\(j\) も同様)

• \(i \neq 0\) かつ、\(\{p_{k}, p_{i - 1}\} = \{(y, 0), (y, 1)\}\) を見たす \(y\) が存在するような \(k\) が \(i - 1\) 未満であれば、確率 \(P\) で、\(i\leftarrow k\) とする。そうでない、もしくは確率 \((1 - P)\) で操作を終える。
  

\(P\) に関してはマジックナンバーで \(50\) % にしましたが、このパートの計算時間を少なくするために、ある程度の確率で操作を終える必要があります。

以上をコンテスト中に実装しました。これらの遷移は \(p\) の連結リストと、任意の \(n\) について、\((n, 0)\) と \((n, 1)\) のどちらが前の方にいるかを持った bool 配列を用いることで時間計算量 \(O(1)\) (遷移 \(2\) に関しては平均計算量)で遷移とスコアの計算をすることが可能です。上の説明では \(p\) のどの index の前後に挿入するかと書きましたが、実際にはどの組の前後に挿入するかを決めて、連結リストと bool 配列を更新するということにしました。

tips

• 評価関数はスコアと同じです。
• \((n, a), (n, b)\) を挿入する際、\((a, b) = (0, 1), (1, 0)\) のいずれかにするかはスコアが良い方を選びました。
• 例えば区間の reverse や valid な区間を取り出して別の箇所に挿入するという遷移は、遷移コストが大きいため最終的には採用しませんでした。