AOJ2327: Sky Jump

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2327

すげえ〜〜〜〜〜

x座標がXに到達した時のYの最大値と最小値を求めてしまえば、そこの間の値はtを連続的に動かすことにより取ることができるのでYes or Noの判定が出来ます。

最小値はロケットのうちどれか1つだけ使えば達成できます。

最大値を考えます。
max f(t_1,....,t_n) = (Σw_i-1/2 g t_i^2)
where
h(t_1,...,t_n)=0, t_1>=0, t_2>=0, ... ,t_n>=0
です。

fにマイナスを掛けて最小値問題にした後、KKT条件は以下のようになります。

∇(-f)+\mu_1 ∇(-t1)+...+\mu_n ∇(-tn)+\lambda ∇(h)=0
\mu_i t_i = 0
\mu_i >= 0 t_i >= 0
h=0

∇をt_iごとに展開すると、
-w_i+g t_i - \mu_i + \lambda v_i = 0
となります。

t_i,\mu_iを削除することを目標にすると、以下のように変形できます。

Σ(v_i^2/g \mu_i - v_i^2/g \lambda) = X - Σv_i w_i / g
\mu_i = max(v_i \lambda - w_i, 0)
t_i = max((w_i - v_i \lambda)/g,0)

これで\lambdaで条件を書き表すことが出来ました。
u(\lambda)=Σ(v_i^2/g \mu_i - v_i^2/g \lambda)とすると、最初の式はu(\lambda) = X - Σv_i w_i / g となります。
さらにu(\lambda)は単調減少であり、\lambda-> -∞ のときu(\lambda) -> -∞, \lambda -> +∞のときu(\lambda) = -Σv_i w_i / g となるので、条件を満たすような\lambdaはただ1つだけ存在します。
単調性より\lambdaは二分探索で求めることができます。boundですが[-20000, 1000]とすれば十分です。
\lambdaが求まれば\t_i,さらにはfもわかるので最大値が求められます。

int N;
double X, Y;
double V[1010], W[1010];

double f(double lamb) {
	double res = 0;
	rep(i, 0, N) {
		res += max(V[i] * lamb - W[i], 0.0) * V[i] / 9.8 - V[i] * V[i] / 9.8 * lamb;
	}
	return res;
}

void solve() {
	while(true) {
		cin >> N;
		if(N == 0) break;
		rep(i, 0, N) cin >> V[i] >> W[i];
		cin >> X >> Y;
		double sum = X;
		rep(i, 0, N) sum -= V[i] * W[i] / 9.8;
		double ok = -20000, ng = 1000;
		rep(_, 0, 60) {
			double m = (ok + ng) / 2.0;
			if(f(m) >= sum) ok = m;
			else ng = m;
		}
		double mf = 0.0;
		rep(i, 0, N) {
			double t = max((W[i] - V[i] * ok) / 9.8, 0.0);
			mf += W[i] * t - 9.8 * 0.5 * t * t;
		}
		// debug(mf, ok);
		bool ans = true;
		if(mf + eps < Y) ans = false;
		double found = false;
		rep(i, 0, N) {
			double t = X / V[i];
			if(W[i] * t - 9.8 * 0.5 * t * t <= Y) found = true;
		}
		if(!found) ans = false;
		if(ans) cout << "Yes\n";
		else cout << "No\n";
	}
}