AHC004に参加しました
AtCoder Heuristic Contest 004に参加しました。
107位でした。
方針
文字列を重ねて詰め込む問題です。
簡単な考察として
- 文字列が被さったり、包含されているものは、優先的に配置したい
というのがあります。
被さりは、suffixとprefixの一致なので、dpなどを使って前計算できます。包含関係も同様です。この値を使って文字列に優先順位をつけ、配置します。
配置する場所は全て試して、他の文字列と被さりがある場合に加点します。
配置の場所は無限にあるので、時間の許す限りランダム要素を入れながら探しました。ここをもっといい感じにしたかったです。