TopCoder SRM 743 Div1 Medium ExpectedSum

これは450ptでもいい気がするなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=15233

問題

N要素の非負整数列S[i]が与えられる。
各要素は確率P[i]で正負反転するものとする。

こうして得られた整数列のうち、総和が最大となる連続部分列の総和の期待値を求めよ。

解法

数列が与えられたとき、上記総和が最大となる連続部分列の求め方を考える。
前から順に要素を足していき、途中負になったら0にする、ということを繰り返し、途中得られた最大値を取ればよい。

S[i]の総和は高々5000なので、
f(n,a,b) := 先頭n要素からなる整数列において、途中総和の最大値がaで、現時点での総和がbであるような状態の遷移確率
とするとf(n,a,b)を順次埋めていき、最後にf(N,a,*)*aの総和を取ればよい。

int N;
double from[2501][2501];
double to[2501][2501];

class ExpectedSum {
	public:
	double solve(vector <int> S, vector <int> P) {
		N=S.size();
		ZERO(from);
		from[0][0]=1;
		
		int i,x,y;
		FOR(i,N) {
			ZERO(to);
			for(x=0;x<=i*50;x++) for(y=0;y<=i*50;y++) if(from[x][y]) {
				to[max(x,y+S[i])][y+S[i]] += from[x][y]*(100-P[i])/100.0;
				to[x][max(0,y-S[i])] += from[x][y]*P[i]/100.0;
			}
			swap(from,to);
		}
		
		double ret=0;
		FOR(x,N*50+1) FOR(y,N*50+1) ret+=from[x][y]*x;
		return ret;
		
	}
}

まとめ

前回も今回もDiv2 Hard == Div1 Easyだったし、問題不足なのかなぁ。