kmjp's blog

競技プログラミング参加記です

TopCoder SRM 780 : Div1 Hard RestrictedLeaves

これ800-900ptで良くないかな。
https://community.topcoder.com/stat?c=problem_statement&pm=15963&rd=17853

問題

根付き木を成すグラフが与えられる。
子を持つ頂点は、2個以上の子を持つものとする。
ここで、DFS順に訪問した葉となる頂点間に対し、リング状に辺を追加したグラフを考える。
この際、グラフの頂点の部分集合のうち独立であるものは何通りか。

解法

各点vのSubTreeに対し、v及び最初と最後の葉頂点に対して部分集合に選んだか選んでないかの8通りを状態として持ち、それぞれの組み合わせ数を数えよう。
ある頂点vの連続する子頂点c1,c2に対し、c1の最後の葉頂点とc2の最初の葉頂点は同時には選べないことに注意する。
また、木全体の結果に対し、最初と最後の葉頂点を同時にも選べない。

int N;
vector <int> P;
vector<int> E[1010];

ll dp[1010][8];
const ll mo=1000000007;

class RestrictedLeaves {
	public:
	void dfs2(int cur) {
		if(E[cur].empty()) return;
		sort(ALL(E[cur]));
		int i;
		ll from[8]={};
		FOR(i,E[cur].size()) {
			int e=E[cur][i];
			dfs2(e);
			ll to[8]={};
			
			int x,y;
			if(i==0) {
				if(E[e].empty()) {
					to[0]=to[1]=to[6]=1;
				}
				else {
					FOR(x,8) {
						(to[x&6]+=dp[e][x])%=mo;
						if((x&1)==0) (to[x^1]+=dp[e][x])%=mo;
					}
				}
			}
			else {
				if(E[e].empty()) {
					FOR(x,8) {
						(to[x&3]+=from[x])%=mo;
						if((x&1)==0 && (x&4)==0) (to[x^4]+=from[x])%=mo;
					}
					
				}
				else {
					FOR(x,8) {
						FOR(y,8) {
							if((x&1)&&(y&1)) continue;
							if((x&4)&&(y&2)) continue;
							int z=(x&1)|(x&2)|(y&4);
							(to[z]+=from[x]*dp[e][y])%=mo;
						}
					}
				}
			}
			
			swap(from,to);
		}
		FOR(i,8) dp[cur][i]=from[i];
		
	}
	
	int count(vector <int> parent) {
		P=parent;
		N=P.size();
		int i;
		FOR(i,N) E[i].clear();
		FOR(i,N) if(i) E[P[i]].push_back(i);
		ZERO(dp);
		dfs2(0);
		ll ret=0;
		FOR(i,8) if((i&2)==0 || (i&4)==0) ret+=dp[0][i];
		return ret%mo;
		
	}
}

まとめ

難しく考えすぎてタイムロス。