Marathon Match 68

TopCoder

http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14495
引っ越しとかで終盤手を付けられなかったけど参加してました。
17位でレート上昇。と言っても前回の下がり幅分回収できるわけもなくまだ青いまま。

問題

サイズと使用可能な単語リストが与えられ、クロスワードを生成する問題。
クロスワードは下に示すような基準で評価され、テストケースごとにそれぞれの基準にかかる重みが変化します。

  • Board filling score - 文字が置かれたセルの割合
  • Rows/columns filling score - 空白ではない行/列の割合
  • Symmetry score - クロスワードの対称性 (線対称かつ点対称かつ転置しても同じ形の時満点になる)
  • Crossings score - 複数の単語が交差しているセルの数

まずはランダム生成から

とりあえずTesterのコードを見ながら評価関数を実装して、ランダム探索で一番スコアが高かったものを返すようにする。43.19点。

まじめに解こうと努力してみる

ランダム生成の解を眺めながら各評価基準について考えると以下のような考えが出てきた。

  • Rows/columns filling score はわりとよく満点が出る。あまり意識しなくてもいいスコアになりそう。
  • Symmetry score が悲惨。ランダムだから仕方ないけど。
  • Crossings score も悲惨。でもこれはランダムじゃなくてもあまり取れないような……

とりあえず Symmetry score は交差を気にしなければ、回の字状に単語を配置すれば簡単に満点が取れることに気が付いたので実装してみる。60.62点。でもクロスワードと言われてこんなの出されたら絶対納得がいかないだろうなー。

これをベースにいじってみる

納得はいかなくてもValidではあるのでこれをベースに進めることに。
やったこと：

  • 残った単語を入れられるところに入れてみて、これでスコアが上昇したらそれを返すようにする。
  • 外周の埋め方をGreedyな方法で求めていたのでちゃんとDPで最適な方法を求めるように。
  • 各四角形の角の部分は文字を重ねるように。

いくらかGreedyな部分があるので時間いっぱい単語の順番をシャッフルしながら試行し、一番スコアのよかったものを返すようにした状態で62.58点。
この方法で生成される解は下図のような感じ(seed=5)。

いくらなんでも Crossings score が悲惨すぎる

重みが 1 1 1 10 みたいになった時が悲惨すぎるのでちょっと考えてみることに。
しりとりのように単語をつないで、それを右上から左下に向かってジグザグに対角線を結ぶように配置する。これで点数がだいたい1/(使用した単語の文字数の平均-1)くらいになるはず。だいたい0.15~0.3くらいとして計算するといくつかのケースで点数が上がりそう、というわけで実装。
ジグザグ配置が使用された場合の解は下図のような感じ(seed=58)。

回の字配置とジグザグ配置で適当に時間を配分し、スコアが良かった方を採用することに。これで63.20点（最終Submit）。
これ以降は引っ越しなんかでばたばたしててまともに調整できず。でも上位陣の配置見てると追いつくのは無理そうだったか。

1週間と短かったけれどすごく楽しめました。また来週くらいにTCO11のMarathonが始まるのでそっちも楽しみです。