AtCoder Regular Contest 054 B - ムーアの法則
問題URL
解説
まず、計算を終了するまでにかかる時間を、計算を開始するまで待つに時間の関数
として定義することを考えてみます。
計算を終了するまでにかかる時間は、
と2つの時間の和で表せます。
と問題文中に登場する
を用いて、この時間を表してみます。
まず、左側の項の「計算を開始するまでに待つ時間」は先程の定義よりです。
次に、「タカハシマン関数を計算するのにかかる時間」ですが、少しも待たないときの「タカハシマン関数を計算するのにかかる時間」がで、そこから計算する速さが
倍になっていきます。
つまり、年後の「タカハシマン関数を計算するのにかかる時間」は
と表すことができます。
よって、は、
のように定義できます。
この関数は下に凸なので、一番小さな値を三分探索することにより、答えを得ることが出来ます。
ACしたコード
#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; }