みんなのオブザイヤーオブザイヤーを募集中!今年のツイート今年のうちにまとめよう!

にぶたん談義

@purple_jewel928さん発祥のにぶたん談義をまとめまています。 参考) にぶたん by @kinabaさん: http://togetter.com/li/331840 続きを読む
プログラミング
2268view 0コメント
2
ぱーぽー @purple_jwl
二分探索書くとき、ループ抜ける判定が怪しくて無限ループになることある
ぱーぽー @purple_jwl
前回のこどふぉD解いてて思った(
みさわ @Mi_Sawa
整数二分探索, int res=l; for(int d=(十分でかい2^n); d; d>>=1) if(res+d <= r && ok(res+d)) res += d; すると間違えない. (n回目)
みさわ @Mi_Sawa
int m = (l+r)/2 とかする書き方, ぼくも苦手だ.
ぱーぽー @purple_jwl
二分探索はできればn回ループで終わらせたい(切実
くりんぺっと @climpet
二分探索,境界あたりの条件がよく分からなくなるので苦手
とーらす @torus711
ub, lb をもつ整数二分探索、lb と ub のどっちが condition を満たすのか意識しておくとちょっとよさげ。そうすると素直に ( ok( mid ) ? lb : ub ) = mid と書ける。ループは while ( lb + 1 < ub )
ぱーぽー @purple_jwl
競プロ関連のツイート、自分がすればするほど雑魚なのがバレてしまうのでつらい
音程 @yosupot
[l,r)で考えればあんま間違えないと思うけどなぁ
くりんぺっと @climpet
ついでに,二分探索と二分法はよく混同する
みさわ @Mi_Sawa
(l+r)/2 の切り捨てが死ぬみたいな何かがある事は覚えていて, 何がどうなんだっけと思い出すのが面倒くさい.
わふならず @wfnarazu
いわゆる繰り返し二乗法では2ベキ作ってく方が好きなんだけど,整数の二分探索は (l+r)/2 するなあ,[l,r) もしくは (l,r] が不変条件になってたら間違えようがない.
わふならず @wfnarazu
@Mi_Sawa 一方が負だとアレかもしれない?
くりんぺっと @climpet
あんまりそういう問題見たことはないけど,もし二分探索的なことを負の数を含む区間について行おうとした場合,[l,r) なら問題ないはずだけど, [l,r] だと除算の切り捨て方向の問題で死ぬ場合があるので注意
ぱーぽー @purple_jwl
(さぁ己の持つ二分探索に関する知識を放出するのじゃ...)
hirokazu @hirokazu1020
二分探索と二分法の違いよくわかってないけど区別する意味がわからない
フキーニョ @fuqinho
二分探索で無限ループはあんまり無いけど、ダイクストラとかでキューからpopするの忘れて無限ループは儀式のようにほぼ毎回やる
tagsanov @tagsanov
ALESSで二分探索の説明するときはub,lb,mdとしました
Masaki Hara @qnighy
l,r,mにおける二分探索では、1次元領域を「A:条件を満たしている」「B:不明」「C:条件を満たしていない」の3区間に分割する。そのうえで、Aの最大元がl, Cの最小元がrという不変条件を保ちつつ、(r-l)が指数的に1まで減少するループを書けばよい。
Masaki Hara @qnighy
@qnighy ある値以上の整数全体がwell-orderなのでループの停止性がわかり、特にその速度が指数的であることもわかる。
Masaki Hara @qnighy
@qnighy また、ループの脱出条件はr - l <= 1であるが、実はr - l >= 1という不変条件が保たれるので、脱出時にはr - l == 1が成立し、したがって「B:不明」という区間は脱出時に消滅していることがわかる。
くりんぺっと @climpet
std::binary_searchさんはどうしてboolしか返さないんだ…
残りを読む(190)
ログインして広告を非表示にする
ログインして広告を非表示にする