フィボナッチ探索 (src/Optimization/fibonacci_search.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-29 17:46:55+09:00
• Include: #include "src/Optimization/fibonacci_search.hpp"

引数の型が整数な単峰関数を対象.
引数の型が long double の単峰関数を対象にする場合は黄金分割探索 を使う.

関数

名前	概要	計算量
fibonacci_search<sgn>(f,l,r)	$\lbrack l, r\rbrack \cap\mathbb{Z}$ 上で単峰となる関数 $f(x)$ の最適値とその最適解を返す. 返り値は { 最適解 $x^\ast$, 最適値 $f(x^\ast)$ } templateの引数で最大最小を指定.	$n=r-l$ とおき, $f(x)$ の評価が$O(A)$ かかるとしたとき $O(A\log n)$

Verify

• 京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305) Ex - Shojin (Alien DP)
• 技術室奥プログラミングコンテスト#2 F - NPCの家 (NPC’s House) (Alien DP)

参考

https://qiita.com/tanaka-a/items/f380257328da421c6584

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Verified with

• test/aoj/2603.AlienDP.test.cpp
• test/aoj/3044.test.cpp
• test/atcoder/abc204_e.test.cpp
• test/atcoder/abc218_h.test.cpp
• test/atcoder/abc279_d.test.cpp
• test/atcoder/abc305_ex.test.cpp
• test/loj/2419.conj.test.cpp
• test/loj/2419.test.cpp
• test/sample_test/cf_contest802_n.test.cpp
• test/yukicoder/180.test.cpp
• test/yukicoder/2276.test.cpp
• test/yukicoder/2309.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include "src/Internal/function_traits.hpp"
#include "src/Optimization/MinMaxEnum.hpp"
// [l,r]
template <MinMaxEnum obj, class F> std::pair<int64_t, result_type_t<F>> fibonacci_search(const F &f, int64_t l, int64_t r) {
 assert(l <= r);
 int64_t s= 1, t= 2, a= l - 1, x, b, y;
 for (int64_t e= r - l + 2; t < e;) std::swap(s+= t, t);
 b= a + t, x= b - s;
 result_type_t<F> fx= f(x), fy;
 for (bool g; a + b != 2 * x;) {
  if (y= a + b - x; r < y) b= a, a= y;
  else {
   if constexpr (obj == MINIMIZE) g= fx < (fy= f(y));
   else g= fx > (fy= f(y));
   if (g) b= a, a= y;
   else a= x, x= y, fx= fy;
  }
 }
 return {x, fx};
}

#line 2 "src/Optimization/fibonacci_search.hpp"
#include <algorithm>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 6 "src/Optimization/fibonacci_search.hpp"
// [l,r]
template <MinMaxEnum obj, class F> std::pair<int64_t, result_type_t<F>> fibonacci_search(const F &f, int64_t l, int64_t r) {
 assert(l <= r);
 int64_t s= 1, t= 2, a= l - 1, x, b, y;
 for (int64_t e= r - l + 2; t < e;) std::swap(s+= t, t);
 b= a + t, x= b - s;
 result_type_t<F> fx= f(x), fy;
 for (bool g; a + b != 2 * x;) {
  if (y= a + b - x; r < y) b= a, a= y;
  else {
   if constexpr (obj == MINIMIZE) g= fx < (fy= f(y));
   else g= fx > (fy= f(y));
   if (g) b= a, a= y;
   else a= x, x= y, fx= fy;
  }
 }
 return {x, fx};
}

Back to top page