AtCoder Regular Contest 054 B. ムーアの法則:複数の解法
5月21日21時より、AtCoderにて定期コンテストであるAtCoder Regular Contest 054 (ARC 054) が開かれました。本記事では、このコンテストで出された問題の一つであるB: ムーアの法則 - AtCoder Regular Contest 054 | AtCoderについて、その解き方と解答例を、学習の記録を兼ねて示します。
問題の趣旨
正の値pに対し、関数を考える。この関数の最小値を与えるxをとするときに、を求めよ。
方針
イメージをつかむために、まずは曲線を図示してみましょう。下の図は、GRAPESを用いて、いくつかのに対してこの曲線を描いたものです。図からわかるように、関数は凸関数です*1。よって、この関数の極小値を与えるxをとすると、ならばであり、さもなければとなります。そこで、以下に示す方法*2のいずれかによりを求めれば、そこから容易にを得られるでしょう。
三分探索あるいは黄金分割探索
上述のようには凸関数なので、三分探索あるいは黄金分割探索を用いてを求めることができます。考慮するxの上限は、上図を参考に決めればよいでしょう。
Brent法
ややオーバースペックに感じられますが、Brent法(参考:wikipedia:ブレント法)を用いてを求めることもできます。ただ、実装がやや複雑なので、これを使用する場合には以下のように外部ライブラリによった方がよさそうです。
実装
上記の各方法*4を用いたPython 3あるいはC++によるコードを以下に示します。
三分探索
黄金分割探索
Brent法
以下のコードは、BoostのMath Toolkitを用いたものです*5。関数を表す関数オブジェクトを、brent_find_minima
に渡しています。
数値微分(5点近似)と二分探索の組み合わせ
感想
コンテスト開催中には、A問題に時間を取られ慌てていたこともあり、ろくに考察せずSciPyを使ってBrent法で「殴ろう」として失敗しました。ピンチ(?)のときこそ、落ち着いて手を動かしてみることの重要性を感じました。