TopCoder SRM 713 Div1 Medium DFSCount、Div2 Hard DFSCountEasy

なんか似たのをCodeforcesで見た。
https://community.topcoder.com/stat?c=problem_statement&pm=14588
https://community.topcoder.com/stat?c=problem_statement&pm=14589

問題

連結無向グラフが与えられる。
任意の頂点から初めて、未訪問の隣接点のうち、任意の点を選ぶ、というDFSを行うことを考える。
訪問順のうちあり得る並び順は何通りあるか。

解法

訪問順が決まっているタイプは、Codeforcesで出ている。
Codeforces #289 Div2 F. Progress Monitoring - kmjp's blog

上記の考え方を応用して、BitDPで解く。
以下の状態を考える。

f(mask,v) := vから初めて、maskに相当する頂点群を訪問し、今vに戻ってきたところである、という訪問順

さて、今vから別の未訪問の頂点群で構成された部分木の根に移動することを考える。
このとき、mask中v以外の頂点から移動可能な頂点は、DFSの特性上すべて訪問済みであるはずである。

上記表現をアルゴリズムに落とし込もう。
mask = A | Bと２つのbitmaskに分解できたとする。(Aはvを含み、Bはvを含まないとする。)
vからBのいずれかの頂点wに遷移するためには、v→wに移動可能で、かつAからvを除く頂点群から、Bの頂点群に遷移できないことが条件である。
条件を満たすとき、f(mask,v) += f(A,v) * f(B,w)で解を数え上げていくとよい。

ll dp[1<<15][16];

class DFSCount {
	public:
	long long count(vector <string> G) {
		int N=G.size();
		int tmask[15]={};
		int i,j,y,x;
		
		ZERO(dp);
		FOR(y,N) FOR(x,N) if(G[y][x]=='Y') tmask[y] |= 1<<x;
		FOR(i,N) dp[1<<i][i]=1;
		
		for(int mask=0;mask<1<<N;mask++) {
			FOR(x,N) if(mask&(1<<x)) {
				for(int smask=(mask^(1<<x));smask>=0;smask--) {
					smask &= (mask^(1<<x));
					int base=mask^smask;
					if(dp[base][x]==0) continue;
					
					int maskto=0;
					FOR(y,N) if((base&(1<<y))&&x!=y) maskto |= tmask[y];
					if(maskto & smask) continue;
					FOR(y,N) if(smask & tmask[x] & (1<<y))  dp[mask][x] += dp[base][x]*dp[smask][y];
				}
			}
		}
		
		return accumulate(dp[(1<<N)-1],dp[(1<<N)-1]+N,0LL);
	}
}

まとめ

よくある末尾要素を覚えるbitdpではなく、先頭要素を覚えるbitdpってのが新鮮。