AtCoder ARC #015 : D - きんいろクッキー

まさかのCookie Clickerネタ。
http://arc015.contest.atcoder.jp/tasks/arc015_4

問題

初期状態ではT秒間の間、毎秒1個ずつ通常クッキーが手に入る。
ここで、毎秒Pの確率で金色クッキーが登場する。
金色クッキーはN通りのいずれかで、それぞれがQ[i]の確率で登場する。
i番目の金色クッキーをとると以後t[i]秒間得られる通常クッキーの倍率がx[i]倍になる。
各金色クッキーの効果は重複して乗算される。

T秒間に得られる通常クッキー数の総量の期待値を答えよ。

解法

最終的な答えは10^100以下と大きいが、必要な精度が低いのでdoubleで計算すればよい。
doubleは10^308位まで行けるのでオーバーフローしない。

あるタイミングで金色クッキーが出現したまたはしない場合、p秒後の倍率M[p]がどうなるかを求める。
1秒後は、M[1] = (1-P) + P*(x[0]*Q[0] + x[1]*Q[1] + ... + x[N-1]*Q[N-1])となる。
金色クッキーの種類をt[i]順に昇順ソートしていくと、iをt[i]＜xを満たす最大のiとしてi番目までの金色クッキーの効果は切れるのでM[x] = (1-P) + P*(Q[0]+...+Q[i]) + P*(x[i+1]*Q[i+1] + ... + x[N-1]*Q[N-1])となる。

1回の金色クッキーの効果がM[x]なので、y秒目に得られる通常クッキーの期待値は。
後はそれをT秒まで総和をとればよいのでが答え。

答えの出力形式が特殊なので注意。

int T,N;
double P;
pair<int,pair<int,double> > E[1000001];
double TM[100001],TMm[100001];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin>>T>>N>>P;
	FOR(i,N) cin>>E[i].second.second>>E[i].second.first>>E[i].first;
	sort(E,E+N);
	
	// TM後の枚数
	TM[1]=1-P;
	FOR(i,N) TM[1]+=P*E[i].second.second*E[i].second.first;
	j=0;
	for(i=2;i<=T;i++) {
		TM[i]=TM[i-1];
		while(j<N && E[j].first < i) {
			TM[i]-=P*E[j].second.second*E[j].second.first;
			TM[i]+=P*E[j].second.second;
			j++;
		}
	}
	
	TMm[0]=TM[0]=1;
	for(i=1;i<=T;i++) TMm[i]=TMm[i-1]*TM[i];
	
	double res=0;
	FOR(i,T) res += TMm[i];
	
	if(res>1e8) {
		int nu=0;
		while(res>1e8) res/=10.0,nu++;
		_P("%d",(int)res);
		FOR(i,nu) _P("0");
		_P("\n");
	}
	else {
		_P("%.8lf\n",res);
	}
}

まとめ

今回初めてのプロコン優勝でした。いい調子。