この記事で使うアルゴリズム
二分探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc023/tasks/abc023_d
この問題は二分探索を用いて解くことができますが、標準ライブラリbisect
を使うことはできません。なぜならbisect
はリストに対する二分探索であり、この問題ではリスト化できない関数に対する二分探索が必要になるためです。
方針
- 「ある時点での高度」や「速度」に対して貪欲に風船を割っても最適な割り方とはならない。
- しかし、ある得点が与えられた時「その得点以下となるように風船を割ることができるか」を判定することはできる。
- 各風船をいつまでに割れば良いかを考え、全ての風船に対して実行可能なスケジューリングがあるかを確認すれば良い
- 判定を元にして二分探索を行えば良い
ポイント
- 特典の最大値に注意する(
1e+14
)
コード
1 | def is_ok(x): |
二分探索を行う関数meguru_bisect
はこちらの実装学習する天然ニューラルネットを利用させていただきました。記事の中で説明している通り、実装が簡潔でバグが入り難いと思います。
関連記事
- bisectを実装する
bisect
に相当する機能を、自前で実装しています。
記事情報
- 投稿日:2020年4月12日
- 最終更新日:2020年5月8日