第33回高専プロコン競技部門準優勝参加記

初ブログです。

とりあえず解法だけ書きます。エキシビジョン以外の問題はすべて理論値*1が出せました。
コードはここに置いています ↓
github.com
あんまりTexとかを書きなれてないのでシグマの添字とか細かいところを適当に書いてます。適宜雰囲気で感じ取ってください。

基本方針

問題データと読みデータをメルスペクトログラムに変換するとこうなります。

読みデータの面影がありますね。これを使ってなんかうまいことできそうです。
また、読みデータが重なっている位置と範囲がわかれば逆波形を重ねることによって重ね合わせ数の一つ少ない問題に帰着できます (この発想は大阪公大を含むいくつかのチームと同じです) 。
この「読みデータが重なっている位置と範囲」の推定を繰り返すことによって、すべての読みデータを特定することを目指します。

詳細

ステップ1

読みデータを一つ固定して、問題データのスペクトログラムの $(i,j)$ 成分を $R_{i,j}$ 、読みデータのスペクトログラムの $(i,j)$ 成分を $S_{i,j}$ とします。
ここでおもむろに、問題データのスペクトログラムの $r$ 列目と読みデータのスペクトログラムの $s$ 列目に関する評価値を、
$f(r,s)=\log \left( \sum_i \left( \frac{S_{i,s}}{R_{i,r}+1} \right)^2 \right)$
$g(r,s)=f(r,s)-\sum_i f(i,s)-\sum_i f(r,i)+\sum_{i,j} f(i,j)$
と定義します。
これらを各 $r,s$ に対して求めてプロットすると次のようになります。*2

明らかに斜めに線が入ってますね。これが正しい読みデータの重ね合わせ位置です。
問題データのスペクトログラムは、大まかに各読みデータのスペクトログラムの重なっている部分の和くらいの値になります。
正しい重ね合わせ位置だと問題データのスペクトログラムの値が読みデータより小さくなることはないので、 $r=s+i$ ( $i$ がスペクトログラム上での読みデータの"位置"になります) の直線上では評価値が小さくなり、それ以外の部分では (たまたま完全に重なることはそんなに多くないため) 比較的大きな値になります。
$g$ は $f$ にある縦横の縞模様を弱めて誤判定を減らすためにつけてます。少なくとも長い問題データでは効果がありましたが、本番のような0.5秒のデータではむしろ逆効果だったかもしれません。
各 $i$ で $r=s+i$ 上の $g(r,s)$ の値の平均をとることで、その位置に読みデータがどの程度含まれていそうかがわかります。

なんかイメージ ↓

ステップ2

その1で評価値が小さかった位置 $i$ (と読みデータの番号の組) から順に処理します。
スペクトログラムに変換ときに横幅がおよそ $\frac{1}{1024 }$ 倍されるため*3、スペクトログラム上での位置が分かっても逆位相を重ねる位置はわかりません。
$1024i$ の周囲適当な範囲を全探索して、逆位相を重ねたときの波形の絶対値の和が最小になる位置を求めます。ステップ1で候補を絞っているので愚直に $O(NM)$ ( $N,M$ はそれぞれ問題データ、読みデータの長さ) かけても計算時間は問題ありません。
このとき、 $i$ が間違っていて周囲に正しい重ね合わせ位置が存在しない場合もあるため、これを適当な閾値で弾きます。
この閾値を最後まで調整していたんですが、結局納得のいく感じにはなりませんでした。
(今考えたら、わざわざ一個ずつ正しいか判定せずに、すべての候補のうち一番良いものを選ぶ、みたいな方法 (大阪公大がやっていたもの) であれば閾値を考える必要がなかったです。)
(もともとこのパートでもスペクトログラムを使ってたんですが、波形の値を直接使っても同じようなことができることにパンフレットを見て気づき、競技一日目の夜に書き換えました。)

ステップ3

~~読みデータはトリミングされることがあるため、逆位相を重ねる範囲を計算する必要があります。~~
問題文を誤解していたようで、範囲を計算する必要はありませんでした。このパートいりません…

ステップ4

逆位相を足して、次の候補でステップ2を再度始めます。ステップ2で一定回数失敗すると停止して、再度ステップ1からやり直します。

その他

もともと機械学習でがんばるつもりだったのでPythonで書いていたんですが、最終的にPythonを使って得した部分は"スペクトログラムの計算をライブラリに任せられる"という点くらいでした。結局途中で言語を変えるのはめんどくさくて (他のチームメンバーが書ける言語も考慮して) Pythonのままいきました。
並列化しました。面倒な割に大した高速化にはなりませんでしたが*4、2倍くらいの高速化にはなりました。
今年は去年よりGUIを凝りました。残り時間とか使用済み読みデータとかハイパーパラメータを表示させるなど。

SA+LCPで一音しか重なっていない部分を線形時間で検出するソルバを書きました。0.1秒くらいしか重なってなくてメインのソルバだと検出できない、みたいなのを想定していたんですが、そんな問題は出なかったので用なしでした。
一部の読みデータが重なっていない分割データが多く存在することを考慮して、次の分割データを取得したときにボーナス係数の減少と新しく見つかる読みデータ数を比べてどの程度スコアが増える可能性があるか？みたいなのを計算する機能を作りました。一つ目の分割データにすべての読みデータが重なっていたので用なしでした。
複数取得した分割データが隣り合っている場合/隣り合っていない場合の場合分けや処理の最適化をかなり書きました。用なしでした。
すでに見つかった読みデータを一度戻して再度見つけなおす、みたいな処理をして間違った推定を防ぐソルバを書きました。用ありでした。

*1:一回戦で2つ分割データが必要だった問題があったんですが、1日目の夜に改善した結果理論値が出せました

*2:どっちの軸がどっちなのかはよく覚えてません

*3:1024はハイパーパラメータで可変です

*4:Numpyがそもそもうまくやってくれているのもあって？