マラソンマッチ68 美しいクロスワード

TopCoder Marathon Match 68 BeautifulCrosswordの意訳です。
翻訳間違ってる箇所があったら、ごめんなさい。
 
原文は、下記になります。
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14495&pm=11353

問題の概要

ここにN×Nマスの板と、単語リストがある。
これらの単語のみを使って、板の上に、より美しいクロスワードを作ることが、あなたの使命だ。

注意点

・ マス上に2つ以上の文字が連続する時、それが垂直(上から下)であっても水平(左から右)であっても、単語と見なされる。単語は単語リストにあるものしか存在してはならない。
・ マス上におかれたアルファベットは、少なくとも1つの単語の一部である必要がある。
・ 各単語は、1回きりしか使えない。

クロスワードの美しさの基準……4つの部分スコア

充填率スコア: アルファベットが埋まっているマス数 / 全マス数
 
行列使用率スコア: 使われている列数×使われている行数 / (全行数+全列数)
 
※ 使われている=列または行に属するマスのうち、1つ以上にアルファベットが刻まれている。
 
対称スコア:
【上下反転/左右反転/90度ずつの回転】を行った時に、各点が移動する8カ所を同一グループと見なす。
 
・ この8カ所全てがアルファベット、または全て空白なら、1。
・ 8カ所中7カ所がアルファベットまたは、1カ所だけがアルファベットなら、0.5。
・ 8カ所中6カ所がアルファベットまたは、1カ所だけがアルファベットなら、0.1。
 
のそれぞれでグループを点数付けし、それらを平均したものが、対称スコアとなる。
 
なお、角の対角線上や、Nが奇数の場合の中央列/中央行では、8カ所ではなく4カ所1グループとなる。
また、Nが奇数の場合の中心点では1カ所1グループとなる。
この場合、アルファベット数を2倍または8倍することになる。
(つまり、Nが奇数の場合の中心点は、常に、全てアルファベットまたは全て空白となり、ポイント1となる)
 
交差スコア: 交差セル数 / アルファベットが埋まっているセル数
交差セルとは、垂直と水平の両方で、単語のアルファベットとして使われているセル。

テストケースごとの最終スコア

テストケースごとに4つの値からなる配列weightsが与えられ、それを用いて以下の様に最終スコアを計算する。
 
最終スコアの計算式:
A*weights[0] + B*weights[1] + C*weights[2] + D*weights[3]) / (weights[0] + weights[1] + weights[2] + weights[3]
A: 充填率スコア
B: 行列使用率スコア
C: 対称スコア
D: 交差スコア
 
なお、無効な回答は0点となる。

総合スコア

総合スコアは、各テストケースの最終スコアの合計となる。
(試合中のランキングでのテストケースは100問、試合終了後のシステムテストでのテストケースは1000問でした)

実装すべきメソッドの引数と戻り値

vector generateCrossword(int N, vector words, vector weights);
 
戻り値は、完成したクロスワードの各行を文字列として入れた配列。
 
Nは20〜100の整数。(ただし、テストケース0のみ、Nは11。
weightsは(前述の通り)4つの要素からなり、各要素の値は1〜10の整数。
 
wordsの各単語は、全て大文字アルファベット。
なお、wordsに使われる可能性のある単語は、あらかじめ公開されている。
http://www.topcoder.com/contest/problem/BeautifulCrossword/words.zip

補足

ローカル環境にてテスト可能なテスターが、与えられる。
http://www.topcoder.com/contest/problem/BeautifulCrossword/manual.html
 
スコアリングの詳細について上記であいまいな場合は、テスターのソースコードを読めば一意に分かる。
また、メモリやソースの長さ等は得に制限ない。(ただし、動かすテストサーバー自体のメモリは有限である)
ただし処理時間は1問につきサーバー時間で10秒で、それ以上かかると処理が打ち切られ、無効な回答(0点)となる。

例題

原文をお読み下さい。