$s_i$を盤面のどこかに上書きする遷移だけの焼きなましをした。
- 遷移の際のスコア更新について。変更に関わるそれぞれの行・列を（折り返しを考慮して）31文字の文字列とみなして、Aho-Corasickで$(s_i)$全体とマッチングした。マッチング結果は行・列ごとに長さ$M$のビット列に保持して、最後にすべてのビット列のORを取って立っているビットを数えた。
- 最初は$(s_i)$中の同一文字列をまとめて1つ1つに重みを与えていたが、重み付きになると最後の「立っているビットを数える」部分でワードサイズ高速化ができなくなって逆に遅くなった。
- 縦に書く文字列と横に書く文字列を混在させようとするより、どちらかに絞ったほうがだいぶ得点効率がいいことに気づいたので、横に書くだけにした。
- 行にだけ文字列を書くとした上で、変更に関わるすべての列を遷移ごとにマッチすると、特に$(s_i)$の平均長が大きい場合に調べるべき列が多くなって重くなる。結果を見ていると、平均長が大きい入力は縦にマッチするパターンがほとんどないようなので、列に関するマッチを完全に無視することにした。具体的には6以上なら列は無視して、5以下は列のマッチも調べた。
- 焼きなましの遷移回数は、前者が$2 \times 10^6$、後者が$4 \times 10^5$くらいだった。
- 盤面に存在しない$s_i$から乱択する遷移と$(s_i)$全体から乱択する遷移を入れていたが、前者がうまく高速化できずにボトルネックになっていたので、全体から乱択するだけにした。
- 追記: もっと単純に、盤面に存在する$s_i$を引いたら何回かサンプルしなおす、でよかった。改善は+0.2%程度。
- 平均長が大きい入力は3秒使いきる前にどこかの山に収束してしまうようだったので、平均長が8以上の入力については多点スタートした。
振り返り
- prefixとsuffixが重なる2つの文字列を1つにすることで点を伸ばしている人が多数いるようだ。これは最初に考えたのだけど、具体的にどの文字とどの文字を連結するべきかを考える必要があるし、焼きなましと相反しないだろうと思って後回しにした結果、最後まで放置してしまった。雑な貪欲でもいいから試してみるべきだったな。
