TopCoder SRM 667 Div1 Medium CatsOnTheCircle

最終的に自力で解いたけど、本番中には１個アイデアが不足してゴールにはたどり着けなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13643

問題

0～(N-1)番の点が円形に時計回り順に並んでいる(当然(N-1)番と0番は隣接している)。
初期状態でプレイヤーは0番の点にいる。

ここで1手ごとに確率pで時計回り、(1-p)で反時計回りに隣接する頂点に移動する。
全部の頂点を１回以上通ったとき、最後に到達した頂点がゴールとなる。
ゴールが頂点Kとなる確率を求めよ。

解法

ゴールが頂点Kとなるには、それ以外の頂点を先に全部到達すればよい。
これは以下の和となる。

• 反時計回りで(K+1)に到達する前に時計回りで(K-1)に到達し、その後時計回りでKに到達することなく反時計まわりで(K+1)に到達する。
• 時計回りで(K-1)に到達する前に半時計回りで(K+1)に到達し、その後半時計回りでKに到達することなく時計まわりで(K-1)に到達する。

現在位置から、時計回りでR個の位置に到達する方が反時計回りでL個の位置に到達するより先であるような確率をf(L,R)とする。
逆に先に反時計回りでL個の位置に到達する確率は(1-f(L,R))となる。
上記「以下の和」をこの関数fを使って書くととなる。
あとはfの値を計算できれば良い。

fは以下のように計算できる。

• R=0ならすでに達成しているのでf(*,0)=1
• L=0ならすでに失敗しているのでf(0,*)=0
• それ以外の場合、f(L,R) = p*f(L+1,R-1) + (1-p)*f(L-1,R+1)

最後の漸化式ではf内の引数の和は等しいので、g(x)=f(L+R-x,x)と1変数の関数gと見なすと、g(0)=1,g(L+R)=0,g(x)=p*g(x+1)+(1-p)*g(x-1)の関係を満たす数列においてf(L,R)=g(R)を求める問題に還元できる。
L+Rは大きいので、この漸化式を愚直にループで求めるのは間に合わない。
g(x)は三項間漸化式なので、特性方程式を考えるとより。
1じゃない方の値をとするとと表現でき、g(0)とg(L+R)の値からが求まり、g(R)も計算可能となる。

k'が大きいと累乗計算時の精度が心配なので、pが1/2を超えるときは全体を反転させておくと良い。
またp=1/2の時はg(x)=(L+R-x)/(L+R)になるので注意。(aの計算過程で0除算が生じる)

class CatsOnTheCircle {
	public:
	long double P;
	
	long double goR(int L,int R) {
		int T=L+R;
		
		if(abs(P-0.5)<1e-10) return L*1.0/T;
		
		long double k = P/(1-P);
		long double a = 1/(1-pow(k,T));
		long double b = 1-a;
		return a*pow(k,R)+b;
		
	}
	
	double getProb(int N, int K, int p) {
		if(p>1000000000-p) {
			p=1000000000-p;
			K=N-K;
		}
		
		P=p/1e9;
		int L=N-K-1,R=K-1;
		return goR(L,R)*(1-goR(N-2,1))+(1-goR(L,R))*goR(1,N-2);
	}
}

まとめ

本番三項間漸化式が出た後、特性方程式で解く方向に向かわず行列累乗を解消する方向に進んでしまったのが失敗。