ARC054B ムーアの法則

この記事で使うアルゴリズム

二分探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

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

方針

計算を終えるまでの時間は凸関数です。そのため三分探索により近似解を求めることができます。

left, rightに対して三等分する点m1, m2を考えます。計算を終えるまでの時間をcostとして、cost(m1)<cost(m2)である時、解はleftからm2の間に存在することがわかります。これらの値を十分な回数更新すれば近似解を求めることができます。

コード

def cost(x):
    return x + P * pow(2,-(x/1.5))
P = float(input())
left = 0
right = 10**18
for i in range(10**5):
    m1 = (2*left + right) / 3
    m2 = (left + 2*right) / 3
    if cost(m1) < cost(m2):
        right = m2
    else:
        left = m1
print(cost(left))

記事情報

• 投稿日：2020年5月27日
• 最終更新日：2020年5月27日