まぁ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の方が問題として面白いかな。