SRM503 Div1 Medium

500

村ごとに計算する。1番近い村が選ばれる確率、2番目に近い村が選ばれる確率、... を計算する。
これを間違わずに実装できる気がしないけれど、本番での正答率はそれなり。
ツラい。

view plainprint?

1. double e_dist(int ax, int ay, int bx, int by)  
2. {  
3.   double x = (ax - bx);  
4.   double y = (ay - by);  
5.   return sqrt(x * x + y * y);  
6. }  
7.   
8. class KingdomXCitiesandVillages  
9. {  
10. public:  
11.   double determineLength(vector <int> cX, vector <int> cY,  
12.                          vector <int> vX, vector <int> vY)  
13.   {  
14.     const int C = cX.size();  
15.     const int V = vX.size();  
16.   
17.     const int F = 50 + 5;  
18.   
19.     double f[F];  
20.     f[0] = 1;  
21.     for (int i = 1; i < F; ++i) {  
22.       f[i] = f[i - 1] * i;  
23.     }  
24.   
25.     double ret = 0;  
26.   
27.     for (int i = 0; i < V; ++i) {  
28.       vector<double> ds;  
29.       double mnC = 1e128;  
30.       for (int j = 0; j < C; ++j) {  
31.         mnC = min(mnC, e_dist(vX[i], vY[i], cX[j], cY[j]));  
32.       }  
33.       for (int j = 0; j < V; ++j) {  
34.         if (i != j) ds.push_back(e_dist(vX[i], vY[i], vX[j], vY[j]));  
35.       }  
36.       sort(ds.begin(), ds.end());  
37.   
38.       for (int j = 0; j < V - 1; ++j) {  
39.         for (int k = 1; k <= (V - 1 - j); ++k) {  
40.           int l = (V - 1) - (j + 1);  
41.           double a = f[l] / f[l - (k - 1)];  
42.           double b = f[k - 1];  
43.           double c = a / b; // nCk  
44.           double prob = c * f[k] * f[V - 1 - k] / f[V];  
45.           double dist = min(mnC, ds[j]);  
46.           ret += prob * dist;  
47.         }  
48.       }  
49.       ret += mnC * f[V - 1] / f[V];  
50.     }  
51.   
52.     return ret;  
53.   }  

double e_dist(int ax, int ay, int bx, int by)
{
  double x = (ax - bx);
  double y = (ay - by);
  return sqrt(x * x + y * y);
}

class KingdomXCitiesandVillages
{
public:
  double determineLength(vector <int> cX, vector <int> cY,
                         vector <int> vX, vector <int> vY)
  {
    const int C = cX.size();
    const int V = vX.size();

    const int F = 50 + 5;

    double f[F];
    f[0] = 1;
    for (int i = 1; i < F; ++i) {
      f[i] = f[i - 1] * i;
    }

    double ret = 0;

    for (int i = 0; i < V; ++i) {
      vector<double> ds;
      double mnC = 1e128;
      for (int j = 0; j < C; ++j) {
        mnC = min(mnC, e_dist(vX[i], vY[i], cX[j], cY[j]));
      }
      for (int j = 0; j < V; ++j) {
        if (i != j) ds.push_back(e_dist(vX[i], vY[i], vX[j], vY[j]));
      }
      sort(ds.begin(), ds.end());

      for (int j = 0; j < V - 1; ++j) {
        for (int k = 1; k <= (V - 1 - j); ++k) {
          int l = (V - 1) - (j + 1);
          double a = f[l] / f[l - (k - 1)];
          double b = f[k - 1];
          double c = a / b; // nCk
          double prob = c * f[k] * f[V - 1 - k] / f[V];
          double dist = min(mnC, ds[j]);
          ret += prob * dist;
        }
      }
      ret += mnC * f[V - 1] / f[V];
    }

    return ret;
  }