Code Festival Team Relay 2018 : F - バス旅行

ここら辺でちょっときつくなってくる。
https://beta.atcoder.jp/contests/cf18-relay-open/tasks/relay2018_f

問題

0～N番の(N+1)個のバス停がある。
バス停iから(i+1)に向け、平均してK分に1回バスが出る。
正確には、nK～((n+1)K-1)分目の間の整数分のどこか等確率で1回バスが出る。
またその際かかる時間はT[i]である。

時刻0に0番のバス停から初めて、N番のバス停に到着する最短時刻の期待値を求めよ。

解法

以下の2値を考える。
X(i,j) := i番目のバス停到着時刻をKで割った余りがjになるようなケースにおける、到着時刻の重み付平均
W(i,j) := 同重み

X(0,0)=0,W(0,0)=1から初めて、X,Wを埋め、最終的にX(N,*)をW(N,*)で重み付平均を取った値が解となる。
後は状態遷移を考えよう。

今X(i,j)からの状態遷移を考えると、この状態はある時刻(nK+j)にバス停に着いたところであると考えることができる。
(nは遷移元によって異なるため、平均値はKで割った余りがjであるとは限らないが、平均を取る前の個々の状態ではこれが成り立つ)

このとき、(nK+j)～((n+1)K-1)で次のバスを捕まえられる確率はいずれも1/Kである。
それ以外の場合、nK～(nK+j-1)にバスが出ていってしまう(確率j/K)と、次のバスは(n+1)K～((n+2)K-1)の回を待たないといけない。
これらを愚直に処理すると、O(NK^2)のDPが出来上がる。
これだとTLが厳しいので、累積和を用いるとO(NK)に落とすことができる。

int N,K,T;
double X[101010][301];
double W[101010][301];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	W[0][0]=1;
	cin>>N>>K;
	FOR(i,N) {
		cin>>T;
		double CX=0,CW=0;
		double LX=0,LW=0;
		FOR(j,K) {
			if(W[i][j]) {
				X[i][j]/=W[i][j];
				CX+=X[i][j]*W[i][j]/K;
				CW+=W[i][j]/K;
				if(j) {
					LX+=(X[i][j]+(K-j))*W[i][j]*j/K;
					LW+=W[i][j]*j/K;
				}
			}
			X[i+1][(j+T)%K]+=(CX/CW+T)*CW;
			W[i+1][(j+T)%K]+=CW;
			CX+=CW;
		}
		if(LW) {
			LX/=LW;
			double w=LW/K;
			FOR(x,K) {
				X[i+1][(x+T)%K]+=(LX+x+T)*w;
				W[i+1][(x+T)%K]+=w;
			}
		}
	}
	
	double ret=0;
	FOR(j,K) ret+=X[N][j];
	_P("%.12lf\n",ret);
	
}

まとめ

O(NK^2)ならまだしも、そこから先が面倒だった。