tsutomu3 https://blog.hatena.ne.jp/tsutomu3/ tsutomu3’s diary https://tsutomu7.hateblo.jp/ プログラミングコンテストチャレンジブックの平均最大化問題は、整数分数計画問題だ。本では2分探索で解いている。 この場合、n桁の精度が必要なら、O(n)の反復回数になる。 2分探索ではなく、解に近い3点から2次近似して次の点を求めるようにすると、はるかに速く収束する。実際、初期点以外では、3回の反復で誤差0となった。 （2分探索では1e-10以下にするのに31回かかる） 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftsutomu7.hateblo.jp%2Fentry%2F2013%2F11%2F01%2F000000" title="2013-11-01 - tsutomu3’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-11-01 00:00:00 rich https://tsutomu7.hateblo.jp/entry/2013/11/01/000000 1.0 100%