Marathon Match 39

賞金付きな上に車校が仮免試験結果待ちで週末なかったので久しぶりにマラソン参戦
今回は暗号を解読しろっていう問題
コーディングフェイズが終了した段階で同率２位
点数は99.98だけどローカルで１万個実行して9999.44だったからもうちょい上がるはず…
まぁ他の人も上がりそうだからあんまり意味ないけどｗ

以下自分の立てた戦略

まぁテキトーに解読して一番英語らしくなるものを選ぶしかないだろうということで、方針決定
英語らしさの判定には隣接文字列の出現頻度を使うことに
ファイルサイズが300KBまでと決められているのでせいぜい隣接４文字までしか埋め込めないかと思ったが、上位の人がやばい得点を出していたのでこれは５文字埋め込むしかないなと思って、圧縮開始ｗｗ
９割くらい圧縮に時間を使ってたような気がしなくもないｗ
ASCIIなんで7bitなんだよーとか苦しみながらも、ハフマンしまくったり、英語であることの特性を活用したりして、最終的に300KB内に隣接５文字の出現頻度の対数取って整数に近似したものと、元の文章丸々一個埋め込むことに成功した
少しでも情報量を増やすためにASCIIの制御文字まで使っちゃたけど大丈夫なのかは知らないｗ
元の文章も一つ埋め込めたのでそこから出題されれば100%満点が取れる
あとは埋め込んだ出現頻度表から確率計算でDPして終了
確率の計算は、文字列Tの出現頻度をP(T)とすると、ある文字列Sの後に文字cが続く確率はP(Sc)/P(S)ってなるだけ
実は隣接５文字で出現するのは26^5のうち35万個くらいしかないので猛烈に枝が刈れて制限時間20sなのに解凍＆初期化を除くと0.1sとかで解けるようになったｗ
10000個テストしても15分くらいで終わる

とまぁこんな感じ
少しでもいい順位取れるといいなぁ