【新機能】作り忘れたまとめはありませんか?31日前まで期間指定してまとめが作れる高度な検索ができました。有料APIだからツイートの漏れはありません!

にぶたん

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

カテゴリーからまとめを探す

ログインして広告を非表示にする
ログインして広告を非表示にする