kmjp's blog

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

TopCoder SRM 725 Div2 Hard HiddenTreeDiv2

まぁDiv1が分かっていればすぐだね。
(URL掲載待ち)

問題

概ねDiv1 Mediumと同じである。
ただ、こちらは名に各頂点の重さが与えられており、条件を満たす辺の張り方が1通りでも存在するかチェックする。

解法

解法もおよそDiv1Mediumと同じ。
数を数え上げるのではなく、解の有無を管理するだけ。
TopCoder SRM 725 Div1 Medium HiddenTree - kmjp's blog

ll sum[1<<14];
int dp[1<<14];

class HiddenTreeDiv2 {
	public:
	string isPossible(vector <int> a, vector <int> b) {
		int N=a.size(),i,j;
		
		FOR(i,N) FOR(j,N-1) {
			if(b[j]>b[j+1]) swap(a[j],a[j+1]),swap(b[j],b[j+1]);
		}
		for(int mask=0;mask<1<<N;mask++) {
			sum[mask]=0;
			FOR(i,N) if(mask&(1<<i)) sum[mask]+=b[i];
		}
		ZERO(dp);
		dp[0]=1;
		for(int mask=1;mask<1<<N;mask++) {
			int high=0;
			FOR(i,N) if(mask&(1<<i)) high=i;
			int pre=mask^(1<<high);
			if(high) pre |= 1<<(high-1);
			
			for(int bmask=pre;bmask<1<<high;bmask=(bmask+1)|pre) {
				int dif=mask^bmask^(1<<high);
				if(sum[dif]+a[high]==b[high] && dp[bmask]) dp[mask]=1;
			}
			if((mask&(1<<(N-1))) && dp[mask]) return "Possible";
		}
		return "Impossible";
		
	}
}

まとめ

これはさすがにDiv1の方が問題として面白いかな。