はむへい’s diary

ねむいです。

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

問題URL

B - ムーアの法則

解説

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

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;
}