第33回高専プロコン参加記
2022/10/15~16に開催された高専プロコンの参加記です
目次
- 開発環境など
- 競技ルール
- 問題文の誤読について
- 誤読した状態での解法
- プログラムの高速化
- 練習結果
- 大会当日の話
- 大会に出た感想
- 誤読していない状態での解法
- 修正後の実行結果
- まとめ(感想など)
開発環境など
OS：Windows10, Ubuntu(macでの仮想環境)
使用言語：C++(mingw, gcc)(ソルバーなど), Python3(通信プログラム)
使用ライブラリ：なし
GitHubレポジトリ(汚いのは許して)：https://github.com/UScuber/procon33
開発期間：募集要項が公開された4月から大会(10月)までゆっくり進めてました
競技ルール
募集要項(https://www.procon.gr.jp/wp-content/uploads/2022/04/7cd7daa1edc6ad3c7077207f1814c2fc-1.pdf#page=9)に書かれています
読みデータの読みの開始位置をずらしたものが複数重ね合わせられたものが問題データとなっています
問題文の誤読について
読みデータの読みの開始位置をずらしたものが複数重ね合わせられたものが問題データとなっています
僕がそれに加えて、問題データの中で札を読み始める位置が変わるという風に勘違いしてしまいました
大会終了まで気づかずに問題に取り組んでいたので、とりあえず誤読した状態の問題の解法を説明していきます...
誤読した状態での解法
今回は焼きなまし法を使いました
ここではNを重ね合わせられている札の数とします
音声データに含まれている札の種類、その音声の開始位置、長さ、音声データへの貼り付け位置の4つの状態をN個、合計4N個のパラメータをランダムに変更しながら問題データへと波形を近づけていきます
4N個のパラメータと読みデータから音声波形を足し算で合成して、受け取った音声データとの波形の差の総和をスコアとしてそのスコアの最小化を目指していきます
始めはシングルスレッドで音声のサンプリング周波数を2000[Hz]にして大まかに推測し、最後にマルチスレッドで6000[Hz]にして解析して少し精度を上げるという感じでやりました
具体的に、焼きなましの近傍の探索はこんな感じに行いました↓
焼きなまし法の近傍(前半)
- 選択中の札を選んで、長さと開始位置、貼り付け位置をすべてランダムに変更
- 選択中の札を別の札に変えて、長さ、開始位置、貼り付け位置をすべてランダムに変更
- 選択中の札を選んで、長さを前後約0.3秒ランダムに変更
- 選択中の札を選んで、長さ(音声の始まりの部分)を前後約0.3秒ランダムに変更
- 選択中の札を選んで、音声の貼り付け位置を前後約0.3秒ランダムに変更
- 選択中の札を選んで、音声開始位置を前後約0.3秒ランダムに変更
- 選択中のある札の別の札に変更
- 選択中の札を選んで別の札に変更し、ほかの選択中の札の情報(長さなど)に変更
焼きなまし法の近傍(後半)
- 選択中の札を別の札に変えて、長さ、開始位置、貼り付け位置をすべてランダムに変更
- 選択中の札を選んで、長さを前後約0.3秒ランダムに変更
- 選択中の札を選んで、長さ(音声の始まりの部分)を前後約0.3秒ランダムに変更
- 選択中のある札の別の札に変更
- 選択中の札を選んで別の札に変更し、ほかの選択中の札の情報(長さなど)に変更
プログラム実行時、前半と後半に分けてそれぞれ遷移を変えました
前半と後半で分けたのは、前半だけにある遷移が最後のほうになるにつれて使われなくなっていったからです
プログラムの高速化
音声のサンプリング周波数を下げる
ある程度速度が出て、分析がうまくできる周波数を探しました
シングルは2000[Hz]でマルチは6000[Hz]で解析するのが一番良かった
関数のインライン化
大量に呼ばれる関数はinlineを付けたり、行数が短ければ直接埋め込んだりして高速化をした
実行ファイルが高速に動くコンパイラを探す
最終的に普段使っているmingwが一番速かった
高速なコンパイルオプションを探す
-O3とか-Ofastなどの最適化オプションなどを付けて探してみる
-Ofast -unroll=4が一番良かった
近傍の変化の種類によってスコア計算を場合分け
ちょっとだけ速くなった(そんなに変わらん)
練習結果
長さ8秒弱、札20枚の音声データを作成して150回テストした結果です この時は札20枚で、1回の解析に5分かけてました
(analyzeディレクトリのresults6.csvに結果が載ってます)
焼きなましの一回の実行時間は]くらい(1秒間で大体
回ほど)で実行してくれます
大会当日の話
大会結果はここから見れます：https://www.procon.gr.jp/?p=78751
予行練習
ネットワークの接続で多少戸惑ったが、何とか通信できるようになった
解析のプログラムもうまく動いてそうで安心
受け取る分割数は全部でなくても行けそうだったので1回戦までに分割データを一部だけ受け取れるようにプログラムの修正をした
1回戦
すべて分割数2にしてパーフェクトを狙った
予行練習よりも圧倒的にスコアが高くて不安だったけど何とかなった 1回戦は無事1位で通過
1日目の夜
分割数1にしたときにバグが発生したのでそこを修正
原因は、問題データに入っているすべての読みデータは1秒以上流れているというのをプログラムに入れており、1秒未満の分析の時に配列外参照をしてしまっていた
訂正後、1回戦のデータをすべて分割数1で実行するとすべて正解だったのでこのままでいくことにした
そのあと、特に直すところはなさそうだったのでABCに出る
準決勝
少し攻めて分割数をすべて1にしてパーフェクトを狙い、大阪公大と弓削と同率になるという作戦で行く
最初は数の指定ミスで2にしてしまったが、何とかパーフェクトで1位通過
松江高専が敗者復活戦からかなり精度を上げて迫ってきてる
お昼に、決勝では分割数の指定をミスしないように分割数をあらかじめ指定しておくようにプログラムの変更をした
決勝
分割数はすべて1で行くことに(ここで取らないと上位に行けないので)
1問目の結果
最初、札の枚数が12枚とそれなりに多く、かなり精度が落ちてしまった(ここで5ミス)
残りの2~4問目はミスした部分を変更札にしていきながら何とかすべて正解
最終結果は......
4位でした
分割数を1にして攻めてみましたが、1問目の5ミスがスコアにかなり響いてしまい、松江高専と差をつけられてしまいました...
大会に出た感想
もともとは決勝戦出場を目指してやってきたので決勝に出れて嬉しかったんですが、長い期間やってきた分、3位を譲ってしまったことにかなり落ち込みました
自分にもっと実力があればなと思ったりとかもしました
高専プロコン自体はめちゃくちゃ楽しかったです
大会終了後
募集要項が公開されてからずっと誤読していたことに気づく。
もし、元から気づいていれば3位になれたのではないかと思い、かなり落ち込んだ。
誤読していない状態での解法
長さと張り付け位置は常に変わらないのでそのパラメータを取り除いてコードを修正していきます
さっきの解法のコードよりもだいぶシンプルになってます
ソースコード：https://github.com/UScuber/procon33/tree/fix
修正後の実行結果
大会で出題された問題をすべて分割数1で実行してみました
1回戦
1回の実行は1分以内でできて、2~3回実行すればどれかが確実に完全一致した
焼きなましの近傍1回の実行時間はは大体]～
]くらいでした
準決勝
準決勝～順位決定戦の問題データの一部をいただいたのでそれを使わせてもらいました(ありがとうございます)
実行時間は少し長めにして実行
温度を調整して実行してみると、すべて完全一致
いい感じ
決勝戦
1問目で2ミス(うーん...)
2~4問目は完全一致
順位決定戦
9/20個一致でした(かなりひどい)
大会で使ったプログラムだと分割数1で15/20個一致でした
もうこれは乱択の限界な気がする
まとめ(感想など)
今回のプロコンの関係者の方や、自分のチームを応援してくださった方、ありがとうございました！！
問題の誤読が原因で決勝戦で解析がうまくできなかったので、来年は募集要項を読み込んで、たくさん質問できるような状態にしていこうと思います。
来年は3位(あわよくば2位)を目指して頑張ります！！！
