TechFUL: Extreme Happy!

TechFUL TechFUL: 中級 二分探索 二分法

問題概要

関数 f が以下のように定義される．

f(x) = a \cdot x^{2 + \log (x)} + b \cdot x + c

f(x) が最小となる x の値を小数点第 5 位を四捨五入して出力せよ．

但し、最小値となる x はただ一つであり、0 より大きく 100 未満の値をとることが保証されている．

制約

考えたこと

f(x) = a \cdot x^{2 + \log (x)} + b \cdot x + c を微分すると f'(x) = 2a \cdot x^{1 + \log (x)} \cdot (1 + \log (x)) + b となる．

f(x) が最小となる x の値を x^{*} とする．

条件から恐らく f(x) は下に凸で、 f'(x^{*}) = 0 が成り立つと考えられる．

x^{*} の値は二分法で求めることができる．

二分法の解説：二分法とは？   アルゴリズム・収束・例題 - 理数アラカルト -

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

double round_n(double data, long long n) {
    double ret = data * pow(10.0, n);
    ret = (double) (long long) (ret + 0.5);
    return ret * pow(10.0, -n);
}

const double EPS = 1e-10;
double a, b, c;

double ff(double x) {
    return 2 * a * pow(x, 1 + log(x)) * (1 + log(x)) + b;
}

int main() {
    cout << fixed << setprecision(4);

    cin >> a >> b >> c;
    double lb = 0.0, ub = 100.0;
    for (int i = 0; i < 100; ++i) {
        double m = (lb + ub) / 2.0;
        if (ff(m) < -EPS) lb = m;
        else ub = m; 
    }
    cout << round_n(lb, 4) << endl;
}

類題