AtCoder Regular Contest 054 B - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Regular Contest 054 B ( ABC 054 B ) 。
三分探索で解いた。
今日の一問は、ARC054より、ムーアの法則！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 29, 2019
問題自体は競プロ的なんだけど、ちょっと問題テーマが面白いから個人的に好きな問題。難易度は400点くらいで少し難しいかも？#chokudai今日の一問
B - ムーアの法則 https://t.co/fuchkfm5bP
B - ムーアの法則
コンピュータの計算速度が1.5年で2倍になる。
タカハシマン関数を計算するのに、 現在のコンピュータではP時間かかってしまう。
計算が終わるまでの最短時間を求めよ。
解いた方針
計算時間の関数の最小値を求めればいいなってことはまず分かった。
計算時間関数：f(x) = x + P * 2^(x/1.5)
最初、微分をして傾きを調べながら、二分探索をしようと思ったけど、 実装がなんかおかしくなった（たぶん解けるはず）。
ということで三分探索を使って解いた（こっちのほうがスマートだった）。
三分探索の解説は以下の記事が分かりやすかった。ありがたい。
三分割する区切りの更新をしっかり実装できれば解ける問題だった。
コード
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
// 判定に使う小さい値
const double EPS = 1e-10;
// 時間を求める関数
double f(double x, double p)
{
return x + (p/pow(2.0, x/1.5));
}
int main()
{
// 入力
double p;
cin >> p;
// 答え
double ans = 1e18;
// 三分探索の両端
double left = 0.0;
double right = 1000.0;
while(abs(right-left) > EPS)
{
// 三分探索の区切り、leftを足すのを忘れずに
double x1 = left + (right-left) / 3.0;
double x2 = left + 2.0 * (right-left) / 3.0;
// 区切ったところを値を計算
double tmp1 = f(x1, p);
double tmp2 = f(x2, p);
// 最小値を更新
ans = min(ans, tmp1);
ans = min(ans, tmp2);
// 三分探索の範囲を更新
if(tmp1 <= tmp2) right = x2;
else if(tmp1 > tmp2) left = x1;
}
cout << setprecision(10) << ans << endl;
return 0;
}
おわりに
三分探索を使ったのが生まれて初めてだった。
