ARC054-B:ムーアの法則

54.ARC054-B:ムーアの法則

問題

https://beta.atcoder.jp/contests/arc054/tasks/arc054_b

今、ある関数の計算に p 年かかる処理がある。x 年後は処理速度が今の 2x/1.5 倍になるとき、計算が終わる最短時間を求めよ。

考え方

全体の仕事量を 1 として今の処理速度は 1/p としてよい。よって x 年後には処理速度が (1/p) * 2x/1.5 になるので計算にかかる時間は

f(x) = x + (1/p) * 2x/1.5
⇔ f(x) = x + p * 2-x/1.5

となる。x に値を代入した時オーバフローに注意する必要がある。
これは下に凸の関数であるから、極小値=最小値を持つ。関数の極値は三分探索で求められるので解くことができるので解が求められた。

       double p;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            p = in.nextDouble();

            double left = 0;
            double right = Double.MAX_VALUE/10;

            for (int i = 0; i < 100000; i++) {
                double c1 = (left * 2 + right) / 3;
                double c2 = (left + right * 2) / 3;

                if (func(c1) < func(c2)) {
                    right = c2;
                } else {
                    left = c1;
                }
            }

            out.println(func(left));

        }

        double func(double x) {
            return x + p * pow(2, -x/1.5);
        }

ポイント

  • 関数の極値は三分探索
  • オーバフローに注意

類題

C - Linear Approximation
本問題では三分探索で直接、値を求められましたが、類題では三分探索で範囲の絞り込みをします。