2011 TCO Marathon Match Round3 : StringCompression

TopCoder

結果が出たら追記する予定

解法

重要なのは2ヶ所だけ。落穂拾いも大事だけど。
基本線略はBFS+枝刈り。
探索を真面目にやると状態数が爆発するので、(圧縮率)*(正しい割合)をキーにして、大きい順にいくつか調べた。

候補となる文字列の列挙

何番目のスロットを使うか、というのは空いているスロットで全部試す。
まず、圧縮加工済みの文字列から、最低でも3文字位オープンにしたマスク(長さ16)を全部列挙する。
例えばa***3****2***みたいな。で、最も頻出なマスクを選ぶ。
次に、そのマスクに閾値以上の割合でマッチングする部分文字列を見つけ、前後64文字くらいの文字の出現回数をincしていく。
後は、指定された長さの部分和が最大になるような選び方をするだけ。

圧縮した文字列の生成

具体例を挙げてみよう。
元データが

zabccyabbdezacabcyef

とかのとき、圧縮する文字列がabcだと、次のような配列を用意する。

original | zabccyabbdezacabcyef
-------------------------------
S[2]=abc | 03100021000110300000

配列の中身に入っているのは、そこを起点としたときマッチングする文字数。これは計算量O(|元データ|*|圧縮文字列|)で計算できる。ただし、ここでの圧縮文字列の長さとは数字を展開しないものの長さ。
で、例えば閾値2以上の部分を圧縮することにするとz2cy2dezac2yefという文字列が得られる。これを元に次の圧縮文字列の候補を求める。
次にS[3]=2de=abcdeで圧縮する文字列を考えると

original | zabccyabbdezacabcyef
-------------------------------
S[2]=abc | 03100021000110300000
S[3]=2de | 03100041000110400000

が、既に計算した配列を利用することでやはり計算量O(|元データ|*|圧縮文字列|)で計算できる。
次は上流の方から圧縮していく。S[3]を圧縮する閾値を4とすると、

zabccy3++++zac3++++f

とする(+は確定済みの部分)。次にS[2]を閾値2で圧縮すると、

z2++cy3++++zac3++++f

となって、+を消去してz2cy3zac3fが得られる。あとは閾値を変更したりしながら進めていくだけ。
閾値は推定誤差を元に二項分布を仮定した期待値から2~3σを引いたものとしている(かなり甘い)。
上の作業で閾値を越える部分の区間が重複している時は、マッチング数の多い順に貪欲に選ぶ。

欠点

毎回元データそのものを圧縮するので計算量が大きい。なのでスロット数が大きくなるほど探索空間が狭くなってスコアが低くなる。

感想(簡易版)

ForumでのPsyhoさんの発言が実に共感できる。algo-ishとかshallowとかは自分も問題文を読んだ初日にそう思った。自分がMarathon中に使ったノートの1ページ目にはでかでかとク○ゲー臭と書いてある。
おまけに問題変更とかが挟まってストレスから正気ではいられなくなった。でもこの変更は多少MM-ish寄りな変更だったので自分には有利な変更だと思った。ただそれはあくまで結果論。自分としては、満点続出でRound 2の結果に委ねるというのでも良かった(Round 2の問題は割と多くの人が良問だと認めると思う)。ごく個人的な感想を付け加えるなら、この問題は正しいものを復元するだけなのでわくわく感が足りない。全然足りない。正直、TCOでなかったら参加を見送っていただろうし、参加してもモチベーションの観点から惨敗していたと思う。
とまあ、問題自体には負の印象しかないんだけどMarathon Matchとして見ればそれなりに楽しめた。特に、onsiteが12人なのに13~14位の所に壁があるのが実にドラマチックだ。当事者としては気が気でないけど。自分の落穂拾いが相当下手なのは知っていたので、ACRushさんがずば抜けたスコアを出しているのが実に頼もしかった。
他の参加者のseed1-500のスコアと比較すると自分のprovisional scoreは相当間引きしないと駄目っぽい。まあ、下がるのが自分だけでないなら大丈夫なんだけど。後は結果が出るまでお祈りでもして待つことにしましょう(MM中に放置していた雑多な課題から目を逸らしながら)。
(以下追加)
Forumを見たら概ね同じような感じ方をしていた人が多かったようだ。でも、こういう問題批判をしてると落ちたときの言い訳をしてるように見えてしまう（実際そういう意図が無いとは言わない）。やっぱりこういうのは通ってから批判するのがカッコイイ。
(追加２)
どうせ問題変更するんならerror率0.16以下のヤツは切り捨てて良かったんじゃ…。アレのせいでプレテストの個数が実質40とかになって正確さが失われた気がする。後、問題作成者って自分で自分の問題解いたりしなかったのかな
(追加３)
plohさんのregion alignmentsというのが気になる。75%置換されたのが復元できるって恐ろしく感じる。でも、こういう既に解法があるようなのはやっぱり止めてほしいと思ったりする。調査を怠った責任が自分にあるのは確かだが。