今日解いた競プロの問題。

いろはちゃんコンテスト Day1-L: 答えを仮置きして二分探索する典型。仮置きした値をBとして、ORがB以上なる区間がK個未満なら答えはB未満。B未満なる区間がK個以上なら答えはB以上。

それはまあ良いとして、区間をどう数えれば良いのかだいぶ悩んだ。よく考えたら累積ORは単調増加なのでその性質を生かしてどうとでも料理出来る。自分は尺取り法っぽくやった。ORは逆演算ができないので、そこはセグ木で区間和を計算し直す実装にした。計算量は全体$O(N\log N\max A)$。

「K番目」を求めるための二分探索条件に悩んだうえ、にぶたん最大値の見積もりとKの型サイズを間違えて4WAした。適当にやってはいかんな。

---

以前にUnityを使っている人が紹介していた描画高速化周りに関する記事を読んだ。

https://zenn.dev/r_ngtm/articles/unity-study-srpbatcher

GPUとCPUの間の通信を減らす、コンテキストスイッチ的な処理を減らす、という大まかな方針はVulkanを直に使うときとあまり変わらないな。SRP Batcherについては若干よく分からない。マテリアルが同じなら単にDrawIndirectすればいいんじゃないのと思うが、違うマテリアルだけど部分的に情報が共通している場合に使いまわせますよ～みたいな話？