POJ 2613 Choose and divide

問題

二項係数同士の除算C(p,q)/C(r,s)を行い、小数点第五位までを出力せよ。p,q,r,sは10000未満で、答えは常に1e7を超えないとしてよい。

やりかた

素直にやると精度が落ちて誤差死する。なので優先度付キューを2つ用意して式の分母と分子の数字をそれぞれ入れていき、入れ終わったらそれぞれ大きい方から取り出して割るという風にして精度が落ちるのを防いだ。

以下ソース。

int main(int argc, char **argv){
  double p, q, r, s;
  while(scanf("%lf %lf %lf %lf", &p, &q, &r, &s) != EOF){
    priority_queue<int> nume, deno;
    for(int i = p; i >= 1; i--) nume.push(i);
    for(int i = s; i >= 1; i--) nume.push(i);
    for(int i = r - s; i >= 1; i--) nume.push(i);

    for(int i = q; i >= 1; i--) deno.push(i);
    for(int i = p - q; i >= 1; i--) deno.push(i);
    for(int i = r; i >= 1; i--) deno.push(i);

    double ans = (double)1.0;
    while(!nume.empty()){
      ans *= (double)nume.top();
      ans /= (double)deno.top();
      nume.pop(); deno.pop();
    }
    printf("%.5lf\n", ans);
  }
  return 0;
}