TopCoder SRM 824 : Div1 Medium SeeAllDifferences

遠回りしてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17403

問題

1～Dが書かれたD面のダイスロールを考える。
今まで出されたダイスの目の一覧が与えられる。
連続した2回のロールにおける差の絶対値は、0～(D-1)のD通りが考えられる。
この全通りが最低1回以上現れるようにしたい。

今後ダイスを振ったとき、条件を満たすまでに必要なダイスロール回数の期待値を求めよ。

解法

f(mask, d) := これまで登場した差の絶対値のバリエーションをbitmaskで表現したものがmask、最後の目がdであるとき、条件を満たすまでに必要なダイスロール回数の期待値

とする。maskが大きい順に、f(mask,*)を埋めて行こう。
ダイスロールを振っても、maskが更新されないパターンがある。
そこで、maskが一致するf(mask,*)についてD変数の連立方程式を解くことで埋めることができる。

double dp[1<<16][16];

const int MAT=16;
double ma[MAT][MAT],V[MAT],R[MAT];

int Gauss(int n,double mat_[MAT][MAT],double v_[MAT],double r[MAT]) {
	int i,j,k;
	double mat[MAT][MAT],v[MAT];
	memmove(mat,mat_,sizeof(mat));
	memmove(v,v_,sizeof(v));
	
	FOR(i,n) {
		if(mat[i][i]==0) {
			for(j=i+1;j<n;j++) if(mat[j][i]) break;
			if(j>=n) return i;
			FOR(k,n) swap(mat[i][k],mat[j][k]);
			swap(v[i],v[j]);
		}
		v[i]/=mat[i][i];
		for(k=n-1;k>=i;k--) mat[i][k]/=mat[i][i];
		for(j=i+1;j<n;j++) {
			v[j]-=v[i]*mat[j][i];
			for(k=n-1;k>=i;k--) mat[j][k]-=mat[i][k]*mat[j][i];
		}
	}
	
	for(i=n-1;i>=0;i--) {
		for(j=n-1;j>i;j--) v[i]-=mat[i][j]*v[j],mat[i][j]=0;
		r[i]=v[i];
	}
	return n;
}

class SeeAllDifferences {
	public:
	double solve(int D, vector <int> rolled) {
		int i,j,x;
		int D2=(D+1)/2;
		ZERO(dp);
		int mask;
		for(mask=(1<<D)-2;mask>0;mask--) {
			ZERO(ma);
			ZERO(V);
			FOR(i,D) {
				V[i]=1;
				ma[i][i]=1;
				FOR(j,D) {
					x=abs(i-j);
					if((mask&(1<<x))==0) {
						V[i]+=dp[mask|(1<<x)][j]/D;
					}
					else {
						ma[i][j]-=1.0/D;
					}
				}
			}
			Gauss(D,ma,V,R);
			FOR(i,D) {
				dp[mask][i]=R[i];
			}
			
		}
		
		
		FOR(i,D) {
			FOR(j,D) {
				x=abs(i-j);
				dp[0][i]+=dp[1<<x][j]/D;
			}
			dp[0][i]++;
		}
		
		int did=0;
		FOR(i,rolled.size()-1) {
			int x=abs(rolled[i]-rolled[i+1]);
			did|=1<<x;
		}
		int cur=rolled.back()-1;
		return dp[did][cur];
	}
}

まとめ

本番、最大ケースでTLEになるかと思って変な高速化をしようとしていまい、タイムロスした。