アルゴリズム問題: モンスターvsうさぎvs人間

TopCoderOpen 2008 Qual Round 1に出題されたEasy問題

いったいどこがEasyなんだ......

人間が1人、モンスターがM匹、ウサギがB匹います。ここから、モンスターか人間がいなくなるまで無作為に2匹（もしくは1人と1匹）を選び出し、以下の行動を繰り返します。

• モンスターとモンスターが選ばれると、両方のモンスターが死にます
• モンスターとモンスター以外が選ばれると、モンスター以外が殺されてしまいます
• ウサギとウサギが選ばれると、何も起こりません
• ウサギと人間が選ばれると、人間の生存確率が最も高くなるように、ウサギを殺す、またはそのままにする、のどちらかの選択をします

モンスターの数Mとウサギの数Bが与えられたときに、最後に人間が生き残る確率を答えなさい。ただし、M、Bともに1000以下の整数とする。

以下、ヒントと回答です。 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

ヒント

①うさぎは実は考慮しなくていい。

②モンスターが奇数だったら...?

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

私の回答 by Ruby

MONSTER = ARGV[0].to_i
PERSON = 1

class Integer #Override
  # 5C2 = 10 みたいなやつ
  def c(m)
    (1..self).to_a.combination(m).to_a.length
  end
end

def recursive_battle(monster, result=1)
  return 0 if monster.odd? #偶数なら生存確率0%
  return result if monster <= 0 #基底部
  existence_this_time = existence(monster) #今回の生存確率を計算
  existence_total = result * existence_this_time #前回までの生存確率 * 今回の生存確率
  recursive_battle(monster - 2, existence_total) #Monsterの数を2匹減らして、再帰する。
end

def existence(monster)
  1.0 - (monster.to_f / (monster + 1).c(2).to_f )
end

puts recursive_battle(MONSTER, PERSON)

解説そのうち載せます。