MM108備忘録

MM108の参加記を書き忘れていることに気が付いたので備忘録

最終的に3位でした*1。

問題概要

H*Wのマスと文字列集合が与えられる。
各マスにアルファベットを配置して、与えられた文字列集合からなるクロスワードパズルを作れ。
ただし、アルファベットが2つ以上連続している個所はすべて文字列集合に含まれている必要があり、かつ、各文字列は一度までしか使ってはいけない（使ってないものがあってもよい）。
アルファベットが配置されてないマスごとにスコアは-1され、各配置された文字列について、その長さをlとおくとfib(l)分だけスコアに加算される。

やったこと

言葉にするのがしんどい

こんな感じでまずは文字列をきれいに交差しないように並べる
そのあとに交差するところに置けるかどうかをチェックして置けるなら置く。
大事なのは、交差しない段階ではまだその長さの文字列を置くということまでしか決めておらず、交差するときにはじめてどの文字列を使うか決定することで、こうすることで多くの文字列を置けるようになる。
また、交差するように置けないときにもともと置いていたものを少しずらしてみたりするとよい。
また、文字列を配置するときに上下左右どこから埋めていくかで結果が異なるので、いろいろと試したりする（時間は余るため）。

まぁこんな感じ（雑）

*1:前回は多分一部のケースでTLEしたことにより順位が落ちたので落ちなくてよかった