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

問題URL

B - ムーアの法則

解説

まず、計算を終了するまでにかかる時間を、計算を開始するまで待つに時間の関数として定義することを考えてみます。
計算を終了するまでにかかる時間は、
と2つの時間の和で表せます。
と問題文中に登場するを用いて、この時間を表してみます。
まず、左側の項の「計算を開始するまでに待つ時間」は先程の定義よりです。
次に、「タカハシマン関数を計算するのにかかる時間」ですが、少しも待たないときの「タカハシマン関数を計算するのにかかる時間」がで、そこから計算する速さが倍になっていきます。
つまり、年後の「タカハシマン関数を計算するのにかかる時間」はと表すことができます。
よって、は、のように定義できます。
この関数は下に凸なので、一番小さな値を三分探索することにより、答えを得ることが出来ます。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    long double P;cin >> P;
    long double x = 0;
    long double y = 1e18;
    auto calc = [&](long double i){
        return i + P / pow(2, i / 1.5);
    };
    while(y - x > 1e-6){
        long double x_ = x + (y - x)/3;
        long double y_ = x + (y - x)/3*2;
        //cout<<x_ <<" "<<y_<<" "<<calc(x_)<<" "<<calc(y_)<<endl;
        if(calc(x_) > calc(y_)){
            x = x_;
        }else{
            y = y_;
        }
    }
    cout<<setprecision(20)<<calc(x)<<endl;
}