yukicoder : No.23 技の選択

どんどん行きます。
http://yukicoder.me/problems/33

問題

体力の初期値Hを持つ敵の体力を０以下にしたい。
１回通常攻撃をすると、敵の体力はA減少する。
１回必殺技を放つと、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)である。