Marathon Match 48

TopCoder

今回の題材は電子透かし。
個人的に今まで参加した中で一番面白い問題だった。

問題概略

プログラムは２つのパートに分かれている。

  • mark

ある波形Sと、整数N、ノイズの大きさCが与えられるので、Sを好きなよう改変してS1~SNを作って返す。

  • identify

作った波形のどれかにノイズが加えられて渡されるので何番の波かを推定。



１回の波形作成と、１００回の推定で１テスト。
ノイズは、まず10Cのガウス分布で全体上下一律シフトが入り、各値にCのガウス分布ノイズがかかり、さらに(1-C/20)の確率でなくなったりして、最後にC個ずつの平均をとるという操作。
スコアは(改変量^2+ミス)*2^ミス　で一番小さい人との相対評価。



データの埋め込みと読み込みの両方をやるというとても面白そうな問題だったうえに、賞金付きだったのでもちろん参加。

以下２週間の流れ
ローカルテスターに全ソースコードが残っているのでばっちり思い出せるｗ

１週目木曜~土曜

とりあえず、途中まで作ってあった汎用ローカルテスター(スコアを表で表示＆ソースコードと出力のバックアップ)を完成させ、ついでに今回の問題用のVisualizerを作った。

1週目日曜

ランキングが相対評価なので目標が分からないから、とりあえずてきとーなやつを書いて提出したらトップと1000倍差以上あってやべーってなった。

1週目月曜

約1000倍のスコアを達成。
この頃の方針はこんな感じ。
まずノイズかかったやつと元のやつとで位置合わせをするが、波の一部を部分的に微妙に上下に動かして信号を埋め込むとかすると、本来とは違う位置であってしまって上下の情報を取り出せない。
ずれても問題ないように信号を入れればいいので、自分もノイズを入れて、ノイズの大きさを信号としてみた。
これで約100倍。
あとは誤り訂正したらもう約10倍になった。

1週目火曜日

トップとの差もあんまりなくなってきたのでとりあえずてきとーにビットの高さとかの最適化。
確か2.5倍くらいになったはず。

1週目水曜日

突如閃いた方針を実装してみたらなんと当時のトップの10倍近いスコアが出てしまって潜伏決定ｗ
キーポイントは平均を取る操作の除去。
平均の操作は初めのC-1個の値を決めれば元に戻せるが、波形が連続なので、こいつらを変数として隣り合う値の差の二乗を最小化とかで最小二乗法すればほぼぴったりに元に戻せた。
これで位置合わせの精度が上がるわけだが、注目点は急な坂で、隣り合うやつとの差がCよりでかいからノイズが入ってもまずぴったりと位置が合う。
というわけで坂に幅１で隣との差の1/3以下の高さのビットを入れていけばほぼ完全に取り出せる。

2週目木曜日~金曜日

大学の課題をやっていてマラソンできなかった

2週目土曜日

いきなり断トツトップの点数の人が現れたので潜伏中止してとりあえず水曜のやつを提出。
だいぶいい感じの点が出たので方針はあってそう、というわけで最適化開始。
ビットの高さをどれくらいにするのがいいか分からなかったので、時間の余っているmark内で高さを変えてシミュレーションしてよさげなのを採用することにした。
これで3倍近くスコアが上がってとりあえずトップに。

2週目日曜日

チョー強いPsyhoが突如現るgkbr
位置合わせの精度を上げるべく最適化を試みたが高速になっただけでスコアが余りあがらなかったorz

2週目月曜日

またしても突如赤い人現るgkbr
シミュレーションの高速化を行い精度をアップさせた。

2週目火曜日

Psyhoに抜かれたorz
しかもやたら強いMITのplohが突如現るgkbr
誤り訂正の改良とビットの個数の調整をしてみたがあまり点数が上がらないorz

2週目水曜日

朝起きたらPsyhoに30%くらい差をつけられててorz
シミュレーションの爆速化を思いついたので実装したみたら10秒間で数千テストできるようになった、が全然スコアが上がらないorz
むしろちょっとミスしてもいいから攻めに行った方がいいんでないかと思ってパラメータいじったら少し上がってトップとの差15%

2週目水曜残り４時間

plohがやはり潜伏していたことがわかりorz
identifyも時間がかなり余っていたので時間のある限り色々な評価関数でやって総合評価でーとかやったら結構上がったので提出
10%くらい上がったがそれでも届かずorz
しかもplohはさっき提出したやつが8割しかとかないプログラムらしく断トツトップをとって行った…
強すぎだろーｗ



というわけでほぼ３位確定ぽいですorz
今回の反省点としては、ランキングを信用しちゃいけない、強い人はやばいスコア出して潜伏中ということ。
水曜の時点で断トツくさかったからと言ってのんびり課題やっていたのが間違いだった。
というわけで、次回からは潜伏しまくるぞ〜