■ [TCO][MM]Marathon Match 69（=TCO11 Marathon Round1） 
http://www.topcoder.com/longcontest/?module=ViewStandings&rd=14503
今回もおなじみの「トップまで達するにはレベルがあと2，3ほど足りない人」を演じ切りました
問題概要
W*Hの二値画像が与えられる。この中にいろんな大きさのアルファベットがnLetter個含まれている。アルファベットは互いに重なっているかもしれない。
各アルファベットのピクセルパターンがどんなものかは別途与えられる。
任意の列をscanしてその列のピクセルがどうなっているかを知ることができる。この情報を使って、未scan列の黒マスがどこかをできるだけ多く当てよ。
50<=W,H<=300, W*H/400<=nLetter<=W*H/200
基本的な戦略
- 5列ごとにscan
- まだ使われていない黒マスのうち多くの黒マスをカバーする文字の置き方をgreedyに選択する→使った黒マスを除去して繰り返し
- 上でクラスタリングしたそれぞれの黒マス集合に対して、そこに置ける文字を列挙して、未scan列の各マスが黒くなる確率を求める
- ある文字の置き方が他の文字にめり込んでいる場合、その置き方の確率を下げて再計算
- 未scan列のうち、すでに黒マスと断定したマスの数に比べてよく分からない状態のマスが多い列はそこを追加でscanして得られた情報を元に周囲の列を再計算
- どの文字にも含ませることができなかった黒マスについて、その周囲を適当に黒マスで埋める
5列ごとにscan
scanする列の決定は、処理を進めるごとに随時確率を計算して、一番スコア上昇に効く列はどこかを求めて適応的にscanしていくのが最適だろうとは思ったものの、
実装時間と実行時間が手に負えなくなりそうだったのでその方針は取り組まないことにした。
この時点でもうトップを取るのは不可能だったといえる。
方針の大枠となる、↓のgreedyクラスタリングにたどり着くまでに手間取って、もう残り1週間を切っていたのが痛かった。
多くの人がやっている、スキップする列の数を非整数にして固定間隔を避けるのは、ごく序盤のちゃんと方針が定まっていなかった頃にちょっとやってみて
よい結果が出ていなかったので試さなかったのだけど、終盤でもう一度試しておくべきだったか。
黒マスをgreedyにクラスタリング
すべての文字の置き方を試して、可能な黒マスのカバーの仕方を列挙する。
より多くの黒マスをカバーしている置き方からgreedyに選択していく。
大きい盤面の場合は候補が数十万通りくらい出てきて、単純にやると時間制限が危ういので適当に枝刈り的なことをして高速化する。
高速化のためにもう1つ、まったく同じピクセルパターンのアルファベットが1割以上存在するので、そいつらを縮退させて二重に計算しないようにした。
カバーする黒マスが同じ数の場合のタイブレークは、その置き方がカバーする黒マスの隣に関係ない黒マスが存在しない方がよい、という基準を設けた。これでだいぶ誤爆が減る。
いろんな出力を見ている感じ、JやZが良く誤爆しているようなのでそいつらの文字の場合評価を下げるようなことができないかとちょっと思ったが実装できなかった。
それと、単に1回greedyするだけではなくちょっと違う取り方をバックトラックなりで試して、
どのクラスタにも属さない黒マスが最小になる取り方を選ぶと誤爆率がもっと減ったかもしれないが、
これも実装する時間がなかった。
置ける文字を列挙してクラスタごとに確率計算
↑の各黒マスクラスタごとに、そこに配置しうるアルファベットを列挙して各マスが黒くなるかどうかの確率を求めた。
黒くするマスは、確率が1/2を超えるもの、とした。
また、確率が1/7〜1/2のマスについては、曖昧な状態のマスとしてその数を列ごとに記録しておく。
本当は、確率が1/2を超えるマスについても曖昧さを考慮すべきだったり、1/2に近いほどより強く考慮すべきだったりするのだけど、
このあたりに取り組みはじめたのが最終日だったのでそこまで手が回らなかった。
めり込み判定・再計算
テストデータはあまり文字が重ならないように作られるので、それを考慮する。
もう一度、各黒マスクラスタに対して可能なアルファベットの置き方を列挙して、その置き方が他の黒マスクラスタで塗られている領域にめり込んでいないかを判定する。
めり込んでいるものがあったら、そのアルファベットの置き方についての重みを下げて、黒マス確率を再計算する。
どのくらい重みを下げるかは、全体の文字の密度に依存して変える。密度が低いほどペナルティを大きくする。
追加スキャン
すでに黒マスとしたマスの数に比べて曖昧な状態のマスが多い列について、scanして周囲の列を再計算する。
どの黒マスクラスタからでもカバーされない余った黒マスが出た場合は、周囲にある他の余った黒マスとを一緒にカバーする文字の置き方があるか調べる。
そのような文字の配置が存在するなら、新しい黒マスクラスタを作って前にやったように確率計算する。
落ち穂拾い
どのクラスタにも属させることができなかった残り物の黒マスについて、その周囲を適当に黒く塗った。
具体的には次のように。
・上下1マスを黒にする
□□□ □■□ □■□ → □■□ □□□ □■□
・5列下のマスも残り物黒マスだったら間を埋める
□■□ □■□ □□□ □■□ □□□ → □■□ □□□ □■□ □□□ □■□ □■□ □■□
・斜めのマスも残り物黒マスだったら間を埋める
■□□□ ■□□□ □□□□ □■□□ □□□□ → □■□□ □□□□ □□■□ □□□□ □□■□ □□□■ □□□■
これだけでスコア0.4くらい違うんだからバカにならない
結果
（追記）
- 最終スコア 684.14（1000ケースの合計）
- 最終順位 2位
- レート 2010->2094
今回は大まかな方針が定まってしまいさえすれば、あとは出力を見るとどこを改善すれば良いかはわかりやすくて、それを一つ一つ実装していくだけ、という感じでした。
面白いともいえるしそうでないともいえる。
最後まで通して「これを実装すればスコアが上がる」というのをこれほど確信して取り組めたのは初めてなのではなかろうか。
それができたのも、テスト結果を正解や間違いがはっきり分かるように画像で出力させていたから。
適切なビジュアライズはやっぱり重要です
