この記事で使うアルゴリズム
二分探索
はじめに
カテゴリー競プロ初中級者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
の間に存在することがわかります。これらの値を十分な回数更新すれば近似解を求めることができます。
コード
1 | def cost(x): |
記事情報
- 投稿日:2020年5月27日
- 最終更新日:2020年5月27日