TopCoder SRM 675 Div2 Hard TreeAndPathLength2

解き方がDiv1 Easyとだいぶ変わるのが面白い。
https://community.topcoder.com/stat?c=problem_statement&pm=14092

問題

整数n,sが与えられる。
n頂点からなる木を成すグラフのうち、長さ2のパスがちょうどs個になるようなものは存在するか判定せよ。

解法

1個の頂点にa個の点が連結されている場合、その点を中心とするパスはComb(a,2)個作れることがわかる。
この事実をもとに条件を満たす根付き木を考える。

各Subtreeについて、以下の2値を持つ状態を考える。
dp[頂点数][含む長さ2のパス数][親を持つ(1)/持たない(0)] := そのようなSubTreeが存在するしない

a個の点を持つ頂点はどこにあっても等しくComb(a,2)個のパスを作るので、何処にあっても良い。
よって、子を持つ頂点は常に先頭の子のSubtreeのみに存在すると仮定すると、DFSする際探索する子を1個に絞れる。

後は以下をDPなりメモ化再帰を考えればよい。
dp[n][s][p] := (dp[n-x][s-Comb(x+p,2)][1]=1を満たすxが1個でもあれば1、なければ0)

処理の計算量はO(n^2*s)なので十分間に合う。

int memo[51][1020][2];

class TreeAndPathLength2 {
	public:
	int ok(int n,int s,int par) {
		if(n<=1) return (s==0);
		if(memo[n][s][par]!=-1) return memo[n][s][par];
		int ret=0;
		int i;
		for(i=1;i<=n-1;i++) {
			int sc=(i+par)*(i+par-1)/2;
			if(sc>s) continue;
			ret |= ok(n-i,s-sc,1);
		}
		
		return memo[n][s][par]=ret;
	}
	
	string possible(int n, int s) {
		MINUS(memo);
		if(ok(n,s,0)) return "Possible";
		else return "Impossible";
		
	}
}

まとめ

長さ3でconstructionゲー作りつつ、2でDPゲーと全く異なる問題作るのすごいな。