kmjp's blog

競技プログラミング参加記です

Codeforces #284 Div1 B. Name That Tune

Codeforces

計算時間の見積もりが厄介。
http://codeforces.com/contest/498/problem/B

問題

N個の曲がある。
各曲は1秒毎に確率P[i]で曲名を認識できる。また、T[i]秒経過した場合も認識できる。
曲名を認識したら、次の曲の認識に取り掛かる。

T秒で認識できる曲数の期待値を答えよ。

解法

i番目の曲を認識するのにx秒かかる確率Q(i,x)は以下の通り。
\displaystyle Q(i,x) =\begin{cases} P_i \times (1-P_i)^{x-1} & (x \lt T_i) \\ (1-P_i)^{x-1} & (x = T_i)\\ 0 & (x \gt T_i) \end{cases}

i番目の曲をy秒ちょうどで認識し終わる確率R(i,y)は以下の通り。
R(i,y) = \sum_{1\le t \le T_i} R(i-1,y-t)\times Q(i,t)

このR(i,y)を順に求めていって認識曲数の期待値を求めればよい。
ただし上記sumをまじめに計算してしまうと、全体でO(N*T^2)程度かかりTLEする。
そこで上記sumの計算をさぼる方法を考える。

xがT[i]-1以下ならQ(i,x)=(1-P)Q(i,x-1)であることを利用し、以下のように変形できる。
R(i,y) = \sum_{1\le t \le T_i} R(i-1,y-t)\times Q(i,t) = \\ P_i \times R(i-1,y-1) + (1-P_i)^{T_i-1} R(i-1,y-T_i) + \\ (1-P_i)\times(R(i,y-1) - P_i \times (1-P_i)^{T_i-2} \times R(i-1,y-T_i) - (1-P_i)^{T_i-1} \times R(i-1,y-T_i-1)

あとはO(N*T)のDPを回すだけ。
小数計算が多い上、N,Tが5000以下と割と大きいので、乗算除算をしすぎるとTLEする。
以下のコードは10^-15以下の確率は無視して計算速度を向上している。

int N,T;
double P;
int TT;
double P2[2][6001];
double ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	
	P2[0][0]=1;
	double ret=0;
	FOR(i,N) {
		int cur=i%2,tar=cur^1;
		
		cin>>P>>TT;
		if(P==100) TT=1;
		if(TT==1) P=100;
		P/=100;
		
		double pt1=pow(1-P,TT-2)*P;
		double pt0=pow(1-P,TT-1);
		if(pt1<1e-13) pt1=0;
		if(pt0<1e-13) pt0=0;
		
		ZERO(P2[tar]);
		
		double tt=0,left=1;
		for(j=i+1;j<=T;j++) {
			
			if(TT==1) {
				tt=P2[cur][j-1];
			}
			else {
				if(j>=(TT+1) && pt0) tt-=P2[cur][j-(TT+1)]*pt0;
				if(j>=(TT) && pt1) tt-=P2[cur][j-TT]*pt1;
				tt*=1-P;
				if(j>=TT && pt0) tt+=P2[cur][j-TT]*pt0;
				tt+=P2[cur][j-1]*P;
			}
			ret += tt;
			left-=tt;
			if(tt>1e-15)  P2[tar][j]=tt;
		}
	}
	
	_P("%.12lf\n",ret);
}

まとめ

本番中に式変形でO(NT)にできたが、TLEしてしまった。
これ２秒でもいい問題だと思うんだけどな。