三分探索談義

not @not_522

三分探索は関数が凸じゃなくても使えて、単峰性を持っていれば十分

not @not_522

これ無限回言ってる気もするけど、どうせ定着しないので今後も無限回言って行きます

beet @beet_aizu

@not_522 単峰性って具体的にはどう定義されますか？

not @not_522

@beet_aizu たぶんよくある定義は「極値が一つ」だけど、「微分が0の有限の長さを持つ区間が存在しない」も入れないと壊れるはず(もう少しゆるい条件でもいいのかも…)

みさわ @Mi_Sawa

@not_522 3分探索は local optimum を一つ見つける 任意の local optimum が global optimum である(特にlocal optimum が一つしかない)ならば3分探索は global optimum を一つ見つける あたりがよい特徴付けな気がします

てんぷら @tempura_cpp

pic.twitter.com/2c9fBcFNEM

拡大

やぱた @odenmonster

三分探索や黄金探索で盛り上がるコミュニティ良い意味でだいぶ狂っている気がする

のみ @nomikura

「Linear Approximation 」 Σの式を変形すると嬉しくなるやついつも解けない。 qiita.com/nomikura/items… #Qiita

のみ @nomikura

これ3分探索でも解けるって聞いた気がするけどあれって値がユニークじゃないとできないんじゃなかったっけ？

31536000 @CuriousFairy315

@nomikura そんなの有りましたっけ？ 凸関数なら解けた気がしますが

31536000 @CuriousFairy315

@nomikura 反例できました 確かにユニークじゃないとダメか……あらら

のみ @nomikura

@CuriousFairy315 二分探索ならいけたっぽいです。3分探索はできるかわからないです twitter.com/lumc_/status/1…

31536000 @CuriousFairy315

@noshi91 @nomikura このケース、どっちを切り捨てれば良いんでしょうか pic.twitter.com/cV74VRdnNF

拡大

⚡すく⚡ @0214sh7

三分探索の話をやめてガイダンスを三分聞きなさい

⚡すく⚡ @0214sh7

Linearうんちゃらは三分探索で解いた記憶ある

kichi2004 @kichi2004_

三分探索って log log Nですか

QCFium @qcfium

@kichi2004_ logNです

kichi2004 @kichi2004_

@qcfium そしたら今無理に覚える必要はないですかね、、

QCFium @qcfium

@kichi2004_ まぁ二分探索とは性質が違うので... 出てきたら覚えれば良いと思います

ふるやん @furuya1223

三分探索は平らなところが探索範囲内の最小値以外にあると失敗し得る

31536000 @CuriousFairy315

三分探索な時点で今更な気が というか別に追い抜かしたりする訳じゃないんだから、誤差でうっかり極値を範囲外にすることって無くね

QCFium @qcfium

僕は離散なものに対しては差分で二分探索します(あるところまでは一つ右との差が非負だけどどこかから負になるみたいな感じで) というか三分探索を書いたことがないことに気がついた

ふるやん @furuya1223

競プロ的な文脈で誤差が怖くない場合はm1=(l+r)/2, m2=m1+1 にすれば底が約2になって速いみたいな話を聞いたことがあって、実用的な使い道があるのが疑問に思ったことがある

えびちゃん🍑🍝🦃 @rsk0315_h4x

離散だとにぶたん，わかるなぁ

えびちゃん🍑🍝🦃 @rsk0315_h4x

黄金比分割探索って三分探索にくくられるものとしていい？ それとも別？