ARC 054 B

今回はこの問題。

arc054.contest.atcoder.jp

現在のコンピュータで解くとP年かかる問題があります。ムーアの法則により、いまからx年後のコンピュータの能力は2^(x/1.5)になり、解く時間もP/(2^(x/1.5))になります。計算時間は(今から計算を始めるまでの時間)+(計算にかかった時間)になります。最短計算時間を求めなさい、という問題です。

数学の問題です。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    double f(double x, double p)
    {
        return x + p / pow(2, x / 1.5);
    }
     
    double dfdk(double k, double p)
    {
        return 1 - (2 * log(2) * p) / (3 * pow(2, 2 * k / 3));
    }
     
    double mink(double p)
    {
        double left = 0.0, right = 1000.0;
        for(int i = 0; i < 10000; i++){
            double mid = (left + right) / 2;
            if(dfdk(mid, p) > 0) right = mid;
            else left = mid;
        }
        return left;
    }
     
    int main()
    {
        double p;
        cin >> p;
        printf("%.10f\n", f(mink(p), p));
        return 0;
    }

k年後に計算を開始するとすると、計算時間はk + P(2^(k/1.5))になります。これをkについて微分して0になるところを2分探索で求めます(微分した結果は単調増加になるので正しく求められます)。最後に計算時間を求めればよいです。