Hatena::Grouptopcoder

じじいのマラソン反省会@TopCoder

ニコニコ生放送:red.cliff.jp
TopCoderでプログラムしてみた(Algorithm Single Round Match専用):http://red.cliff.jp/topcoder.html
 | 

2011-07-22

方針

00:56

  1. ボトムアップで、短い単語から、平文から数字に置き換えていく。
  2. トップダウンで、長い単語から、平文から数字に置き換えていく。(最終的に企画倒れ
  3. 神頼みフェーズ(一番使われているのが多い文字で埋める)

ボトムアップで、短い単語から、平文から数字に置き換えていく。

  • S[x]の同じ長さの部分文字列の中で、たくさんでてくる「似たような」文字列を探す。探し方は以下の通り。
    • (このやり方より、「一番短い部分文字列は、必ず最初の32文字以内に現れる」の法則を使ったほうが、確実かつ高速だったと思います。全く気づけませんでした。ビューワ作ってれば気づいてたかも…)

例えば、"ABCDEFABXDE"の中にある似たような部分文字列(長さ5)を知りたいとき

(1)連続する2文字のハッシュ値の登場回数をカウント

map[連続する2文字のハッシュ]++

AB 2点

BC 1点

CD 1点

DE 2点

EF 1点

FA 1点

BX 1点

XD 1点

(2)連続する文字列長xの間で、連続する2文字のハッシュが合計何回でてくるかカウント(合計はしゃくとり法で求めました)

ABCDE 2+1+1+2=6点

BCDEF 1+1+2+1=5点

CDEFA 1+2+1+1=5点

DEFAB 2+1+1+1=5点

EFABX 1+1+1+1=5点

FABXD 1+1+1+1=5点

ABXDE 1+1+1+1=5点

(3)最高得点のやつが、もっともよく出てくる似た文字列。(ただこの得点のつけ方だと長い文字列が必ず有利になるので、得点のつけ方は、若干調整してます。)

この場合、ABCDEが6点で最高。

  • これを深さ優先探索(←全然ダメ)でやりました。枝の数は、Sの数に応じて、調整しました。

トップダウンで、長い単語から、平文から数字に置き換えていく。(最終的に企画倒れ

今回、問題が途中で変更になり、error値が大幅に大きくなりました。そこで、平文がerrorによりぐちゃぐちゃになっても、まだ残っている情報ってなんだろう?「実は長い平文のほうが、残っている情報が多いから、復元のチャンスがあるのでは?」と思い、やってみたのですが…

  • まず、同じ文字の間隔が多いところを探す

同じ文字の間隔を使えないか?

ABCDEFABXDE

A-A 文字の間隔 4

B-B 文字の間隔 4

D-D 文字の間隔 4

E-E 文字の間隔 4

よく出てくる単語は、同じ間隔がでてくる回数も多くなります。文字間隔が小さいと(特に26以下)役に立たないけど(鳩の巣原理)、文字間隔が大きいときは、実際の文字間隔だけが突出した値になります。平文が長ければ多ければ、誤差が大きくても正しい単語間隔が見つかりました。

  • 文字間隔から、実際の単語S[]の位置を探す

文字間隔dが既知となりました。文字間隔をdとしたとき、位置aと位置a+dが同じ文字になる場所を羅列します。横軸を単に順番のID(aの小さい順)、縦軸をaとしたとき、以下のようなグラフになります。

f:id:shindannin:20110816010843p:image

エクセルシートのA列が、縦軸のaです)

このグラフを見ると傾きが平らな部分と、急でガタガタな部分にはっきりと分かれます。この平らな部分が実際単語がある部分、急な部分はたまたま同じ文字が現れた部分になります。というわけで、急な部文と平らな部分の境界が単語のスタート位置になるのが分かりますが、ここで問題がありました。

  • 単語の位置は少しでもずれて置き換えてしまうと、その後の結果がひどいことになる。
  • 意外と平らな部分とガタガタな部分の境界を正しく求めるのが難しい(1階微分・2階微分いろいろ試しました。)

というわけでトップダウンの方法は諦めました。ただ、この平らな部分の傾きからerrorを求めることができるので、それは副産物として使用しました。

 |