TopCoder SRM 725 Div1 Medium HiddenTree

これはまぁまぁすんなり。
(URL掲載待ち)

問題

N頂点の有向グラフを考える。
グラフはDAGを成しており、かつ各頂点の入次数は高々1とする。
各頂点は２つの値を持ち、頂点自身の重さと、頂点から遷移可能な頂点の重さの総和を持つ。
このうち後者のみ与えられているものとする。
後者の重さの条件を満たすような有向グラフは何通りあるか。

解法

Nが14以下ということからO(3^N)解法が思い浮かぶ。
重さの総和が小さい点から大きい点に辺を張ることはない。
よって重さの総和が小さい点から順に頂点の辺の張り先を決めていこう。

自身より重さの総和が小さい頂点は、そこから辺を張る先をすべて確定済みとする。
このうち、入次数が1以下という条件より、まだ入次数が0、すなわちまだ辺の行先として受け入れうる頂点をbitmaskで管理しよう。

重さの総和が下からv番目まで処理した状態におけるbitmaskは、下記のように遷移できる。

• 直前の状態はv-1番目まで処理した状態のはずなので、v-1番の頂点に対応するビットが立っているはずである。
• 直前の状態と今のbitmaskを比べ、消えたビットを比較すると、それらはv番目から辺が張られた頂点に対応するものであり、それらの重さの総和がv番目の重さの総和以上になってはならない。

これらの条件より、遷移直前の状態はほぼ現在ののbitmaskからv番目のbitを落とした状態を含むものに限定される。
このようにbitmaskを列挙する過程で、さらにそのbitmaskを含むbitmaskを総当たりする処理はO(3^N)で処理できる。

int mo=1000000007;
ll sum[1<<14];
int dp[1<<14];


class HiddenTree {
	public:
	int N;
	int count(vector <int> b) {
		N=b.size();
		if(N==1) return 1;
		
		sort(ALL(b));
		int i;
		for(int mask=0;mask<1<<N;mask++) {
			sum[mask]=0;
			FOR(i,N) if(mask&(1<<i)) sum[mask]+=b[i];
		}
		
		dp[0]=dp[1]=1;
		ll ret=0;
		for(int mask=2;mask<1<<N;mask++) {
			int high=0;
			dp[mask]=0;
			FOR(i,N) if(mask&(1<<i)) high=i;
			int bef=(mask ^ (1<<high)) | (1<<(high-1));
			for(int bmask=bef; bmask<(1<<high); bmask=(bmask+1)|bef) {
				int del=bmask^mask^(1<<high);
				
				if(sum[del]<b[high]) {
					dp[mask] += dp[bmask];
					if(dp[mask]>=mo) dp[mask]-=mo;
				}
			}
			
			if(high==N-1) {
				ret+=dp[mask];
			}
		}
		
		return ret%mo;
		
		
	}
}

まとめ

Nが14以下ってのがヒントとして強すぎるな。