202130500

人力二分探索をする機会はよくあるけれど、たいてい途中で間違えて区間を適当に伸ばすはめになる。ノイズがある場合の二分探索について知っておく必要がある。素朴に区間の存在確率を持っておいて、一番大きい区間を分割していくと O(log^2(N) * f(間違える確率)) くらいか。いやこれは正しくないな。同じ確率で幅の違う区間があったら、幅の狭い区間を探索すべきだ。ええと...。