二分探索・三分探索・適当に分割する

解き方メモ 日記 C++ 信頼性低

三分探索は、ある1つ以下の点で傾きの正負が入れ替わる場合に、その点(最小値/最大値)を求めるアルゴリズム。
また、その分割を黄金比にすると多少効率がよくなるらしい。
たまに想定解でなくてもこれで解ける時があると思う。
二分探索は、ある1つ以下の点の左右で真偽が入れ替わる時に、その点を求めるアルゴリズム。

SRM 323 DIV1 Medium Survived

http://community.topcoder.com/stat?c=problem_statement&pm=6782&rd=10003
以下の式を満たすθを求めたい。
atan2(v cosθ + u, v sinθ) = atan2(x, y)
で、これは等式だが、absを取ることによって最小化になる。
このとき、ラジアンは2πで周期的なことに注意して、適当にやっておく。
これをプロットしてみると、2πで周期的な形で、周期ごとに谷がひとつ以下あるような形に見える。
このままでは、周期を分断した端っこが谷と誤認されてそこへ行ってしまうので、どうするか？
これは、[0,π]と[π,2π]に分けてそれぞれ探索して、そのうち目的関数で小さい値を取るものを採用すれば良い！
…と思っていたが間違いで、明らかに谷が二つある形が。

これは多分、谷が二つになる時は両方0または両方0じゃない、であって、どっちでも良い、とかそういうことだろう。
実際に、下のコードでPractice System Testを通った。
ただし、誤差とか面倒な部分はあるが。
しかし、半分に分けるというのは有りで、たくさん分割すればいろんな形に対応できる。もちろん、そういう特徴がある場合にだが。
また、分割しすぎること自体では、答えが合わないことはないので(誤差とかはどうだろう？)、それっぽいなと思ったらたくさん分割して試したほうがいいだろう。
山/谷が一つじゃないけど、山/谷の大きさはある程度以上大きい、ということはあると思うので。

SRM 325 DIV1 Medium ModularInequality

http://community.topcoder.com/stat?c=problem_statement&pm=6765&rd=10005
この問題は、
Σ |Ai - X| <= P
となるXの範囲を求める問題である。
これに三分探索と二分探索を適用した。
この総和の部分をプロットしてみると、谷が一つだけある形になることがわかる。
ここで求めたいのは、ギリギリP以下である二つ以下の点である。それを以下の方法でやった。
まず、最小値を二分探索を求める。
整数の場合、三分探査をしなくても、f(x-1)>f(x)となるような境界部分を二分探索を用いて最大値・最小値を求めることが出来る。
ここで最小値がPより大きいなら範囲は空である。
次に、その最小値で左右に分割し、それぞれに対して二分探索で、P以下となる最小・最大のXの値を求める。
この[最小,最大]が答えである。
つまり、何個か二分探索で求めたい点があるとき、それがどこにあるかを三分探査などで求めてその区間でやる、ということ。

雑多

  • 三分探査の対象となるものとして、絶対値をとっているものは、もとのものが単調なら谷ができる。偶数乗も同じ
  • 三角関数は、周期が2πであって、その周期ごとに山・谷がひとつある

コード

SRM 323 DIV1 Medium Survived
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<ll,ll> pll; typedef vector<pll> vpll; typedef vector<string> vs;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
#define double long double

const double pi = acos(-1);

struct Survived {
	double find_min(double a, double b) {
	  const double r = 2 / (3 + sqrt(5));
	  double c = a + r * (b - a), d = b - r * (b - a);
	  double fc = find_func(c), fd = find_func(d);
	  rep(ii, 100) {
	    if (fc > fd) { // '<': maximum, '>': minimum
	      a = c; c = d; d = b - r * (b - a);
	      fc = fd; fd = find_func(d);
	    } else {
	      b = d; d = c; c = a + r * (b - a);
	      fd = fc; fc = find_func(c);
	    }
	  }
	  return c;
	}
	double V, U, R;
	double find_func(double r) {
		double y = V*sin(r), x = V*cos(r) + U;
		double t = atan2(x, y);
		return min(min(abs(R-t),abs(R+pi*2-t)),abs(t+pi*2-R));
	}
	double minTime(int x, int y, int V_, int U_) {
		V = V_; U = U_; R = atan2((double)x,(double)y);
		if(x == 0 && y == 0) return 0;
		double r1 = find_min(0, pi), r2 = find_min(pi,2*pi);
		double r = find_func(r1) < find_func(r2) ? r1 : r2;
		cout<<r<<": "<<find_func(r)<<endl;
		if(find_func(r) >= 1e-9) return -1;
		double yy = V*sin(r), xx = V*cos(r) + U;
		return hypot(xx,yy)<1e-7 ? -1 : hypot(x*1., y*1.) / hypot(xx,yy);
	}
};
SRM 325 DIV1 Medium ModularInequality
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<ll,ll> pll; typedef vector<pll> vpll; typedef vector<string> vs;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

struct ModularInequality {
	vi A; int n;
	ll check(ll x) {
		ll r = 0;
		rep(i, n) r += abs((ll)A[i] - x);
		return r;
	}
	int countSolutions(vector <int> A_, int P) {
		A = A_; n = A.size();
		ll l = -100000000000LL, u = 100000000000LL;
		while(u-l>1) {
			ll m = (l+u)/2;
			(check(m-1) - check(m) > 0 ? l : u) = m;
		}
		ll t = l;
		if(check(t) > P) return 0;
		cout << "t: " << t << ": " << check(t)<<endl;
		l = -100000000000LL, u = t;
		while(u-l>1) {
			ll m = (l+u)/2;
			(check(m) > P ? l : u) = m;
		}
		ll uu = u;
		cout << "uu: " << uu << ": " << check(uu)<<endl;
		cout << "uu-1: " << check(uu-1)<<endl;
		l = t, u = 100000000000LL;
		while(u-l>1) {
			ll m = (l+u)/2;
			(check(m) <= P ? l : u) = m;
		}
		ll lu = l;
		cout << "lu: " << lu << ": " << check(lu)<<endl;
		cout << "lu+1: " << check(lu+1)<<endl;
		return lu - uu + 1;
	}
};