TopCoder SRM 791 : Div1 Medium RandomDijkstraDiv1

落ち着いて考えればよかったな。
https://community.topcoder.com/stat?c=problem_statement&pm=16534&rd=18307

問題

各辺にコストが設定されたN頂点の完全有向グラフが与えられる。
ここでダイクストラ法を行い、各点について頂点0からの最短距離を求める手順を考える。
ダイクストラ法では未処理の点のうち距離が最短なものを選び、そこからの遷移で各点の最短距離を更新していく。
その際、以下2点の変更を加えると、正しくこのアルゴリズムが最短距離を計算する確率はどうなるか。

• 未処理のうち、等確率でランダムで点を選ぶ
• 処理済みの点もそれ以上距離を更新する。(これがdiv2との違い)

解法

各点について、処理済みかどうかと最短距離を保持するかどうかで4通りの状態がある。
そのためグラフ全体では状態がO(4^N)考えられ、TLEが怖い。
ただ実際には全状態に遷移するわけではないので、これでも通る様子。

ここでは、O(3^N*N^2)解法を取る。
各点の状態を以下の3通りとする。

• 未処理
• 処理したが、その時はまだ最短距離を保持していなかった
• 処理したとき、すでに最短距離を保持していた

ある点を処理するとき、その点の最短距離を正しく設定するような点が1つ以上、先に正しく処理済みであれば処理対象の点も最短距離を設定済みとなる。
ここで問題となるのは、全点処理したあと「処理時点では最短距離を保持しないが、その後更新されて最短距離を持つケース」をどう回収するかである。
これは、最終的な状態に対して、改めて各点が最短距離を持ちうるか再計算することで確認できる。

int D[20][20];
int M[20][20];
double dp[5000000];
int p3[15];

class RandomDijkstraDiv1 {
	public:
	double solve(int N, vector <int> G) {
		int i,x,y,z,j;
		FOR(y,N) FOR(x,N) M[y][x]=D[y][x]=G[y*N+x];
		FOR(z,N) FOR(x,N) FOR(y,N) M[x][y]=min(M[x][y],M[x][z]+M[z][y]);
		p3[0]=1;
		FOR(i,14) p3[i+1]=p3[i]*3;
		ZERO(dp);
		dp[0]=1;
		
		double ret=0;
		int mask;
		FOR(mask,p3[N]) if(dp[mask]>0) {
			int ok=0;
			int ng=0;
			int lef=0;
			int cnt=0;
			FOR(i,N) {
				int v=mask/p3[i]%3;
				if(v==2) ok|=1<<i;
				if(v==1) ng|=1<<i;
				if(v==0) lef|=1<<i,cnt++;
			}
			if(lef==0) {
				int isok=1;
				
				FOR(i,N) if(ng&(1<<i)) {
					isok=0;
					FOR(j,N) if((ok&(1<<j))&&M[0][j]+D[j][i]==M[0][i]) isok=1;
					if(isok==0) break;
				}
				if(isok) ret+=dp[mask];
			}
			else {
				FOR(i,N) if(lef&(1<<i)) {
					int isok=1;
					int nmask=mask;
					if(i==0) isok=2;
					FOR(j,N) if((ok&(1<<j))&&M[0][j]+D[j][i]==M[0][i]) isok=2;
					nmask+=isok*p3[i];
					dp[nmask]+=dp[mask]/cnt;
				}
			}
		}
		
		return ret;
		
	}
}

まとめ

本番中に状態をO(3^N)から落とせず唸ってたけど、O(4^N)で実際に試してみてもよかったな。