M回握手をして出来る幸福度の最大値を、１回の握手で幸福度がｘ以上上がるような握手の回数がM回出来るｘの最大値を求める問題と考えれば、二分探索でｘを求めて、左手 i を固定したときにｘ以上の握手ができる手の数は、 a を昇順ソートしておけば k = n - …

数列を前から見ていって、二分探索でその数字が今の数字の色の種類のどれに上書きできるかをを探して、上書きできる奴で、一番数が大きいものにその数字を上書きする。 貪欲法の練習問題で箱を入れていくやつと同じ考え方。 D - プレゼント0 なら色の種類を …

文字列をアルファベットのリストに入れていって二分探索したらいいやつ。 s = contest, t = cc みたいなときに 一つ目の c と二つ目の c が同じ答えにならないように 見ている t の位置が更新するたびに ans += 1 してデバッグするのに 15 分ほどで気づけた…

f (t) = a * t + b * sin( c * t * pi ) として、 f (t) - 100 中間値の定理から、f (left) - 100 0 (left f (t) - 100 0 なら、t = (t + left)/2 として探索範囲を狭めていけば答えに効率的にたどり着く。 a,b,c = map(int,input().split()) import math de…

二分探索で最小値を探すやつ。蟻本３－１－３ 二分探索は値の探索をするだけなので、最小回数で動作終わるようにするための必要十分な動作方法を、主に貪欲法で見つけてくる方に難易度が関わってくる。 今回は左端 ( X0 ) から順に arg回で、それより左側の…

二分探索２つめ。 答えを n と仮定したときに n が条件を満たすかどうかは (a, b) = (x, 1)*k + (1, y) * (n - k) とおいたときに、R >= a かつ B >= b を満たす 0以上 n以下の整数 k が存在することと同値である。 （厳密にはさらに n これを正負に注意して…

二分探索の問題。二分探索はここのサイトがとても参考になった。 めぐる式二分探索 コピペで使えるPython実装 - 学習する天然ニューラルネット 答えを arg と仮定した場合にそれが条件をみたすなら、arg+1についてもまた調べる、満たさないなら、arg//2 につ…