この記事で使うアルゴリズム
二分探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c
https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6
この問題は二分探索で解くことができます。
方針
まず全探索の計算量はO(N^4)
なので、最悪のケースN=1000
では間に合いません。
次に単純な二分探索について考えます。ダーツを3回投げたのち、最後の1回でどこに投げれば良いかを二分探索します。これは計算量がO((N^3)logN)
なので、これでも最悪のケースN=1000
では間に合いません。
より計算量を削減する方法としてダーツを2本ずつにまとめて考えます。二分探索をすると、計算量は、O((N^2)log(N^2))
となります。(log(N^2)=2logN
なので計算量はO((N^2)logN)
とも表せます)
コード
1 | import bisect |
記事情報
- 投稿日:2020年5月25日
- 最終更新日:2020年5月25日