yukicoder : No.2222 Respawn

なるほど…。
https://yukicoder.me/problems/no/2222

問題

Nマスからなる双六を考える。
プレイヤーは1番のマスからN番のマスに移動したい。
この時、以下の操作のいずれかをそれぞれ1/3の確率で取る。

• 1つ進んだ番号のマスに進む
• 2つ進んだ番号のマスに進む
• 現在位置をセーブする

一部のマスは侵入不可であり、もし進んだ先のマスが侵入不可の場合、直前のセーブ位置に戻される。
N番のマスに至る、操作回数の期待値を求めよ。

解法

E(i,j) := セーブ位置がj番のマス、現在位置がi番のマスの場合の、ゴールまでの操作回数の期待値
とする。愚直に計算するとO(N^2)かかる。

セーブ位置からゴールまでの操作回数の期待値をXとすると、E(i,j)はXの一次式で書ける。
というか、i≠jの場合、Xの一次式という点でjに寄らずE(i,j)は同じ式になる。
よってg(i)をE(i,j)とすると、g(i)とE(i,i)を、iの大きい順に埋めて行けばよい。

int N;
string S;
double dp[202020];
double E[202020],GA[202020],GB[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	S+="#";
	GA[N]=1;
	
	for(i=N-2;i>=0;i--) {
		if(S[i]=='#') {
			GA[i]=1;
		}
		else {
			double a=1-(GA[i+1]+GA[i+2]+1)/3.0;
			double b=(GB[i+1]+GB[i+2])/3.0+1;
			E[i]=b/a;
			GA[i]=(GA[i+1]+GA[i+2])/3;
			GB[i]=(GB[i+1]+GB[i+2]+E[i])/3+1;
		}
	}
	_P("%.12lf\n",E[0]);
	
}

まとめ

期待値を一次式で書いてしまうという発想がなかった。