2011-07-31 - TopCoderの学習のお時間

ある法則で生成された、同じパターンが繰り返し出てくるような文字列がある。

その中の文字の何割か（どのくらいの割合かはテストケースごとに大幅に違う）がランダムに違うものに置き換えられた文字列が与えられる。

それを元に、最初に文字列を生成するのに使われていた法則を推測して、与えられた文字列をできるだけよく復元せよ。

1段階ずつ元のキー文字列を推測していく。

同じパターンが何回も登場するところが一番奥のキー文字列に該当するだろう、ということで、隣接する4文字のパターンがそれぞれ何回出現するかを数える。

出現回数が多いものから上位いくつかに対して、出現箇所の前後30文字くらいの各位置でそこにある文字のヒストグラムを作る。

適当な評価関数を元に、ヒストグラムがよく1位の文字に集中してるっぽい範囲をキーの文字列候補とする

ただし、エラー率が大きい場合は隣接4文字パターンが一番たくさん出現するものでも5回とかになってほとんど意味のある情報が得られないので、

そのような場合は文字列の先頭5000文字くらいから全部調べる。圧縮のルールから、キー文字列はある程度最初のうちに必ず出現することが分かるので先頭のほうだけ調べれば良い。

キー文字列の候補が推測できたら、正解の可能性が高そうなものから順に、圧縮する→次のステップに進む　をDFS的に繰り返す。

圧縮では、間違えて圧縮しすぎてしまったら後のステップでキー文字列が推測不可能になって致命的なので、最初はエラーの許容度をきつめにしておく。

後のステップで圧縮するときに、前のステップでの圧縮し残しをゆるめに判定してまとめて圧縮する。

最後にランダム解を時間いっぱい試す。

キーの順番をランダムに決めて、キー文字列のランダムな位置に数字を配置する。

それを展開して正解の文字列と比べることで、キーの（数字が埋まっていない）各位置でどの文字を入れるのが良いか数えた、というだけ

中盤以降は、どういじっても別のところが悪くなってまったく良くならなくなってしまった。それで「全部当てようとしなくても前半のほうだけ当てるような方法があるんじゃないか？」という的外れな方針を探りに行ってしまった。
- そんな方法はない、というのを早く見抜いてもっと本流のほうを考えるのに集中できていたらちょっとは違ったかも
デバッグ出力を眺めてどこで推測に失敗しているかを探す作業が延々発生するのだけど、そのためのログ出力があまりうまくできていなかった感がある
- こういうのってつい最初に作ったやつをそのまま使い続けてしまうのが良くない。それを何度も使うことになるのだからもっと真剣に考えておくべきだった
しかし、こういう"正解"を出せ、という問題はとても苦手なのだけどその割には頑張ったような気もする
仕事の都合などで、時間的には過去に参加したMarathonの中で最低なくらいしか使えなかったのも痛かったか
言い訳は色々できるけれども、どうにしろ通過組とのはっきりとした差は感じる。方針を考えるときに勘で進んでいっちゃうことが多いけど、その方針でどれだけ行けるか検証するプロセスを充実させないといけないのだろう

この順位でもレートは意外と上がった。

オンサイトはまた来年…