yukicoder : No.813 ユキちゃんの冒険

まんまと想定誤解法に行ってしまった。
https://yukicoder.me/problems/no/813

問題

N個の門が一列に並んでいる。
列の端から反対の端に向かって移動することを考える。
門に遭遇すると、

• 確率Pで向きを反転し、門を通過せず戻る
• 確率Qで門を通過する。
• 確率(1-P-Q)で移動を止める。

列の反対側に到達せず、移動を止めることもなく、元の位置に戻ってくる確率はいくらか。

解法

大概のケースでは愚直にシミュレーションすると通ってしまうが、P=Q=0.5では、TLに収まる範囲の反復回数では収まらない。
ある門に突入したとき、確率Xで突破し、Yで戻るものとする。
さて、ここで別の門がその直後に並んでおり、そちらは確率X'で突破し、Y'で戻るものとする。

そうすると、詳細な計算はEditorialに任せるとして、２つの門を連結したときの突破確率は、戻る確率はとなる。
これで２つの門を連結する手段がわかった。
あとは二分累乗法の要領でN個連結すればよい。

int N;
long double P[21],Q[21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q[0]>>P[0];
	
	if(Q[0]==1) return _P("1\n");
	
	long double CP=1,CQ=0;
	FOR(i,20) {
		if(N&(1<<i)) {
			double PP=CP,PQ=CQ;
			CP=PP*P[i]/(1-PQ*Q[i]);
			CQ=PQ+Q[i]*PP*PP/(1-PQ*Q[i]);
		}
		P[i+1]=P[i]*P[i]/(1-Q[i]*Q[i]);
		Q[i+1]=Q[i]+Q[i]*P[i]*P[i]/(1-Q[i]*Q[i]);
	}
	
	_P("%.12lf\n",(double)CQ);
	
}

まとめ

Nがさほど大きくないので、自分含めシミュレーションに走った人多そう。