discordの通話音声をbotで取得する方法について調べていた。discord.pyを今までbot開発で使っていたのだがそちらでは実装されておらず、py-cordというフォークでは実装されているらしい。なのでそちらを使った。
VoiceClientクラスのstart_recordingメソッドによって録音が行える。引数としてSinkクラスのオブジェクトを渡す形になっていて、Sinkクラスを継承したWaveSinkとかMp3Sinkといったクラスが用意されている。こうしたクラスを使えば任意のフォーマットで書き出せるようだ。
ただ今回は書き出しが目的ではなくデータを取りたいという用途。自分で生の波形データをハンドルしたい場合、Sinkクラスを継承してwriteメソッドをオーバーライドすればよいようだ。ただこの使い方はあんまり想定されている雰囲気ではなく、ちゃんと内部実装をある程度理解して使う必要はある。
ABC294に出た。冷え冷え。
A: やるだけ
B: やるだけ
C: A,Bそれぞれの各要素について値と元の場所のペアとしてひとまとめにソート
D: std::setで呼ばれるの待ちの人と呼ばれたけど行ってない人を管理すればよい。
E: 尺取りっぽくやればよい。細かい部分の実装で手間取った。
F: 最悪。基本的な発想は全て合ってたのにただのオーバーフローに気付けず解けなかった。
基本の方針としては濃度を二分探索する。混ぜた砂糖水の濃度がb以上となるような組み合わせがK個となるような濃度bを二分探索すればよく、一回の判定がある程度高速にできれば良い。
全ての組み合わせを取れば当然判定にO(NM)かかりTLEする。そこで高橋君が持っている各砂糖水に対して、濃度をb以上とするような青木君の砂糖水がいくつあるかを二分探索できれば良さそうな気がする。これができればO(NlogM)で一回の判定が出来ることになる。(当然高橋君と青木君の立場はどちらでもよい)
問題は青木君の砂糖水の二分探索で、単調性をどうにかして見出さなければならない。頑張って式変形すると以下の式が成り立つことが分かる。
$\frac{A_i+C_j}{A_i+B_i+C_j+D_j}\geq b\leftrightarrow A_i-b(A_i+B_i)\geq b(C_j+D_j)-C_j$
ということで$b(C_j+D_j)-C_j$でソートすれば単調性を得られることが分かる。ソートにかかる時間はO(MlogM)なので濃度の二分探索判定のたびにやっても問題ない。これで一回の判定がO((N+M)logM)でできた。
「多数ある組み合わせの中の上からK番目」を得るために、ある値以上の組み合わせの個数を見て値を二分探索するというのはド典型なので割とスッと出た。ただ、毎回ソートしなおすことで単調性が出るというのは初めて見たパターンだったので面白かった。その辺にも気づけただけに、ただのオーバーフローを見逃したのがあまりにも悔しい。50000^2がintに収まらないのは分かっていたのだが、lintの中にintが埋まっていて見逃していた。
G: 分からず。重みの更新はさておき、木で任意の2点間の距離を取るクエリに高速に答えるとなると選択肢は限られる。自分にはLCAしか思いつかない。重みの更新をどうやるかは全く分からなかった。こんなのを600人以上が解いているのか。
Categories: 未分類