問題：AtCoder Regular Contest 054: B - ムーアの法則

解説

微分して二分法をして解を求める方法と、三分探索をして解を求める方法があります。

問題を要約すると、x年後のコンピュータを使ってT(334)の計算が終わる時間をf(x)としたときの、 $f(x) = x + \frac{P}{2^{\frac{x}{1.5}}}$ の最小値を求めるというもの。

$0 \leq P \leq 10^{18}$ という制約により、xの値を0から一個ずつ試していくという線形探索は時間がかかりすぎるので駄目っぽいのは気づきます。

$f(x)$ が下に凸関数ということに気づけば、以下の2つの方法のどちらかで問題を解けます。

【方法1】 $f'(x)=0$ のとき（傾き0のとき） $f(x)$ は最小値をとるので、 $f'(x)=0$ となるようなxを二分探索で探せばよい。

【方法2】下に凸関数なので、 $f(x)$ の最小値を三分探索で求める。

$f(x)$ が下に凸関数の条件は、「 $f''(x)>=0$ 」であること。

詳しくは上に凸，下に凸な関数と二階微分 - 高校数学の美しい物語を参照。

f:id:takeg:20200506073440j:plain

$a^{x}$ の微分は30億年ぶりなので、間違ってるかもしれません。

ソースコード

# -*- coding:utf-8 -*-

def solve():
    """f'(x)=0となるようなxを二分法（二分探索）で求める方法"""
    import math

    P = float(input())

    def f(x):
        # f(x)
        return x + P/(2**(x/1.5))

    def fd(x):
        # f'(x)
        return 1 + P*math.log(2**(-1/1.5)) * (2**(-x/1.5))

    left, right = 0, P
    cnt = 500  # 適当
    while cnt > 0:
        cnt -= 1
        mid = (left+right)/2
        if fd(mid) == 0:
            break
        elif fd(mid) < 0:
            left = mid
            continue
        elif fd(mid) > 0:
            right = mid
            continue

    print(f(mid))


def solve2():
    """三分探索で解く方法"""
    P = float(input())

    def f(x):
        # return x + P/(2**(x/1.5))  # OverflowError: (34, 'Result too large')
        return x + P*(2**(-x/1.5))

    # f(x)は下に凸関数なので、三分探索で解く
    left, right = 0, P
    cnt = 500  # 適当
    ans = float("inf")
    while cnt > 0:
        cnt -= 1

        c1, c2 = (2*left+right)/3, (left+2*right)/3
        ret1, ret2 = f(c1), f(c2)

        if ret1 > ret2:
            left = c1
            ans = min(ans, ret2)
            continue
        else:
            right = c2
            ans = min(ans, ret1)
            continue

    print(ans)


if __name__ == "__main__":
    solve2()

注意なのですが、上の、

    def f(x):
        # return x + P/(2**(x/1.5))  # OverflowError: (34, 'Result too large')
        return x + P*(2**(-x/1.5))

の部分の書き方によって、OverflowError: (34, 'Result too large')のエラーが発生してしまいます。

3.0000
Traceback (most recent call last):
  File "c:/Users/XXXX/YYYY/022.py", line 32, in <module>
  File "c:/Users/XXXX/YYYY/022.py", line 17, in solve
    ret1, ret2 = f(c1), f(c2)
  File "c:/Users/XXXX/YYYY/022.py", line 7, in f
    return x + P/(2**(x/1.5))
OverflowError: (34, 'Result too large')

xが10000程度でも、途中計算の(2**(x/1.5))の値が大きすぎてオーバーフローして上記のようなエラーが発生します。

これを(2**(-x/1.5))と書き換えることで、途中計算でオーバーフローの発生を防げます。

計算式をプログラミングするときは、書き方に意識しましょうという問題で学びがありました。