scipy.optimize.bisectを使った二分法を競プロで使う

はじめに

今日のyukicoder contest 246で関数の二分法に関する問題が出ました。

競プロPython勢ではAtCoderのD - 高橋君ボール1号をニュートン法(scipy.optimize.newton)で解く方法が有名かとは思いますが、二分法でもscipyのモジュールで解けるようなので使ってみました。

問題

yukicoder.me

要約するとが与えられるので、でとなるがどこに収束するのかを求めよという問題です。

二分探索で求めれば良さそうです。scipy.optimize.bisectを使ってみましょう。

コードを書く

が保証されているので、下限は1として、上限は余裕を持ってとしたコードがこちらです。

from scipy.optimize import bisect
import numpy as np
def f(x):
    return x ** 2 - q * x * np.log2(x) - p
p, q = map(int, input().split())
print(bisect(f, 1, 10 ** 15))

結果

input >8 1
output>4.000000000001498

input >7654321 1234567
output>30706182.56174902

たった6行のコードですが解けてしまいました。

おわりに

scipy最高！！！！

ついでに上記の高橋君ボール1号もこの二分法で解けるので解いてみてください。