マラソンマッチ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
戻り値は、完成したクロスワードの各行を文字列として入れた配列。
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点)となる。
例題
原文をお読み下さい。