二分探索

関連問題

• 食塩水 (ABC034)
• Enclose All (ABC151)
  座標問題における二分探索の基本、及び浮動小数点演算時の注意点を理解するのに良い問題です。
• Yakiniku Optimization Problem (ABC157)
  Enclose Allを1段階難しくした問題です。

三分探索

関数の極値を探索するアルゴリズム。
極値が1つしかない関数に適用した場合、最大値または最小値が求まる。(e.g. 二次関数)

微分してf'(x)=0となるxを二分探索しても答えは求まる。
しかし、三分探索を用いた方が微分の手間が省け、計算ミスやエンバグの可能性を減らすことができる。

(参考) 三分探索 – 忘れても大丈夫

例題

ムーアの法則

#include <bits/stdc++.h>
using namespace std;

using ld = long double;

ld f(ld p, ld x) {
  return x + p / pow((ld)2, x / 1.5);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ld p;
  cin >> p;

  ld l = 0, r = 1e18;
  while (r - l > 1e-12) {
    ld x1 = (l * 2 + r) / 3;
    ld x2 = (l + r * 2) / 3;
    if (f(p, x1) < f(p, x2)) {
      r = x2;
    } else {
      l = x1;
    }
  }

  cout << f(p, (l + r) / 2) << endl;
  return 0;
}