AtCoder Regular Contest 054 B : ムーアの法則

微分して、0になるxを紙で書いて見つけてポイ

$x = \frac{3 \log(p \frac{\log 2}{ 1.5})}{\log 4}$

$f(x) = x + \frac{p}{ 2^{\frac{x}{1.5}} }$

下手に回り道して無限に時間がかかった・・・。
あと、log_2 とlog_10 と log_e がごっちゃになってつらかった。

解説を見たら、3分探索というのでも解けるらしい。
凸関数の極値を求めるのに使うそうだ。

調べたら、黄金分割探索、というのがより効率的で良いとのこと。
ライブラリ化しよう。

その際に参考にしたページ：
qiita.com

ちょっと、

Comparator.comparingDouble(Double::doubleValue).reversed()

このDouble::doubleValueというのが汚い。いい方法ないかな。

やざてんさんよりコメントで、二分探索でも解けるとのこと。

f:id:arukuka:20161022122044p:plain

midが負だったら、left=mid、正だったらright=midとして、
微分した関数f'(x)=0となるxを探索する。

数値解析では二分法と呼ばれているものですね。
ここをニュートン法とかでやってみてもおもしろいかも。

ご指摘ありがとうございます。

そのままだったら三分探索、微分したら二分探索、
式をいじったらO(1)っておもしろい。