■ [MM]Marathon Match48 
SRMの回数が減ったなら、マラソンマッチをやればいいじゃない
とどこからか聞こえた気がしたので参加してみました。初挑戦。参加ガイドを書いてくださったEmKさんありがとうございます。
今回の問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13681&pm=10293
波形に電子すかしを埋め込んで、ノイズのかかったものからすかしを復元するという課題。
2009-01-17 土曜（3日目/14日間）
問題文を読む。難しー、と思う。
2009-01-20 火曜（6日目/14日間）
作成したすかし同士を区別するには、互いに直交した信号を埋め込めばいいのだろうと考える。
というわけで、すかしn番めは周波数n倍のサインカーブを波形全体にわたって足してやる、という方法にした。
復号では、各周波数のサインカーブとの積分を取って、値がもっとも大きくなったものを答えとする。たぶん異なる周波数のサインカーブ同士の積を積分するとほぼ0になって、周波数が一致している場合のみ大きな積分値が得られるので1つに特定できるはず。
しかしこれではだめだめでスコア0.00。
2009-01-24 土曜（10日目/14日間）
サインカーブ法の駄目な点は、たぶん次のようなもの。
- 領域全体にわたってすかしを埋め込むためすかし量が大きい
- ノイズによる幅方向のずれによってすぐ誤検出する
そこで、すかしをシャープにしようと、こんな信号を1ビットとして必要な数だけ埋め込んだ。表しているビットが0か1かによって、信号の形が+→-か-→+かどちらかになる。
┌┐
─┘│┌─
└┘
信号の幅は適当に選択。埋め込む位置は、とりあえず全体を等分した場所に。
復号では、埋め込んだ信号と同じ形の信号を掛けて積分し、正の大きな値になるか負の大きな値になるかでビットを判定する。
これでぎりぎり非ゼロのスコア（0.06）。
2009-01-25 日曜（11日目/14日間）。
ノイズがかかった波形から、失われた点を回復して元の波形と同じサイズに引き延ばすフィッティング方法を改良。これまでは単純に全領域相似変換するというひどい方法だったのを、極値を検出して極値の位置だけは合わせるようにした。
これに伴って、極値の検出を邪魔しないように、信号の埋め込み位置は極値を取る位置の中間くらいの適当な点へ変更。
手元のテストでは数十倍くらいになって期待していたのだが、提出してみたらさして上がらず（0.15）。
2009-01-26 月曜（12日目/14日間）
すかし信号の形を、+→-の形をやめて、+か-どちらかだけを加えるようにした。
復号は、たとえば+の値だけを埋め込んだ場合、1階微分を取ると+→-型の信号になってくれるので、それを積分して検出する。
1階微分を取ることのメリットは、フィッティングの誤差を軽減できること。値そのままを使うと、フィッティングにずれがあった場合に元波形との値の異なりが大きくてビットの検出が難しくなるが、変化率なら多少フィッティングがずれていても元波形とさほど変わらないので。
これで2.07。
2009-01-27 火曜（13日目/14日間）
違った方針をいろいろ試してみるが、結果は芳しくない。
この日は提出せず。
2009-01-28 水曜（14日目/14日間）
月曜日のものを元に2点改良。
これで3.34（暫定）。なんとか半分より上にこれた。ふぅ。
感想
アイデアを出して、実装して、スコアアップ、という繰り返しで非常に面白かったです。極値の検出とか、連続的フィッティングとか、ちょいっと書いたコードが動いてくれると嬉しいですね。とくに今回は図形的に視覚化できるものだったので喜びひとしお。これはSRMよりこっちのほうが楽しいかも。時間のプレッシャーないし。
解くための方法は多彩なので、終了後に他の人の方針を聞いて発見することもたくさんです。フィッティングに最小二乗法を使うとかなんで気づかなかったんだろう…。
ただ、レッドコーダーになるのはSRMよりもかなり難しそうかなぁ。今回1位の人のコードがやばいぞー。
