yukicoder : No.1501 酔歩

こういう式変形さっとできないなぁ。
https://yukicoder.me/problems/no/1501

問題

N個のマスが並んでおり、各マスiには数値A[i]が書かれている。
今、駒がK番目のマスにある。
この駒は以下のように動く。

• 駒が1番かN番のマスに到達したら終了。
• そうでない場合、現在位置iに対し、A[i-1]/(A[i-1]+A[i+1])の確率で(i-1)番に、残りの確率で(i+1)番に動く。

最終的にコマがN番のマスに到達して終了する確率を求めよ。

解法

f(i) := i番目のマスに駒があるとき、最後N番のマスに到達して終了する確率
とすると、f(K)を求める問題となる。このf(i)は以下のようになる。

• f(1)=0
• f(N)=1
• f(i) = (A[i-1]*f(i-1)+A[i+1]*f(i+1))/(f(i-1)+f(i+1))

この式を頑張って変形すると、

となるので、1/(A[i]*A[i+1])の累積和を取れば容易に計算できる。
この問題は有理数で答えるので、1～10の2値の積の最大公約数である6350400を使い、分子分母ともに6350400/(A[i]*A[i+1])を用いるようにすると小数を使わずに済む。

int N,K;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i+1];
	if(K==N) {
		cout<<1<<"/"<<1<<endl;
	}
	else if(K==1) {
		cout<<0<<endl;
	}
	else {
		ll p=0,q=0;
		for(i=1;i<K;i++) (p+=6350400/(A[i]*A[i+1]));
		for(i=1;i<N;i++) (q+=6350400/(A[i]*A[i+1]));
		ll g=__gcd(p,q);
		cout<<p/g<<"/"<<q/g<<endl;
		
	}
	
}

まとめ

両端の確率がわかっているケース、割かし苦手。