Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1915-f599ab0c
この記事にトラックバックする(FC2ブログユーザー)

SRM503 DIV1 MEDIUM - KingdomXCitiesandVillages (この記事を編集する[管理者用])

Source

TopCoder SRM503 DIV1 MEDIUM (500pt)
Problem Statement
SRM503 DIV1 自分の参加記録

問題概要

2次元平面上のN個 (50以下) の街とM個 (50以下) の村の座標が与えられる.
最初は道はなく,M個の村は,どの街とも隣接していない.
以下の作業を行ったとき,できる道の総距離の平均値を求める問題.
 ・まだ街に移動できない村を1つ選ぶ これをXと書く
 ・街か,街に移動できる村の中から,Xに一番近いものを選び,その間に道をつくる
 ・街に移動できない村がある限りこれを繰り返す

解法

期待値の線形性を利用して,各村ごとにそこから引く道の長さの期待値を足していけば良い.
後は,その村から,他の村までの距離と,一番近い街までの距離でソートして,
 一番近い村がすでに街に繋がっている確率
 一番近い村がまだ街につながっていなくて,2番目に近い村が街に繋がっている確率
 …
を求めれれば良いことになる.
一番近い村がすでに街に繋がっている確率は,選ばれる順番としては,
 一番近い X
 X 一番近い
が同じように起きるから1/2.
同様に,1番目~k-1番目がXより後に選ばれるという仮定のもと,k番目がXより先の確率は
 k X 1 2 … k-1
 X k 1 2 … k-1
 X 1 k 2 … k-1
  …
 X 1 2 … k-1 k
より1/(k+1)となる.
(上の例では,1~k-1の順番を固定したが,どの順番だと仮定しても同じ確率になるからこれで良い)
一番近い街までの距離より,遠い村は考えず,その場合は一番近い街につなげる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-9

double get_dist(double x,double y){
  return sqrt(x*x+y*y);
}

class KingdomXCitiesandVillages {
public:
double determineLength(vector <int> cX, vector <int> cY, vector <int> vX, vector <int> vY) {
  int i,j,k;
  double res = 0;
  double dist[120], best, tmp, per, con;

  rep(k,vX.size()){
    best = 1e100;
    rep(i,cX.size()){
      tmp = get_dist(cX[i]-vX[k], cY[i]-vY[k]);
      best = min(best, tmp);
    }

    rep(i,vX.size()){
      dist[i] = get_dist(vX[i]-vX[k], vY[i]-vY[k]);
      if(i==k) dist[i] = best;
    }

    sort(dist,dist+vX.size());
    per = 1;
    rep(i,vX.size()){
      if(dist[i] > best-EPS){ res += per*best; break; }

      con = per / (i+2);

      res += con * dist[i];
      per -= con;
    }
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1915-f599ab0c
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。