例によって昼すぎまで寝ていた。
ABC278に参加した。ペナを出さなかったのは良かったが、添え字ミスとかのしょうもない直しに時間を食ったので、もうちょっと手早く正確にやればもっと上位が狙えたように思う。というかサンプルケースが親切じゃなかったら無限にWA出してた可能性もある気がする。
A: A問題でforの要る問題を出さないという制限は完全に消えたらしい。
B: 1分ずつ回していくだけ。
C: map<int, set<int>>
D: 操作1で全ての値をリセットするくだりがボトルネックになる。どうせ一度に1つの値しか求められないことを踏まえると全てを一時に更新する必要はなく、「最後に操作1が行われた時刻」と各値についての「最後に操作1を反映した時刻」を記録すればよい。操作2,3が行われるたびに対象の要素の「最後に操作1を反映した時刻」を見て、必要に応じて更新すればよい。
E: 各数値の出現数を愚直に数えていると全体$O((H-w)(W-w)HWN)$になってしまう。あらかじめ2次元累積和で各数値の出現数を求めておけば任意の長方形内の数値の出現数を$O(1)$で求めることができ、全体$O(HWN)$で解ける。
F: シンプルなゲーム問題。どの文字列が既に使われたか、最後にどの文字列を使ったかを考えると状態数は高々$N2^N$通りなので、ちゃんと後退解析すれば問題なく求まる。
G: 解けず。grundy数を求めようと思えば求められそうだ、というのは分かったのだが、10^9オーダーなのでいくら定数倍が小さくてもTLには間に合わない。解説を読むに、やはり「それは一応正しいけど高速化が要る」という感じらしい。
想定解は真似っこ戦略というやつらしい。趣旨は分かるがテクニックとして抽象的すぎて、次同じような問題が出てきてもちゃんと応用できるかどうか怪しい。
最近のABCはGでやたら高度な典型？が出されている気がする。この辺をちゃんと履修していけばARCにも通用するようになっていくんだろうか。
OpenAL-softがLGPLで扱いにくいので、代替手段をちょっと調べた。libsoundioが選択肢の中では悪くなさそう。だが、AndroidNDKで使えるかどうかが未知数。libsoundioはALSAバックエンドらしく、ALSAならandroidでも一応使えてもおかしくないのかと思うが、分かりやすい資料が見当たらない。
明確にAndroidで使えるものとしてminiaudioおよびsoloudというやつを見つけたが、vcpkgで入れられない。
また、どれを使うにしてもOpenAL-softのようにHRTFを簡便に適用するのは難しそうだった。自力実装を見据え、OpenAL-softのHRTF実装をちゃんと読んでみることにした。
どうやらHRIRを愚直に足していってるっぽいことが分かった。周波数空間上でかけ算をしているのかと思っていたが、そういうことはないらしい。ちょっと計算量的に重そうな気がするが、まあ定数倍は軽いだろうから問題ないのだろう。
https://github.com/kcat/openal-soft/blob/master/core/mixer/hrtfbase.h#L17
https://github.com/kcat/openal-soft/blob/master/core/mixer/mixer_c.cpp#L88
また、HRTFの測定点の間で補間処理を行っていることが予想されたが、実装としてはおそらく「2つのフィルタから出た音を補完している」っぽいことが分かった。2つのフィルタを合わせて新たなフィルタを作っているんじゃないかと思っていたのだが、そんな面倒くさいことはしていないようだ。
https://github.com/kcat/openal-soft/blob/master/core/voice.cpp#L396
使うフィルタを選定する処理は見つけられなかった。そもそもHRTFのデータの形式自体よく分からん。
2.5kmジョギングした。なんか普通に走り切れてるな。
Categories: 未分類