さて勝手に始めている競技プログラミングシリーズの出題編第4問
前回の「最短経路探索」は正攻法に+αの効率化が求められたのだが今回の「生き残り確率」はそれだけでは解決するのが難しいだろう
第4問 「生き残り確率」 Lv. ★★★★
————————————————————
人間が1人、モンスターがM匹、ウサギがB匹います。
ここからモンスターか人間がいなくなるまで無作為に2匹（もしくは1人と1匹）を選び出し、以下の行動を繰り返します。
・モンスターとモンスターが選ばれると、両方のモンスターが死にます
・モンスターとモンスター以外が選ばれると、モンスター以外が殺されてしまいます
・ウサギとウサギが選ばれると、何も起こりません
・ウサギと人間が選ばれると、人間の生存確率が最も高くなるようにウサギを殺す、またはそのままにするのどちらかの選択をします
行ごとにモンスターの数Mとウサギの数Bがスペース区切りで与えられたときに、最後に人間が生き残る確率Xを小数点以下4桁まで出力するプログラムを作成してください。
ただしM、Bともに1000以下の整数とします。
・入力
2 2
12 13
・出力
0.3333
0.0769
※ 入力には標準入力、出力には標準出力を用いてください。
————————————————————
このシリーズだが出題編は今回で終わり次回からは解答編へと移る
今回の問題は先述の通り正攻法でプログラムの設計をしてしまうとどうしても計算が収束しないという事態に陥ってしまうことと思う
実はこの問題は私も正解出来なかったのだが後に解答を聞かされた時は正に狐に摘ままれたようであった今一度条件を整理してみよう
