ARC054 B ムーアの法則
http://arc054.contest.atcoder.jp/tasks/arc054_b
t + p / pow(2.0, t / 1.5)
これを最小化するだけ。
微分ははるか昔に習った気がしますが無理。
上がる関数と下がる関数がくっついてるんだから下に凸になるだろ(超適当)ということで三分探索で解きましたが、やり方が間違っていました……orz。
これが小数点以下3桁くらいが合わないソースコード。
double p; double check(double t){ double temp = pow(2, t / 1.5); return t + p / temp; } const double INF = 1.0e+12; const double EPS = 1.0e-10; int main(){ cin >> p; double ub = INF, lb = 0.0; rep(i, 1000){ double pp = (ub - lb) / 3.0; double m1 = lb + pp, m2 = m1 + pp; double c1 = check(lb), c2 = check(m1), c3 = check(m2), c4 = check(ub); if(c2 < (c3 + EPS) && c3 < (c4 + EPS)){ ub = m1; }else if((c1 + EPS) > c2 && (c2 + EPS) > c3){ lb = m2; }else{ ub = m2; lb = m1; } } printf("%.10lf\n", check(lb)); return 0; }
いきなり区間を3分の1に絞ろうとすると誤差で死ぬようで。
三分探索を書いたのは初めてなのですが、一般的に以下のような実装になるそうです。
rep(i, 1000){ if(lb > ub) swap(ub, lb); double pp = (ub - lb) / 3.0; double m1 = lb + pp, m2 = m1 + pp; double c1 = check(m1), c2 = check(m2); if(c1 < (c2 + EPS)) ub = m2; else lb = m1; }
区間を3分の2ずつに絞っていきます。
ちゃんと調べてから書くべきでしたね。
解法は3分くらいで思いついたのに解けず、悔しい思いをしました。