TopCoder SRM 420 Div1 Medium

今日は id:suztomo 宅でTopCoder & カレー
R枚の赤いカードとB枚の黒いカードを順番にめくっていって赤が出たら1ドル、黒が出たら-1ドルというゲーム。最良の戦略を取ったときに期待値がいくらでしょうか、という問題。例えば赤が5枚黒が1枚なら全部取れば4ドルは貰えるけど、それは最適な戦略ではない。5枚とって全部赤だったときには最後のカードを引かない方がいいからうんぬん。という問題。

  double getProfit(int R_, int B_) {
    size_t R = R_ + 1;
    size_t B = B_ + 1;
    vector<double> score(R * B);

    for(size_t b=0; b<B; b++){
      score[b] = 0.0;
    }
    for(size_t r=1; r<R; r++){
      score[r * B] = r;
      for(size_t b=1; b<B; b++){
	size_t pos = r * B + b;
	score[pos] = (r + r * score[pos - B] - b + b * score[pos - 1]) / (r + b);
	if(score[pos] < 0) score[pos] = 0; // <- here
      }
    }
    return score[R * B - 1];
  }

hereって書いてある1行を忘れて、それでも4つもテストを通ったのでアルゴリズムが間違っていることに気づかずに「doubleでは精度が足りないのか？！ど、どうすれば？！」と混乱してしまった。

Test Case #0...PASSED
Test Case #1...PASSED
Test Case #2...PASSED
Test Case #3...PASSED
Test Case #4...FAILED
	Expected: "8.32418"
	Received: "8.30769"

慌ててもっと高精度にすることを考えてしまったので泥沼。むー。