yukicoder : No.425 ジャンケンの必勝法

散々考えた結果、シンプルな回答に。
http://yukicoder.me/problems/no/425

問題

２人でジャンケンを行う。あいこの場合、勝負がつくまで繰り返す。

通常、ジャンケンはランダムに手を出すので勝率は1/3である。
ただし、プレイヤーは必勝法を用いることが出来る。
この必勝法を用いると相手が直前あいこだった場合、その手は次に出さないことがわかるので、負けはありえず、1/2で勝ちまたはあいこに持ちこめる。

ただしこの必勝法はむやみに使いたくない。
必勝法は毎回確率pパーセントで利用する。このpは以下のように定まる。

• 初回あいこ後の勝負は、p=p0。
• 以降のあいこ後の勝負は、直前で必勝法を使ったならpをq引き、使ってないならq足す。ただし0パーセント未満になったり、100パーセントを超えることはない。

p0,qに対し、必勝法を使えるプレイヤーが普通のプレイヤーに勝つ確率を求めよ。

解法

勝ったり負けたりすると一見確率の遷移が難しい。
ただ、考えてみるとpの取り得る値は0～100の整数しかない。
よって以下をDPで求めよう。
dp[i][p] := i回あいこになった次の勝負が、pであるような状態の確率
次の勝負は確率pで必勝法を使うので、それに対してDPしていく。

なお、必勝法を使っても使わなくてもあいこになる確率は高々1/2なので、何度も連続あいこになることはほとんどない。
なので恐らくあいこ数十回までDPを行えば、誤差の範囲に収まる。

int P,Q;

double dp[1010][101];

double R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>Q;
	dp[0][P]=R=1/3.0;
	
	FOR(i,1001) {
		FOR(j,101) if(dp[i][j]) {
			R += dp[i][j]*(j/100.0)/2.0;
			R += dp[i][j]*(1-(j/100.0))/3.0;
			dp[i+1][min(j+Q,100)] += dp[i][j]*(1-(j/100.0))/3.0;
			dp[i+1][max(j-Q,0)] += dp[i][j]*(j/100.0)/2.0;
		}
	}
	
	_P("%.12lf\n",R);
	
}

まとめ

最初p0,qを小数で取ったため、状態がこんがらがった。