TopCoder SRM 622 Div1 Medium Ethernet

なんとか自力で解いたけどかなり苦戦。
http://community.topcoder.com/stat?c=problem_statement&pm=13186

問題

辺に距離があり、木を成したN点のグラフが与えられる。
これらのグラフをいくつかに分割したとき、各グラフの直径がmaxDist以下になるようにしたい。
最小で何個のグラフに分割する必要があるか。

解法

各頂点をDFSでたどりつつDPしていく。
状態としてDP[頂点番号][親側の最遠距離]を持ち、親側と連結されないグラフ数の最小値を求めていく。

このDPにおいて、「親側の最遠距離」を例えばXとする。
この時、子のうち１個は同じグラフにできる最長距離Yに対し再帰的に処理を行う。(X+Y==maxDist)
残りの子は、最長距離Zに対し再帰的に処理を行う。(max(X,Y)+Z==maxDist)

ただし、各子は最長距離YないしZの範囲で無理に連結させるより、子は別グラフにした方が結果的に総グラフ数は減る場合があるため、連結させる場合とさせない場合のうちグラフ数が小さい方の値を取る。

以下のコードはO(N^2*maxDist^2)。
O(N*maxDist^2)にすることも容易だが、これで間に合ったので計算量は落としていない。

int memo[55][501];

class Ethernet {
	public:
	vector<pair<int,int> > E[55];
	
	int connect(vector <int> parent, vector <int> dist, int maxDist) {
		int N=parent.size()+1;
		int i,j,k,l,m,x,y;
		
		FOR(i,55) E[i].clear();
		ZERO(memo);
		
		FOR(i,N-1) E[parent[i]].push_back(make_pair(i+1,dist[i]));
		for(i=N-1;i>=0;i--) {
			FOR(j,maxDist+1) if(!E[i].empty()) {
				memo[i][j]=10000;
				
				for(k=1;k<=maxDist-j;k++) {
					l=maxDist-max(j,k);
					if(l>k) continue;
					FOR(x,E[i].size()) {
						m=0;
						FOR(y,E[i].size()) {
							int f=E[i][y].first,s=E[i][y].second;
							int t=s+((x==y)?max(j,l):max(j,k));
							m+=min((t>maxDist)?10000:memo[f][t],1+memo[f][0]);
						}
						memo[i][j]=min(m,memo[i][j]);
					}
				}
			}
		}
		
		return memo[0][0]+1;
	}
}

まとめ

面倒なDPだったな。