5,356,477,323点で 114位/622人 でした。
最終提出はこちら Submission #23750881 - AtCoder Heuristic Contest 004
最終解法
- 自身が完全に含まれる文字列があれば、そのうち最も短いものに合成。
- 文字列が短い順に、前後端が最も長く重複する文字列と合成していく。ただし、最長ケースが一定値を超えない場合は合成自体しない。
- 1, 2 で残った文字列を、合成された個数が多い順に横向きに敷き詰めていく。
- 空きスペースを集めるように縦方向に文字列を並べ替える
- 3の余りの文字列の内、合成された個数が多い順に、4で作った空きスペースに縦向きに置けるだけ置く。
という流れを、2に出てくる一定値を変動させて複数パターン試して、最も点数が高かったものを選んだ。
思ったことを雑多に
なだらかな近傍が作れる気がしなかったので、山登り系のアプローチは早い段階で切って、大体ずっと貪欲解法を模索していました。*1 文字列合成部分とか、賢いアルゴリズムがありそうだよなあとか思いつつ、貪欲でごまかしごまかし進めていました。
4時間経過したあたりで、思いついた実装できそうなことは一通り試し終わり、残りはほとんど座っているだけになってしまっていました。 実行時間ががっつり余っていたので、なんか上手いこと使いみちを考えられるとよかったんだけどなあとかを思ったり。
こっからどう伸ばしたらいいのかてんで見当がついていないので、上位陣の解法を見て勉強して行きたいなと思います。
*1:TL見てたら、上位解法に焼きなまし系の解法がポツポツあるように感じたので、気になっています。
