TopCoder SRM 662 Div1 Medium ExactTree

これは自力では解けず。
http://community.topcoder.com/stat?c=problem_statement&pm=13857

問題

N頂点からなる木Tを作りたい。
木のコストS(T)は、全頂点ペア間の距離の和だとする。
S(T) mod M == Rとなる最小のS(T)が存在するならそれを答えよ。

解法

p頂点の木T1とq頂点の木T2の間を辺でつないだ木T3を考える。
S(T)にはその辺によりp*q分コストが加算されることになる。
すなわちS(T3)=S(T1)+S(T2)+p*qとなる。

この考えをもとに、n頂点でMで割った余りがrになる木の最小コストをdp[n][r]=最小コストの形で管理し、DPで更新して最後にdp[N][R]を答えればよい。

１点注意点として、上記式では２つの木の連結による辺のコストをp*qで計算している。
しかし実際は最終的には辺の両端は計N頂点になることになることを考慮しなければならない。
よってT1側の木はそれ以上他の木を連結せずT2側にのみ連結する、と仮定し、S(T3)=S(T1)+S(T2)+p*(N-p)で更新していけば問題ない。

int dp[51][101];

class ExactTree {
	public:
	int getTree(int n, int m, int r) {
		MINUS(dp);
		dp[1][0]=0;
		int i,j,x,y;
		for(i=2;i<=n;i++) {
			for(j=1;j<i;j++) {
				FOR(x,m) FOR(y,m) if(dp[j][x]>=0 && dp[i-j][y]>=0) {
					int z=dp[j][x]+dp[i-j][y]+j*(n-j);
					if(dp[i][z%m]==-1) dp[i][z%m]=z;
					dp[i][z%m]=min(dp[i][z%m],z);
				}
			}
		}
		return dp[n][r];
	}
}

まとめ

距離の総和を求める場合には、各辺を何回またぐかを考えればよい。
しばしば使うテクなのに忘れてたな…。