編集部が厳選した「いま、みんなに見てほしいまとめ」をイチオシとして紹介しています!グサッと刺さる良質まとめはこちら!

にぶたん

まとめました。
プログラミング
3605view 0コメント
このまとめをお気に入りにして応援しよう!
0
ログインして広告を非表示にする
kinaba @kinaba
にっきかいた。みんな二分探索どう書くの。http://t.co/qg7wvIbu ライブラリ化する際に引数と返値と関数名と引数名をどうするのという話としてもよいです。
まっつん @y_mazun
左辺値って3項演算子で選べたのか。ほえー
jkrod @Isa_rentacs
lbとubどっちが条件満たしてどっちが条件満たさないかは結構書くたびに違っている気がする…
jkrod @Isa_rentacs
間違えやすいのは確かにその通りで、いつも線分図書いて、これが求めたい値、ここまでtrueでここからfalse、だからmedがtrueなら動かすのは…とか考えて書いてる
jkrod @Isa_rentacs
「最大値の最小化」ってよく言われてるけど自分が問題によってはその形にうまく落とせないので、ある区間にただ1つ閾値があって、それを境にtrue/falseが変わる->にぶたん だと思ってます。
しおしおた @shioshiota
にぶたん、閉区間で差が2より小さくなるまでまわしてる。 得られた二つの候補について適切か毎回確認してから、より適切なものを返すようにしてる(無駄)
tanzaku @_tanzaku_
二部探は解の区間だけ意識してwhile(L <= R) { ... } return L - 1; みたいにやってるなー。
はまづ @hama_du
整数二分探索は回数指定でループを回して、さらに念のため収束した値のプラマイ2ぐらいを追加でチェックしてる
k_operafan @k_operafan
整数二分探索は「lはかならず条件を満たし、rはかならず条件を満たさない」という感じに考えているのです
todo @todo314
そうするように、と私はライブラリに明記してます。
2018年こそ夏バテにならない @tomerun
二分探索のことを「二部探索」と書く人が多いのはなぜなのか気になっている
k_operafan @k_operafan
この考え方はコーチから教わったのですが、1の差が出てくるミスが減ったので重宝しているのです
hogeover30 @hogeover30
整数にぶたん昨日のSRMでは while(L<=R) { M=(L+R)/2; if (hoge) L=M+1; else R=M-1; } return L; で通った
しおしおた @shioshiota
@hama_du 念入りですね!! 回数指定は回数の見積りミスが怖いので滅多にしないです。
tanzaku @_tanzaku_
あ、二部になってる…
tanzaku @_tanzaku_
よくよく見ると意味不明な日本語だった。少しは推敲してから書こう。
tanzaku @_tanzaku_
区間を意識ではなく、LとRのどちらが条件を満たしていて、どちらが条件を満たしていないか意識して~
まっつん @y_mazun
2分探索はその場のノリで適当に。苦手意識あるから逆にちゃんと意識するので正答率は高いイメージ
しおしおた @shioshiota
なるほど、勉強になるなぁ。
はまづ @hama_du
@shioshiota 回数はだいたい100か200って書いちゃいますね。整数型の場合はそれで十分ですが、実数でにぶたんするときは回数のミスは怖いですね。
kinaba @kinaba
みんなループにinvariant書かないとobfuscationで失格ということにしよう(過激派)
白茶利休 @shiracha
とりあえずループを見たらinvariantを考える派の私としてはこれはギャグじゃなくて割りと・・・。
白茶利休 @shiracha
loop invariantは普通、真偽の2値しかとらないが(なぜなら述語なので。)、あるループが開始してから、終了するまで、常に同じ値をとる関数を取って、それをloop invariantと看做した上で、ループ初期値に対する同値類を考えたらきっと楽しいんじゃないかなー。など思う
残りを読む(31)
ログインして広告を非表示にする
ログインして広告を非表示にする