二分探索について、chokudai氏とbeepcap氏との議論をまとめてみた

古寺いろは@競プロ応援アカウント @codera_iroha

【アルゴリズム雑談】 答えが小数になる二分探索の問題についてですよ！ 難易度：★★★☆☆ pic.twitter.com/pxQCvXufgl

拡大

拡大

拡大

拡大

beepcap @beepcap

えーーーー 定数回のloop処理は悪手だし、そもそも固定小数点数を使えよ・・・

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap 固定小数点数だとどう解決するんですか！定数回のloop処理だとどう悪手なんですか！

beepcap @beepcap

@chokudai 固定小数点数ならそもそも切り捨てだから振動しませんし、固定回数のループはループを抜けてきた時に振動が発生しているのか、それともループ回数が不足していたのかを別途判定する(しかも、最悪またループしなきゃ！)すひつようがある時点でナンセンスです。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap 「別途判定が必要になる」というのであれば、あらゆる処理が「十分であるかどうか判定する必要がある」ということになります。競プロのように（当然競プロ以外でも）、値域が与えられている問題に対し、「別途判定を書かなきゃいけない」と考えるほうがおかしいです。

beepcap @beepcap

@chokudai ああなるほど、実問題ではなく競技プログラミングだから使えるテクニックということですか。なるほど、これは僕の観点が間違っていました。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap 競プロ以外では、処理すべてにおいてどんな値域の数が与えられるかまったくわからない、と主張されるのであればその通りです。（当然自分はそのつもりで書いてないですけどね）

beepcap @beepcap

@chokudai いいえ、そういう意味で言っていません。しかし、ある式が収束しうるかは、入力値の範囲のみでは分かりかねると言っています。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap 要求する絶対誤差がaで、返す値としてありうる値の最大値と最小値の差がbとすると、二分探索の終了条件はおおよそlog2(b/a)回ですよー。（まぁ、さっき言った通り、精度の問題があるので理論値ですが） 相対誤差の場合も同様に求められます。

beepcap @beepcap

@chokudai ああいや、その話は理解できますよ。しかし、終了条件が何で抜けてきたかを判断出来なければ駄目ではないの？という疑問です。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap ん？そうなんですか？「これは絶対誤差で抜けてきたからこうして、これは相対誤差で抜けてきたからこうする」ってのがわからないとダメ、って話ですか？そうではなく？

beepcap @beepcap

@chokudai そうではないのですが、相対誤差、絶対誤差かんけいあります？ 僕は単に複数の終了条件で同じ処理に入るときに、どの終了条件かを判定出来ないケースがないかと言っているつもりなのですが。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap あ、複数の終了条件の具体例（今回の場合は元ツイートに合わせた）つもりです。判定できないケース、というか、判定するのが必要であれば、まぁそれを返すように組むべきでしょうね。見たことないですけど。

beepcap @beepcap

@chokudai うーん？それはつまりあの例の関数は「振動している事が分かれば十分」ということですか？

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap まぁ「どっちかの条件を満たした」ってのが分かれば十分、という認識です。（数が変わらないのって振動っていうんですかね？） 正直何が言いたいかわからないのでお手本コード見せてもらえますか＞＜

beepcap @beepcap

@chokudai えーっと、double型で2分探索を行う場合という前提がもう間違ってて、固定少数点数を使えよという話なので、前提はdoubleじゃなくていいですかね？

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap まぁ、要求仕様によっては、多倍長を使った時点で十分な速度が出ず、固定小数点数を使った時点で十分な精度が出ないと思いますので、そこが本質ではないと思いますけど、別にいいですよー。

beepcap @beepcap

@chokudai 言いたい事は言ってしまった気もするので、こういうことで。 (ビルドも通してないけど) pic.twitter.com/i5MYxT4KCW

拡大

beepcap @beepcap

なんだろう、100って決め打ちにすると、探索が終わらないうちに処理が終わる危険性が無いかって話が、なんでこじれるのだろう。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap あ、もしかして要求誤差が1e9ではなく1e-9であることがかみ合っていない・・・？

beepcap @beepcap

@chokudai いや多分違うんですけどなんだろうなぁ・・・多分最初から「深度から考えて十分な値を回数として与える」というコードになっていたら、きっとなんかなんにも気にならなかったような気もします。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap ぶっちゃけ、突っ込まれポイントとしては、「いやそこは100じゃなくてMath.Log(2, b-a)+2くらいにしとけよ、とか言われたら、「確かに定数だと無駄生じるけど、そこの計算のミスのが怖いから定数にしてるけど、まぁ厳密に書けたほうが良いよね」とは（続き）