にぶたん談義

Hideyuki Tanaka @tanakh

gitにも二分探索するコマンドあるもんなあ

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

二分探索は半開区間で、 while (l+1 < r) { int c = (l+r)>>1; if (is_ok(c)) l = c; else r = c; } という定型を使ってるなぁ。このタイプは、lとrのどちらがokなのかを意識するだけで良い。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

（逆向きなら r = c; else l = c;）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

半開区間だと真ん中を求める式が簡単、閉区間だと端を一個ずらすのを気にしなくていいというメリットがあるかな。めぐるちゃん式はどっちがokかを考えなくていいというメリットがあって、これも結構良さそう。まぁ自分の好きなタイプを使えばいいと思う。

kuuso @kuuso1

にぶたんは紆余曲折を経て int c; while(r-l>1){c=(l+r)/2; if(isOK){}else{} ) while(isOK)c++; while(!isOK)c--; という変則定型に落ち着いた。 後ろ2つはupper/lowerbound相当を調整する。

kuuso @kuuso1

（おおざっぱにlogで探索範囲狭まってるんだからあとは線形で多少探してもええやんって感じ）

hogeover30 @hogeover30

hirose_golfさんとかMi_Sawaさんが言ってた頭よさそうな二分探索やっと理解して使えた

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

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

拡大

拡大

拡大

拡大

beepcap @beepcap

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

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

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

beepcap @beepcap

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

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

@beepcap 振動しない代わりにオーバーフローするからこの場合ダメですよね？（そもそも精度が足りないのが問題、って話です） 固定回数のループは、「差をこれだけ縮めたい」っていうのを明確に記述する上で最も有効です。（今回は/2の処理を100回できる、というのが明確になる）

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

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

beepcap @beepcap

@chokudai 後半の意味はさっぱりわかりません。前半は目的のない関数なので、何がダメなのかはわかりませんが、もしもオーバーフローを気にするのであれば、多倍長の演算が行えるライブラリを利用すべきです。

beepcap @beepcap

@chokudai かりに、後半の話で100回行ったから、それがなんなのでしょうか？

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

@beepcap 理解できないなら説明しないでいいやって感じになったからいいです・・・（二分探索で達成したいことをわかっている人向けの話でした）＿

beepcap @beepcap

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

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

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

beepcap @beepcap

実数の二分探索になんで深度がだいじなんだろう？

beepcap @beepcap

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

beepcap @beepcap

何回目で振動が始まるかはとても大事な要素だけど、振動した結果を含めたものが100回に達したという情報はなんのやくに立つんだ？

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

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

beepcap @beepcap

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

beepcap @beepcap

おおよそってのはどうでもいいんだよ。 (まぁ、RSAの例もあるけど)

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

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