TopCoder SRM 503 Div1 Medium KingdomXCitiesandVillages

これもDiv2 Hardとの問題設定の変え方が面白い。
http://community.topcoder.com/stat?c=problem_statement&pm=11063

問題

基本的な設定はDiv2 Hardと同じである。
TopCoder SRM 503 Div2 Hard KingdomXCitiesandVillagesAnother - kmjp's blog

ただ、Div2 Hardはこちらの任意の順番で道路を整備できたが、こちらは町につなげる村の順番が等確率でランダムに指定される。
最小整備コストの期待値を答えよ。

解法

ある村から出る道路を整備する場合、もし近くに別の村があっても、その村は未整備で町と接続されてなければそこは選択できない。

各村iから出る道路を考える際、他の村を村iからの距離でソートする。
村iが距離順j番目の村に道路を作る確率は(j-1)番目までの村が未整備で、j番目の村が整備済みの場合である。
よってこの確率とj番目の村までの距離を掛け合わせていけばよい。

なお、途中で距離順j番目の村より最寄りの町の方が近くなるなら、距離として後者と採用すればよい。

double dist[52][52];

class KingdomXCitiesandVillages {
	public:
	double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
		int C=cityX.size(), V=villageX.size();
		int x,y,i;
		FOR(x,V) FOR(y,V) {
			dist[x][y]= sqrt((villageX[x]-villageX[y])*(ll)(villageX[x]-villageX[y])+(villageY[x]-villageY[y])*(ll)(villageY[x]-villageY[y]));
		}
		FOR(x,V) {
			dist[x][50]=1e20;
			FOR(y,C) dist[x][50] = min(dist[x][50],
				sqrt((villageX[x]-cityX[y])*(ll)(villageX[x]-cityX[y])+(villageY[x]-cityY[y])*(ll)(villageY[x]-cityY[y])));
		}
		
		double ret=0;
		FOR(x,V) {
			vector<double> D;
			FOR(y,V) if(x!=y) D.push_back(min(dist[x][y],dist[x][50]));
			sort(D.begin(),D.end());
			double r=1;
			FOR(i,D.size()) {
				ret += D[i]*r/(2+i);
				r*=(1+i)/(2.0+i);
			}
			ret += dist[x][50]*r;
			
		}
		return ret;
	}
};

まとめ

ここらへんDiv1 Mediumだけど割とサクサク解けている。