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"; } }