![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="48" height="48"><rect fill-opacity="0"/></svg>)
今までこういうのあんまり突っ込んでなかったけど、二分探索が正しくない局面で二分探索をするのはダメな競プロerです！！アルゴリズムの使い方をただしく見極めましょう！！！
引用ツイート
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24"><rect fill-opacity="0"/></svg>)
二項しいぷ
@BinomialSheep
【競プロer同棲ないない】
浮気ラインを探るために伝家の宝刀†二分探索†をする
スレッド
新しいツイートを表示
会話
通じてなさそうなので解説！
二分探索は「OK判定もNG判定も十分な回数出せる」って前提の下で成り立ってます！
今回の場合は「NG判定の上限数が決まっているので、二分探索が適用できず、他のアルゴリズムを考える必要があります！（続）
引用ツイート
へだる
@hedalu244
返信先: @chokudaiさん
浮気判定には単調性がないってことですか？
例えば「浮気レベルが1~100の整数で表現できます。2回浮気レベルがボーダーを越えると離婚です。離婚しないで許容される浮気レベルを正確に知りたいです。何回の試行が必要ですか？」って問題を考えましょう。これは二分探索では解けず、DPなどで解けます！解いてみましょう！（続）
![画像](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="520" height="520"><rect fill-opacity="0"/></svg>)
よく見るとGoogleの問題は卵が2個割れてもおっけーだけど、さっきの問題は浮気を2回してしまうとアウトなので、別の問題でした＞＜