はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

AtCoder Regular Contest 054 B. ムーアの法則:複数の解法

5月21日21時より、AtCoderにて定期コンテストであるAtCoder Regular Contest 054 (ARC 054) が開かれました。本記事では、このコンテストで出された問題の一つであるB: ムーアの法則 - AtCoder Regular Contest 054 | AtCoderについて、その解き方と解答例を、学習の記録を兼ねて示します。

問題の趣旨

正の値pに対し、関数f_p(x) = x + p \cdot 2 ^ {-2x/3} (x \ge 0)を考える。この関数の最小値m(p)を与えるxx_0 (p)とするときに、m(p)を求めよ。

方針

イメージをつかむために、まずは曲線y = f_p(x)を図示してみましょう。下の図は、GRAPESを用いて、いくつかのpに対してこの曲線を描いたものです。図からわかるように、関数f_p(x)は凸関数です*1。よって、この関数の極小値を与えるxx_\mathrm{lm}(p)とすると、x_\mathrm{lm}(p)\ge 0ならばx_0(p) = x_\mathrm{lm}であり、さもなければx_0(p) = 0となります。そこで、以下に示す方法*2のいずれかによりx_\mathrm{lm}(p)を求めれば、そこから容易にm(p)を得られるでしょう。
f:id:hamukichi_nbr:20160522182350p:plain

三分探索あるいは黄金分割探索

上述のようにf_p(x)は凸関数なので、三分探索あるいは黄金分割探索を用いてx_\mathrm{lm}(p)を求めることができます。考慮するxの上限は、上図を参考に決めればよいでしょう。

Brent法

ややオーバースペックに感じられますが、Brent法(参考:wikipedia:ブレント法)を用いてx_\mathrm{lm}(p)を求めることもできます。ただ、実装がやや複雑なので、これを使用する場合には以下のように外部ライブラリによった方がよさそうです。

数値微分と二分探索の組み合わせ

3点近似や5点近似のような数値微分の手法により一階微分f'_p(x)を求め*3、その零点を二分探索(二分法)により求めると、それがx_\mathrm{lm}(p)になります。

数式処理システムの使用

SymPyMaximaのような数式処理システムにf'_p(x) = 0を解かせることで、具体的に\displaystyle x_\mathrm{lm}(p) = \frac{3}{2\ln 2} \ln \left( \frac{2}{3} p\ln 2 \right)という式を得ることもできます。どちらかというとこれはad hocな方法と言えそうです。

実装

上記の各方法*4を用いたPython 3あるいはC++によるコードを以下に示します。

三分探索

黄金分割探索

Brent法

以下のコードは、BoostのMath Toolkitを用いたものです*5。関数f_p(x)を表す関数オブジェクトを、brent_find_minimaに渡しています。

数値微分(5点近似)と二分探索の組み合わせ


感想

コンテスト開催中には、A問題に時間を取られ慌てていたこともあり、ろくに考察せずSciPyを使ってBrent法で「殴ろう」として失敗しました。ピンチ(?)のときこそ、落ち着いて手を動かしてみることの重要性を感じました。

*1:関数f_p(x)の2階微分を求め、それが正であることからf_p(x)が凸関数であることを示すこともできます。

*2:コンテスト中に思いついたのはBrent法による解法でした。

*3:本問のf_p(x)はさほど複雑ではないので、数値微分によらず手計算で解析的にf'_p(x)を求めることも可能ではあります。

*4:数式処理システムによるものは省略します。

*5:最近のARCやAtCoder Beginner Contest (ABC) では、Boostが使用可能です。