11 位．
懇親会 + 賞金 1.5 万円ゲット！やったぁ
開始 30 分で考えたこと
- 作る文字列があらかじめ決まっていたら，DP で最適解が作れる
- 文字列の長さを最短にするのが必ずしもいいとは限らない
- 作る縁起の良い文字列の順番を決め打ったら，DP で最適解が作れる
- いい感じの順番を探したい -> ビームサーチ？焼きなまし？
- 2-opt がうまくいかなそう（T1 -> T2 の相性は良くても T2 -> T1 の相性は良いわけではない）
- 他の近傍が思いつかないので，とりあえずビームサーチにしよう
- ビームサーチだと，もともと作りにくい文字列たちが残っちゃわない？ -> 各文字列に対して，"作りやすさ" （値が小さいほど簡単）を定義して，ビームサーチ中にはコストから作りやすさを引くことにすればちょうどいいのでは？
あとはひたすら実装．ビームサーチは速い言語の方が有利なので c++ で書くことにした．
（上に書いた考察は解説放送で大体同じことを言っていた（作りやすさは解説放送の base cost みたいなもの））
実装
まずビームサーチを高速化するのを念頭に， の次に
を付けるときに必要な遷移コストを前計算した．
で「
の末尾の文字がマス
で終わっていた場合に，
の末尾の文字をマス
で終わらせるために必要なコスト」みたいな感じで DP を定義した．
ビームサーチの状態としては，「すでに決定している の順序，および最後のマス」を持った．
文字列 に対する作りやすさ（base cost）は，とりあえず「マス
から始めたとき文字列 t を作るために必要な最小コスト」を
個すべての
に対して求め，それらの平均値とした．
いつもは python を書いているため，慣れない言語でかなり実装にてこずったが，2:07:14 に初提出 (1081686 点)．このとき 10 位．
初提出のビーム幅を間違えて 2 にしていたので，70 にしてから再度提出 (1092374 点)．6 位に浮上．
残り時間は高速化と base cost の計算方法を変えたりしていた．base cost を平均値の 0.8 倍くらいにすると 1097399 点．これがコンテスト中最高点だった．
解説放送を見ると，base cost は「全ての に対する最小コスト」の最小値としていて，これに変えてみると 1099433 点になってコンテスト中順位 8 位まで上がった．コンテスト中にこの計算方法も思いついていたので悔しい．seed=0,1 でよくならなかったので諦めていたが，とりあえず出してみればよかった．
感想
自分の解法がちゃんとはまり，AHC 過去最高順位も取れてうれしい．とても面白い問題だった．懇親会楽しみ～
