SRM421 Div1 easy

http://www.topcoder.com/stat?c=problem_statement&pm=10104&rd=13512
直線上のx[i]の位置にm[i]の質量がn個並んでいる。万有引力は距離の二乗に反比例する。別のものを置いたときにプラス方向へ引く力とマイナス方向へ引く力が釣り合うポイントがn-1個あることがわかっている。これを求めよ。って問題。

チャットから引用

それは二分探索で普通に解けた。
上限をx[i+1], 下限をx[i]にして
pos = (上限 + 下限) / 2にして
posの位置でどっち方向の力が強いか計算する

上に引っ張ってたら上により過ぎだからもっと下がらないと行けない
上限 = posして繰り返し

上限と下限の差が要求されている制度より狭くなったらbreak

これでおわり

上の説明では言及していないけど、与えられた各質量の間に1個ずつしか釣り合いの点がないことが自明じゃない人もいるかと思うので簡単に説明する。
２つの質量の間の点に注目する。その点の少しプラス側では、プラス側にある質量に近づいたのでプラス方向に引く力が強まり、逆にマイナスに引く力は弱まる。この二つの力が一致する点が釣り合いの点なので、これは２つの質量の間には１個しかない。(下がるばっかりの線と上がるばっかりの線は１カ所でしか交差しないよね）

  vector <double> getPoints(vector <int> x, vector <int> m) {
    vector<double> result;
    size_t N = x.size();
    for(size_t i=0; i<N-1; i++){
      double ub = x[i + 1];
      double lb = x[i];
      while(true){
	double pos = (ub + lb) / 2;
	double lforce = 0.0, uforce = 0.0;
	for(size_t j=0; j<=i; j++){
	  double d = x[j] - pos;
	  lforce += m[j] / d / d;
	}
	for(size_t j=i+1; j<N; j++){
	  double d = x[j] - pos;
	  uforce += m[j] / d / d;
	}
	if(uforce > lforce){
	  ub = pos;
	}else{
	  lb = pos;
	}
	if(ub - lb < 1e-10){
	  result += pos;
	  break;
	};
      }
    }
    return result;
  }

ちなみに、result += posはvectorに対して+=しているわけだけど、これって意外と知らないひとが多いね。boost/assign.hppを使っています。push_backって長くて面倒だもの。