黄金分割探索

凸関数の極値を三分探索よりも高速に求める。

下に凸な場合なので、上に凸な場合は渡す関数の返り値に-1をかければよい。

code:cpp

template <typename F>

long long golden_section_search(F f, long long lb, long long ub) {

// t-s, s, t are consecutive fibonacci numbers

long long s = 1, t = 2;

while (t < ub - lb + 2) std::swap(s += t, t);

long long l = lb - 1, m1 = l + t - s, m2 = l + s;

auto v1 = f(m1), v2 = f(m2);

while (m1 != m2) {

std::swap(s, t -= s);

if (ub < m2 || v1 <= v2) {

m2 = m1;

v2 = v1;

m1 = l + t - s;

v1 = f(m1);

} else {

l = m1;

m1 = m2;

v1 = v2;

m2 = l + s;

v2 = m2 <= ub ? f(m2) : v1;

}

}

return m1;

}

使用例

(小さいNのときが上手くいかず全探索している)

code:cpp

bool solve(){

LL(n);

if(n<15){

ll anss{};

rep(i,1,n+1){

cout << "? " << i << endl;

LL(y);

chmax(anss,y);

}

cout << "! "<<anss << endl;

return false;

}

Fill(ans,-1);

unordered_map<ll,ll>mp;

x++;

if(x<=0||x>n)return -abs(x);

cout << "? " << x << endl;

LL(y);

},0,n)+1]);

cout<<flush;

return false;

}