「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」の第一問目の解答を試みる
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」 (1/3) - ITmedia エンタープライズ
こちらの記事の問題が面白そうだったので第一問目だけ解いてみることにしました。あっているかどうかは知りませんのでご注意を。
該当の問題は以下、
人間が1人、モンスターがM匹、ウサギがB匹います。ここから、モンスターか人間がいなくなるまで無作為に2匹（もしくは1人と1匹）を選び出し、以下の行動を繰り返します。
モンスターとモンスターが選ばれると、両方のモンスターが死にます
モンスターとモンスター以外が選ばれると、モンスター以外が殺されてしまいます
ウサギとウサギが選ばれると、何も起こりません
ウサギと人間が選ばれると、人間の生存確率が最も高くなるように、ウサギを殺す、またはそのままにする、のどちらかの選択をします
モンスターの数Mとウサギの数Bが与えられたときに、最後に人間が生き残る確率を答えなさい。ただし、M、Bともに1000以下の整数とする。
難しそうですが、問題文からはすぐに以下のことがわかります。
- モンスターを消すには、モンスター×モンスターのペアを作る方法しかありません。そのため、もしモンスターの数が奇数でペアが作れなければ、残念なことに人間は生き残ることができません。すなわち、Mが奇数であれば生存確率は常に０％になります。
- モンスターの数が０のとき、問題文より、ウサギ×人間のペアを作ると人間が生き残ることとなります。すなわち、M=0であればBの数に関係なく人間は必ず生き残ることになります。
- このことから、（全てのモンスターが消え、かつ、全てのウサギと人間が生き残る確率）＝＝（人間が生き残る確率）という等式がなりたつはずです。
- ウサギ×ウサギのペアは無視してOK。
以上のことを踏まえ、C#で記述してみると、
amespace TopCoderSolver
{
class Program
{
static void Main(string[] args)
{
for (int i = 1; i != 10; ++i)
{
System.Console.WriteLine("|{0}|{1}|", i, lifeProbability(i, 0));
}
}
public static double lifeProbability(double M, double B)
{
return M == 0 ? 1.0 : M == 1 ? 0 : B == 0 ? (M / (M + 1)) * ((M-1)/M) * lifeProbability(M - 2, 0):
(M/(M + B + 1)) * ((M-1)/(M + B)) * lifeProbability( M - 2, B ) + (M/(M + B + 1)) * (B/ (M + B)) * lifeProbability( M, B-1);
}
}
}と、なります。ムリヤリ2行です。正解しているかは、どんなもんでしょう、ちょっとわかりませんね。
B=0で固定し、Mを１〜９まで動かしたときの結果は以下です。
| M | 生存確率 |
| 1 | 0% |
| 2 | 0.333333333333333% |
| 3 | 0% |
| 4 | 0.2% |
| 5 | 0% |
| 6 | 0.142857142857143% |
| 7 | 0% |
| 8 | 0.111111111111111% |
| 9 | 0% |
[追記]
いきなり間違いを見つけたので、コードを修正。
[追記]
コードをもう一度修正しました。
[追記]
the question doesn't ask to compute how fast you win..(1/M+1)
but you could win where number of bunnies is not zero and where bunny meets monster, bunny meets bunny or bunny meets you(could get killed or not) before all monsters diequestion is biased to computing the probability of winning in least number of meetings
ウサギは関係ないみたい。問題は納得ができていないところ。
生存確率の定義を勘違いしているのが原因かな。
[追記]
問題文をもう一度読んでみる。
モンスターの数Mとウサギの数Bが与えられたときに、最後に人間が生き残る確率を答えなさい。ただし、M、Bともに1000以下の整数とする。
『ただ一人、人間が生き残る』という条件ではなかった。ウサギが全部生き残ってかつ人間が生き残ってもOKだ。ウサギ関係ない。生存確率はモンスターの数にだけ依存する。
こうかな？
public static double lifeProbability(double M, double B)
{
return M == 0 ? 1.0 : (M + 1) % 2 == 0 ? 0 : 1.0 / (M + 1);
}答えは同じ。
[追記]
ブックマークのコメント経由のこれが最短か。
public static double lifeProbability(int M, int B)
{
return (M+1)%2 / (double)(M + 1);
}
