TopCoderOpen 2022 Round2B : Medium Delina

大幅にやらかした回。
https://community.topcoder.com/stat?c=problem_statement&pm=17126

解法

以下のゲームを考える。
今仲間がG体いるとする。
20面ダイスを(G+1)個転がし、目の最大値がT未満ならゲーム終了。
T以上なら、仲間を1体増やしてゲームを続行する。

T,Gに対し、ゲームが永遠に続く確率を求めよ。

解法

Pを、(T-1)/20、すなわちダイスを1個転がしてT以下の値が出る確率とする。

f(G) := 今G体仲間がいるとき、その後ゲームが永遠に続く確率
とする。

• f(G) = (1-P^(G+1))*f(G+1)
• f(inf) = 1

とすると、f(G)=(1-P^(G+1))*(1-P^(G+2))*(1-P^(G+3))....となる。
適当に10^6項ぐらいまで計算すれば十分。

class Delina {
	public:
	double getProbability(int T, int G) {
		
		if(T==1) return 1;
		
		int i,j;
		double f=log((T-1)/20.0);
		double ret=1;
		
		FOR(i,1000000) ret*=(1-exp((G+i+1)*f));
		
		return ret;
	}
}

まとめ

なんか永遠に続くってのが直感と合わなくてしっくりこない。