にぶたん

白茶利休 @shiracha

なんかあんまり正確じゃない。なんだ。まあ、ある初期状態から開始して終了するまでは全て同じloop invariant値で、別のある初期状態から開始して終了するまでも同じloop invariant値だが、必ずしも２つ開始状態でloop invariant値が同値ではないような。

白茶利休 @shiracha

たぶんなんだけど、自明なそういう多値loop invariantとしては終了時の値をloop invariantと看做すようなものがありそう。未来予測になるけど。

白茶利休 @shiracha

つまりそういうある事後状態が成り立つ初期状態の集合をそれぞれとって同値類に割る。

白茶利休 @shiracha

ループコード側がコードの実行によって変化しないならループは同じ状態に対して同じ結果をもたらすのは自明で(自明じゃない？なら適当な意味論を仮定してfixedpoint theoremを証明すりゃわかる。)

白茶利休 @shiracha

以下略

白茶利休 @shiracha

ループには素直な半順序が見えるー。

nanikaka(静寂の使徒) @nanikaka

にぶたんは、LとRのどっちが常に解の条件を満たすかとか、意識したことなかった。適当に解のありそうな区間を絞って、L+1 == Rになったら、LとRどちらが解にふさわしいかを更にチェックしている

はまづ @hama_du

昨日はプラマイ2をチェックしたつもりだができてなかった（本体の書き方が正しかったから良かったけど）

しおしおた @shioshiota

@nanikaka 僕とかなり近いです。

nanikaka(静寂の使徒) @nanikaka

少し、整数のにぶたんの意識が変わりそう

lyoz @lyoz

にぶたんはstd::lower_boundの真似をしてif(ok) hi=mi; else lo=mi+1;って書いてる

J. Kuroda @Isa_rentacs

lb/ubって書いてて「あれ？どっちが大きいんだっけ?」ってなるのもなんとかしたい

しおしおた @shioshiota

半開区間でやったほうが絶対いい気がしてきた・・・。しかし、国内予選前に変更するのも危険なのでしない。

いちょう @ichyo

ICPC国内予選に二分探索が出るフラグ

とーらす🌸📦🌕✨🍀 @torus711

整数二分探索の話題がアツいみたいなので僕も昨日のコード貼ろうと思ったけど、今良く見たら間違ってんじゃん。なんで通ったの。m ( (lb+ub)/2 ) を次の範囲に含めるかどうかについては意識しておかないと危険かも。

nanikaka(静寂の使徒) @nanikaka

@shioshiota 一緒ですね

とーらす🌸📦🌕✨🍀 @torus711

多く目に入った lb/ub で書いたけど、僕は l/r 派です。 QT俺：https://t.co/d4kqItgC

hotpepsi @hotpepsi

Lが満たさないRが満たすで二分探索する場合、0～MAXでやると0が例外になるので場合わけしてる人が何人かいた。kinabaさんのは-1からやってた。これは自分で書くのは怖いなあ

hirosegolf @hirose_golf

自分の二部探索の書き方ってかなり変わってるかもしれない。LとRを使って書いたことがない。

hirosegolf @hirose_golf

@kinaba 自分は整数の二分探索は全部このやり方で書いています。http://t.co/KV1g6rH3 。個人的に間違いが少なくて良い書き方かなと思っていて、他の人の意見に興味あります。

hirosegolf @hirose_golf

３分探索は２分探索と違ってLとRを使わないと書けないから、未だに書き方をちゃんと把握できてない。

yatuhata @yatuhata

@kusano_k こんな二分探索初めて見ました！勉強になりますね！

kusanoさん@がんばらない @kusano_k

@yatuhata 私も初めて見ました。とても書きやすい気がするので、今度使ってみます。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@hirose_golf その書き方だと、範囲に負の数が出てきた時に死にませんか！

hirosegolf @hirose_golf

@chokudai ansの初期値を小さくして開始すれば大丈夫ですが、そもそも範囲に負の数が出てくることがかなり珍しくないですか？