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

にぶたん談義

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

ブックマークしたタグ

あなたの好きなタグをブックマークしておこう!話題のまとめを見逃さなくなります。

コメント

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