■ [MM]NSA Marathon Event 3 
妙な問題だった
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14209&pm=10756
遺跡から石版が発掘された。しかし石版はバキバキに割れていてピースの1割強は行方不明。さらにピースの端はぼろぼろに欠けている。もとの石版の形と模様を復元せよ。
解法
自明解+α
全部を空白で埋める・白で埋める・黒で埋める のうち一番いいスコアになるもので提出。64点で真ん中くらい。
対称性を考えると、Nが偶数ならば必ず真ん中に穴が空いているということが分かったので、Nが偶数の時は無条件で中心に30*30くらいの空白を作るようにすると、わずかに上がった。65点。
リバースエンジニアリング？
Nが偶数→真ん中に穴がある の考えをさらに推し進めて、次の考えに至る。
「ビジュアライザのコードを見ると、あり得る石版の形は数万パターンしかないことがわかる。入力のSとNだけから石版の形を推測可能なのでは？」
ビジュアライザのコードを流用してきて試してみると、だいたい8割のテストケースで一意に石版の形が決まってしまった。まじでー。
残り2割は候補が複数出てきたものの、与えられたピースから直線になっている辺を探して、45°刻みの角を検出してやることで、どれが合致するかはだいたい推測できた。
結局、99パーセントくらいのテストケースで石版の形を正確に把握可能だった。92点、10位くらい。
ジグソーパズル
あとは模様を調べないといけないので、与えられたピースをくっつけてどうこう、とやらないといけない。だがうまくくっつけられる方法が思いつかない。
ボロノイ領域が凸多角形になることを生かして、ピースの凸包を取って端が欠けているのをある程度復元ーとかやってみてたけど、それだけではどうしようもない。
全部のピースの組・回転に対して一マスずつずらしながら調べてみて、合っていそうな距離が長いものからくっつけてみればいいんじゃないか？
というコードを最終日にようやく書き始めるも、誤検出しまくって全然ダメだった。終了。
結果
- 順位 10/61
- レート 2078→2041
けっこう時間使ってたのに完敗。初めてレート下がってしまった。
TCOでがんばれば一気に帳消しにできるくらいではありますが。
感想
上位の人の方針を見ても、模様を調べるのには端っこのピースや対称なピースだけを使っていて、まじめにジグソーパズルやってる人はいなかったよう。やはり無理ゲーだったか。
その方針にたどり着くには、ジグソーパズルをまともにやるのはダメだという確信をもっと早くに得ていないといけなかった。考えるだけで手が止まってしまっていた時間が長かったのが敗因。
しかし実装色の強い問題で大変でした。コード量がこれまでで一番長かったときの倍以上になってしまった。
