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)$ を与えるxを $x_0 (p)$ とするときに、 $m(p)$ を求めよ。

方針

イメージをつかむために、まずは曲線 $y = f_p(x)$ を図示してみましょう。下の図は、GRAPESを用いて、いくつかの $p$ に対してこの曲線を描いたものです。図からわかるように、関数 $f_p(x)$ は凸関数です*1。よって、この関数の極小値を与えるxを $x_\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)$ になります。

数式処理システムの使用

SymPyやMaximaのような数式処理システムに $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が使用可能です。