MarathonMatch48@TopCoder

MarathonMatch48の参加記事です。今回のお題は信号処理でした。信号処理をやっている研究室にいる自分としては、そこそこいい成績をとらないと研究室に顔向けができません！・・・と言いつつ、成績は微妙でしたorz

問題

長さLサンプルの波形(浮動小数の配列)が与えられる。この波形にN種類の"電子すかし"(数値変化)を加え、計N個の波形を返せ。
その後、上記の配列に対して"オフセット"、"ノイズ"、"サンプル欠け"、"ローパスフィルタ"という4種類の"攻撃"が与えられた配列が与えられるので、N種類のうちのどのデータかを判別せよ。

自分の解法

まずはじめに考えたのが波形全体に対して周波数と位相を計N種類ずらした正弦波を加え、判別時には加えた正弦波との相互相関をとり、最も相関の高いものを加えた正弦波であると判別とするという物です。結果は誤差が最小で1e13台、判別ミスはめちゃめちゃ多いという微妙なものでした。
次に考えたのがMDCTを使って低周波成分にデータを埋め込むというものです。研究室の先輩がそんな感じのことをやっていたため真似してみたのですが、基礎的な知識が足らず、うまくいきませんでした。
その次に考えたのは、i種類目の電子透かしを作るときに、波形をceil(logN)分割し、iをビット列と見立てて分割したフレームにビットに対応したオフセットを加えるというものです。また判別ミスを抑えるため、iにハミング符号を適用してみました。その結果誤差は1e10程度、判別ミスはCの値が大きい時以外はそれほどないという、まぁまぁなものになりました。
最後に考えたのは、オフセットをフレームの中央付近にのみ加えるというものです。このとき、ハミング符号は適用しないようにしました。最中的なテスト結果は以下のようになりました。

0) 7.46496E9
1) 7.728E7
2) 2.7659520000200006E11
3) 1.2096E9
4) 2.038824960064E12
5) 4.224E8
6) 3.75732E9
7) 1.386E10
8) 5.39136E9
9) 6.7645734929448305E18

途中結果

何とか点数はもらえました。全体の中でちょうど真ん中くらいにはなれたようです。上位の人たちが桁違いの成績を残しているのですが、全く持って想像がつきません。forumで上位の人たちのやり方を調べてみたいと思います。