TopCoder SRM 604 Div1 Medium FoxConnection

正答率がかなり低かった回。
http://community.topcoder.com/stat?c=problem_statement&pm=12919

問題

木を成すグラフがあり、いくつかの点にキツネがいる。
各キツネは、コスト１で１マス移動できる。
また、各キツネは重なることができない。

各キツネのいる点同士がすべて連結するようにキツネを移動させる最小コストを求めよ。

解法

自分を含め大量に引っかかった誤解法は、ある中心を定めてDFSでそこに集まるようにキツネを移動させること。
これだと以下のケースで失敗する。(F=キツネのいる点、*=いない点)
T字路の中心にキツネを集めると左右のキツネを動かすコストがかかるが、真ん中の縦棒上のキツネを左右に振り分ける方がコストが低い。

F-F-F-F-*-*-*-F-F-F-F
          |
          F
          |
          F
          |
          F

上記誤回答でもpretestの範囲は通過できるため、大量のsubmitが発生した。

上記のことからわかるのは、遠くにあるキツネを中心に寄せるより、中心に近いキツネを遠くに送る方が低コストな場合もあること。
Editorialはこのアプローチを採用した。

中心点を定めてDFSする点は上記誤回答と同じだが、各subtreeに対しキツネを中心に集めるだけでなく、他のsubtreeのキツネからあるsubtreeに余分なキツネを送り込む点がことなる。

subtreeの状態として、[現在位置][辺の番号][処理するキツネ数]と３つ持たせる。
処理するキツネ数のうち、１つは(連結するという条件を満たすために)現在位置に配置するが、残りの(処理するキツネ数-1)を各subtreeの辺に送り込むまたは引き取るコストをDPで求めていく。

なお、状態が３つあるので処理オーダーはO(N^3)に思えるが、実際は辺は全部でN-1本しかないので実際はO(N^2)。
中心点を総当たりするので全体でO(N^3)で処理できる。
Editorialは中心点を総当たりする際に過去の計算結果を流用するため、速度は早いけどちょっと余分なコードがあるね。

string F;
vector<int> E[52],E2[52];
int N,TF;
int NF[52];
int memo[52][52][52];

class FoxConnection {
	public:
	string F;
	
	int dfscount(int cur,int pre) {
		int i;
		NF[cur]=F[cur]=='Y';
		E[cur].erase(remove(E[cur].begin(),E[cur].end(),pre),E[cur].end());
		FOR(i,E[cur].size()) NF[cur] += dfscount(E[cur][i],cur);
		return NF[cur];
	}
	
	int dfsdfs(int cur,int e,int lf) {
		if(memo[cur][e][lf]>=0) return memo[cur][e][lf];
		if(e==E[cur].size()) return memo[cur][e][lf] = (lf <= 1) ? 0 : 1<<20;
		
		int tar=E[cur][e];
		memo[cur][e][lf] = 1<<20;
		for(int sf=0;sf<=max(0,lf-1);sf++) {
			memo[cur][e][lf] = min(memo[cur][e][lf], abs(sf-NF[tar]) + dfsdfs(tar,0,sf) + dfsdfs(cur,e+1,lf-sf));
		}
		return memo[cur][e][lf];
	}
	
	
	int minimalDistance(vector <int> A, vector <int> B, string haveFox) {
		N=A.size()+1;
		int i,x,y;
		
		F=haveFox;
		TF=count(F.begin(),F.end(),'Y');
		if(TF<=1) return 0;
		
		FOR(x,N) E2[x].clear();
		FOR(x,N-1) E2[A[x]-1].push_back(B[x]-1),E2[B[x]-1].push_back(A[x]-1);
		
		int mi=1<<20,center;
		FOR(center,N) {
			MINUS(memo);
			FOR(x,N) E[x]=E2[x];
			dfscount(center,-1);
			mi=min(mi,dfsdfs(center,0,TF));
		}
		return mi;
	}
};

まとめ

辺ごとのDPはあまり経験がなくてすんなり思いつけなかった。