7位/44 Rating 1694→1783
裏マッチだったので、強いのはcolunさんだけなのに、7位。結果のわりには、レートは上がったのは、たまたま自分より上の順位の人が新規の方ばかりだったから。結果を反省せねばなりません…。
平文を圧縮してください。平文の文字列長は500ぐらい~100000。圧縮後の文字列の長さ(辞書みたいなかんじ)も決められてます。例えば、以下のようなかんじに圧縮してください。
S[1] = bpa4h2edn2b3k2d3z2e43b
S[2] = 3i3ufx4uku34gzfob4vlozd3m
S[3] = juquvqvrudlpqezzzchprdwi
S[4] = kozid3pvevaytgjxdmjpfbsfhxrtovqp
暗号の解凍アルゴリズムは決まってます。数字の部分xは、番号のS[x]の文字列に置き換えられます。解凍後の文字列が、元の文字列と同じであればあるほど高得点。その他、もとの平文はランダムで文字が置き換わる確率はテストケースで大きく異なります。
すごくざっくり言うと、「覚えられる単語数が極端に少ない辞書式圧縮で、劣化をできるだけ抑えよ」という問題です。
放送中に、chokudaiさん、yowaさんから頂いたアドバイスなどを元に反省。
例えば、"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点で最高。
今回、問題が途中で変更になり、error値が大幅に大きくなりました。そこで、平文がerrorによりぐちゃぐちゃになっても、まだ残っている情報ってなんだろう?「実は長い平文のほうが、残っている情報が多いから、復元のチャンスがあるのでは?」と思い、やってみたのですが…
同じ文字の間隔を使えないか?
ABCDEFABXDE
A-A 文字の間隔 4
B-B 文字の間隔 4
D-D 文字の間隔 4
E-E 文字の間隔 4
よく出てくる単語は、同じ間隔がでてくる回数も多くなります。文字間隔が小さいと(特に26以下)役に立たないけど(鳩の巣原理)、文字間隔が大きいときは、実際の文字間隔だけが突出した値になります。平文が長ければ多ければ、誤差が大きくても正しい単語間隔が見つかりました。
文字間隔dが既知となりました。文字間隔をdとしたとき、位置aと位置a+dが同じ文字になる場所を羅列します。横軸を単に順番のID(aの小さい順)、縦軸をaとしたとき、以下のようなグラフになります。
(エクセルシートのA列が、縦軸のaです)
このグラフを見ると傾きが平らな部分と、急でガタガタな部分にはっきりと分かれます。この平らな部分が実際単語がある部分、急な部分はたまたま同じ文字が現れた部分になります。というわけで、急な部文と平らな部分の境界が単語のスタート位置になるのが分かりますが、ここで問題がありました。
というわけでトップダウンの方法は諦めました。ただ、この平らな部分の傾きからerrorを求めることができるので、それは副産物として使用しました。
■ファーストインプレッションとその結果
■キーワード(調べ物するとき用)