どんどん行きます。
http://yukicoder.me/problems/33
問題
体力の初期値Hを持つ敵の体力を0以下にしたい。
1回通常攻撃をすると、敵の体力はA減少する。
1回必殺技を放つと、2/3の確率で敵の体力はD減少する。
最適手を取った場合、攻撃回数の期待値を答えよ。
解法
「何かをする回数の期待値を求めよ」という典型問題。
残り体力に対する攻撃回数をメモ化再帰かDPで求めていけば良い。
体力Hの敵を倒すのに必要な攻撃回数の期待値をP(H)とする。
- 通常攻撃を行う場合、P(H)=1+P(H-A)である。
- 必殺技の場合、ダメージを与えられる確率は2/3である。逆にダメージを与えるまでの攻撃回数の期待値は逆数の3/2なので、P(H)=1.5+P(H-D)である。
よって、両者の最小値P(H)=min( 1+P(H-A), 1.5+P(H-D) )を求めればよい。
int H,A,D; double memo[10010]; double dp(int C) { if(C<=0) return 0; if(memo[C]>=0) return memo[C]; return memo[C]=min(1+dp(C-A),1.5+dp(C-D)); } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>A>>D; FOR(i,H+1) memo[i]=-1; _P("%.12lf\n",dp(H)); }
まとめ
「行ってもある確率pで何も起きない」ような場合、状態が遷移するまでの試行回数は1/(1-p)である。