擬似スコアを高速に求められるようにしておいて遷移行列を焼きなますというのはほかの上位陣と同じです．自分は少し変わった初期解の生成方法をしていて，それがうまくいったので記録として残しておきます．

\(P\) は降順にソートされているものとします．

大まかな方針としては以下の通りです．

1. \((S_0,P_0),(S_0,P_0),\dots,(S_{K-1},P_{K-1})\) のみを考えるようにして，\(\sum_{i=0}^{K-1}P_iQ_i\) が大きくなることを目指す．
2. a, b, …, f のほかに大文字 A, B, …,F もあると思って問題を解くことにする．
3. 各 \(S_i(i=0,1,\dots,K-1)\) に対して，各文字を小文字または大文字にランダムに振り分けた文字列 \(T_i\) を生成する．
4. \(T_0,T_1,\ldots,T_{K-1}\) をもとに遷移行列 \(A\) を適当な方法で生成し，それのスコアを求める．
5. \(T_i\) のどれかの文字を大文字から小文字へ，あるいは小文字から大文字に変更するという近傍のみで焼きなましをする

例えば \(S_i\) が abcdefabc だったとき，\(T_i\) は AbcDEfabC みたいな感じです．文字 a, A, b, B, …は頂点 \(0,1,2,3\ldots\) と対応させます．

ここで，手順 4. の遷移行列を生成する方法をどうするかがポイントです．自分は次のようにして生成しました．

1. \(M\times M\) の零行列 \(A\) を用意する．
2. \(i=0,1,\ldots,K-1\) に対して以下を行う．
   • \(j=0,1,\ldots,|T_i|-2\) に対して，\(u=T_{i,j},v=T_{i,j+1}\) としたとき，\(A_{u,v}\) に重み \(w(i,j)\) を加算する．
   • \(u=T_{i,|T_i|-1}\) としたとき，各 \(v=0,1,\ldots,M-1\) に対して \(A_{u,v}\) に \(1\) を加算する
3. \(A\) の各行の総和が \(100\) になるように調整する．
   • すなわち，各 \(i=0,1,\ldots,M-1\) に対して，\(s=\sum_{j=0}^{M-1}A_{i,j}\) としたとき，\(A_{i,j}\) を \(100A_{i,j}/s\) で置き換える．

ここで，重み関数 \(w(i,j)\) は以下のように設計しました．

• \(w(i,j)=P_i\times (\mathrm{offset}+j)\)
  • これのお気持ち：重み関数は \(P_i\) に比例してほしい．同じ文字列の中では後ろの方にあるものの方が重みが大きくなってほしい．

本番では \(K=6,\mathrm{offset}=5\) とするのが一番良く，初期解のみで seed 0 で 40000 点ほど達成できました．（これがなんでうまくいったのかはあまりよくわかっていないです．）

seed 0 で初期解の生成が終わったときの visualizer : https://x.com/torii_kyopro/status/1924108696445235486