にぶたん

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

@hirose_golf うおお、ほんとだ、普通に大丈夫でした＞＜　かなりレアですねー

kinaba @kinaba

@hirose_golf おお、参考になります。これは下限/上限からの距離を上位ビットから決めていくようなイメージになるんでしょうか。

hirosegolf @hirose_golf

@kinaba 「query(ans)が成立する範囲でansを限界まで小さくしたい。最初から１づつ減らすと効率悪い。最初は大胆に減らし徐々に減らし幅を細かくしよう」的な山登り法に近いイメージで考えてます。bの初期値を２冪に限らない数にしてb=b*2/3で減らしていくのもありです。

nico_shindannin（診断人） @nico_shindannin

@hirose_golf 確かにこの書き方だと、X <= x; と x <= X;で間違うことがなさそうですね。良いです。

komiya @kou_miyam

整数の二分探索は珠玉のプログラミングで不変条件大事というのが書かれていたのでそれにならってやっている。ついでに、lowerとupperの初期値は最強の番兵を置く感じで開区間で考え、それしか残らなかったら全滅した、みたいなのを追加することも多い

yowa @yowa

二分探索は「query(lower)とquery(upper)は真偽が異なる」と言い聞かせながらコーディングしてる。