Togetter/min.tを安心してお使い頂くためのガイドラインを公開しました。
編集可能

にぶたん

まとめました。
0
kinaba @kinaba

にっきかいた。みんな二分探索どう書くの。http://t.co/qg7wvIbu ライブラリ化する際に引数と返値と関数名と引数名をどうするのという話としてもよいです。

2012-07-03 23:16:51
まっつん @y_mazun

左辺値って3項演算子で選べたのか。ほえー

2012-07-03 23:21:58
J. Kuroda @Isa_rentacs

lbとubどっちが条件満たしてどっちが条件満たさないかは結構書くたびに違っている気がする…

2012-07-03 23:22:33
J. Kuroda @Isa_rentacs

間違えやすいのは確かにその通りで、いつも線分図書いて、これが求めたい値、ここまでtrueでここからfalse、だからmedがtrueなら動かすのは…とか考えて書いてる

2012-07-03 23:24:13
J. Kuroda @Isa_rentacs

「最大値の最小化」ってよく言われてるけど自分が問題によってはその形にうまく落とせないので、ある区間にただ1つ閾値があって、それを境にtrue/falseが変わる->にぶたん だと思ってます。

2012-07-03 23:26:21
しおしおた @shioshiota

にぶたん、閉区間で差が2より小さくなるまでまわしてる。 得られた二つの候補について適切か毎回確認してから、より適切なものを返すようにしてる(無駄)

2012-07-03 23:25:28
tanzaku @_tanzaku_

二部探は解の区間だけ意識してwhile(L <= R) { ... } return L - 1; みたいにやってるなー。

2012-07-03 23:26:57
はまづ @hama_du

整数二分探索は回数指定でループを回して、さらに念のため収束した値のプラマイ2ぐらいを追加でチェックしてる

2012-07-03 23:27:39
k_operafan @k_operafan

整数二分探索は「lはかならず条件を満たし、rはかならず条件を満たさない」という感じに考えているのです

2012-07-03 23:27:50
todo @todo314

そうするように、と私はライブラリに明記してます。

2012-07-04 01:57:01
tomerun @tomerun

二分探索のことを「二部探索」と書く人が多いのはなぜなのか気になっている

2012-07-03 23:27:53
tomerun @tomerun

二部グラフというのもあるからか

2012-07-03 23:28:29
k_operafan @k_operafan

この考え方はコーチから教わったのですが、1の差が出てくるミスが減ったので重宝しているのです

2012-07-03 23:28:52
hogeover40 @hogeover30

整数にぶたん昨日のSRMでは while(L<=R) { M=(L+R)/2; if (hoge) L=M+1; else R=M-1; } return L; で通った

2012-07-03 23:29:03
しおしおた @shioshiota

@hama_du 念入りですね!! 回数指定は回数の見積りミスが怖いので滅多にしないです。

2012-07-03 23:29:14
tanzaku @_tanzaku_

あ、二部になってる…

2012-07-03 23:30:22
tanzaku @_tanzaku_

よくよく見ると意味不明な日本語だった。少しは推敲してから書こう。

2012-07-03 23:36:07
tanzaku @_tanzaku_

区間を意識ではなく、LとRのどちらが条件を満たしていて、どちらが条件を満たしていないか意識して~

2012-07-03 23:37:46
まっつん @y_mazun

2分探索はその場のノリで適当に。苦手意識あるから逆にちゃんと意識するので正答率は高いイメージ

2012-07-03 23:30:49
しおしおた @shioshiota

なるほど、勉強になるなぁ。

2012-07-03 23:30:50
はまづ @hama_du

@shioshiota 回数はだいたい100か200って書いちゃいますね。整数型の場合はそれで十分ですが、実数でにぶたんするときは回数のミスは怖いですね。

2012-07-03 23:31:12
kinaba @kinaba

みんなループにinvariant書かないとobfuscationで失格ということにしよう(過激派)

2012-07-03 23:32:06
白茶利休 @shiracha

とりあえずループを見たらinvariantを考える派の私としてはこれはギャグじゃなくて割りと・・・。

2012-07-03 23:33:23
白茶利休 @shiracha

loop invariantは普通、真偽の2値しかとらないが(なぜなら述語なので。)、あるループが開始してから、終了するまで、常に同じ値をとる関数を取って、それをloop invariantと看做した上で、ループ初期値に対する同値類を考えたらきっと楽しいんじゃないかなー。など思う

2012-07-03 23:36:55
残りを読む(31)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?