CODE THANKS FESTIVAL 2014 A : G - 通勤電車と気分

好みの問題設定な問題。
http://code-thanks-festival-2014-a-open.contest.atcoder.jp/tasks/code_thanks_festival_14_quala_g

問題

1～K番の座席が一列に並んだ電車がある。
ここにN人の人が順にやってくる。
各人は以下の２つのいずれかの気分を持つ。

• とにかく座りたい気分：空いてる座席のうち一番小さい番号に座る
• 余裕があれば座りたい気分：両隣に人がいない座席のうち一番小さい番号に座る

いずれも条件を満たす座席がなければ座らない。
各人が前者の気分となる確率p[i]が与えられる。
最後の空き席の数の期待値を答えよ。

解法

余裕があれば座りたい人は、前に座った人と１つ飛びの席に座る。
よって、状態として[途中飛び飛びで空けられた席の数][最後の連続した空き席の数]を持ち、その状態に至る確率をDPしていけば良い。

前者の気分の人は、まず飛び飛びの席を埋めるように座り、後者の気分の人は連続した空き席のところで１個飛び飛びの席を作るように座る。
ややこしいのが両端の扱いで、ここだけは例外的に扱う必要がある。

int N,K;
double dp[2][300][300];
double p;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	if(K==1) dp[0][0][K]=1;
	else dp[0][K][0]=1;
	
	FOR(i,N) {
		int cur=i%2,tar=cur^1;
		cin>>x;
		p=x*0.01;
		ZERO(dp[tar]);
		
		FOR(x,K+1) FOR(y,K+1) {
			
			//ts
			if(y>0) dp[tar][x][y-1] += p*dp[cur][x][y];
			else if(x==2) dp[tar][0][y+1] += p*dp[cur][x][y];
			else if(x>2) dp[tar][x-1][y] += p*dp[cur][x][y];
			else dp[tar][x][y] += p*dp[cur][x][y];
			
			//ys
			if(K==1 && y==1) dp[tar][0][0] += (1-p)*dp[cur][x][y];
			else if(x==K) {
				if(K==1) dp[tar][0][0] += (1-p)*dp[cur][x][y];
				if(K==2) dp[tar][0][1] += (1-p)*dp[cur][x][y];
				else dp[tar][K-1][0] += (1-p)*dp[cur][x][y];
			}
			else if(x==2) dp[tar][0][y+1] += (1-p)*dp[cur][x][y];
			else if(x==3) dp[tar][0][y+2] += (1-p)*dp[cur][x][y];
			else if(x>3) dp[tar][x-2][y+1] += (1-p)*dp[cur][x][y];
			else dp[tar][x][y] += (1-p)*dp[cur][x][y];
		}
	}
	
	double ret=0;
	FOR(x,K+1) FOR(y,K+1) ret += dp[N%2][x][y]*(x+y);
	_P("%.12lf\n",ret);
}

まとめ

本選の部屋わけとか、上海大会の焼肉とか、こういう題材の確率問題は好みだね。