Hatena::Grouptopcoder

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

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

2011-07-22

問題

22:03

平文を圧縮してください。平文の文字列長は500ぐらい~100000。圧縮後の文字列の長さ(辞書みたいなかんじ)も決められてます。例えば、以下のようなかんじに圧縮してください。

S[1] = bpa4h2edn2b3k2d3z2e43b

S[2] = 3i3ufx4uku34gzfob4vlozd3m

S[3] = juquvqvrudlpqezzzchprdwi

S[4] = kozid3pvevaytgjxdmjpfbsfhxrtovqp

暗号解凍アルゴリズムは決まってます。数字の部分xは、番号のS[x]の文字列に置き換えられます。解凍後の文字列が、元の文字列と同じであればあるほど高得点。その他、もとの平文はランダムで文字が置き換わる確率はテストケースで大きく異なります。

すごくざっくり言うと、「覚えられる単語数が極端に少ない辞書式圧縮で、劣化をできるだけ抑えよ」という問題です。

 |