yukicoder No.23 技の選択

問題

体力がHのモンスターを倒したい。
毎ターン、通常攻撃と必殺技攻撃ができ、
・通常攻撃の場合は、必ずAのダメージ
・必殺技攻撃の場合は、1/3で失敗し0ダメージ、2/3でDのダメージ
を与えられる。
モンスターを倒すのに、攻撃の回数の期待値が最小となるようにしたいとき、その期待値を求める。

1<=H,A,D<=10^4

考え方

通常攻撃をx回行った場合、H-A*xのダメージが残っており、これを必殺技攻撃で減らす事を考える。
もしH-A*x<=0ならば通常攻撃だけで倒すので、必殺技は必要なく、攻撃回数の期待値はx。
必殺技ではDだけ減らせるので、必殺技攻撃の回数をy回とすると、「y=(H-A*x)/D+((H-A*x)%D!=0)」回の攻撃が必要となる。

「確率pであたる攻撃を、y回当てるまでにかかる回数」＝Xとおく。ここで求めたいのは、E[X]。
愚直に考えると、ちょうどi回でy回攻撃できるとすると、
E[X]=Σ_{i=y}^∞ i * q_i
E[X]=Σ_{i=y}^∞ i * Comb(i-1, y-1) * pow(1.0/3.0, i-y) * pow(2.0/3.0, y)
と考えられる。しかし、無限回の足し算が必要だったり、iが大きくなると、powの部分がかなり小さくなってしまうため、十分な精度で求める事ができない。

別な見方として、Xを分解し、
E[X]=E[最初に攻撃があたるまでにかかる回数 + 2回目に攻撃があたるまでにかかる回数 + ... + y回目に攻撃があたるまでにかかる回数]
とする。
期待値の線形性より、
E[X]=E[最初に攻撃があたるまでにかかる回数] + E[2回目に攻撃があたるまでにかかる回数] + ... + E[y回目に攻撃があたるまでにかかる回数]
とかける。
それぞれ、攻撃があたるまでにかかる回数の期待値は、それぞれ確率が同じなので、期待値も同じになることから、
E[X]=y * E[最初に攻撃があたるまでにかかる回数]
とできる。

「最初に攻撃があたるまでにかかる回数」というのは、「成功確率がpのベルヌーイ試行を繰り返し、最初に成功する試行回数」なので、幾何分布に従う。なので、E[最初に攻撃があたるまでにかかる回数]=1/pが言える。
http://ja.wikipedia.org/wiki/%E5%B9%BE%E4%BD%95%E5%88%86%E5%B8%83
なので、E[X]=y/p=y*3.0/2.0となり、xについてループをまわして「x+y*3.0/2.0」が最小となるものを探せばよい。
(「回数の期待値」っていうのかな？)