mayoko’s diary

プロコンとかいろいろ。

SRM 503 div1 med:KingdomXCitiesandVillages

そこそこ惜しかったな…

解法

普通にやろうとするとN!通りとかN*2^N通りとか試さないといけないので当然間に合いません。期待値だともはやありきたりな感じがありますがこういう時は期待値の線形性を利用して計算量を落とすことを考えます。

それぞれの村について,その村(A村とする)が選ばれる時に最短距離の村(町)としてどの村(町)が選ばれるのかを考えます。そのためにまずA以外の村iに対して,村iと村Aとの距離を配列に記録しておき,ソートします。

この時,i番目の村とA村との距離(村iと村Aの距離が村Aと町の距離の最小値より小さかったら村iと村Aの距離はその最小値が採用されると考える)が採用されるのはどのような場合かを考えます。iより小さいインデックスの村が先に選ばれているとすると,Aとその村との間の距離のほうが短いのでそちらが選ばれてしまいます。よって,i番目の村とA村との距離が採用されるためには,0〜i-1番目までの村はAより後ろで選択されることになります。

ではこのような村の選ぶ順序は全体のうちどれくらいの確率で起こるものなのでしょうか?それがわかればもう勝ったも同然です。というか本番はここで迷っていました。

今回の場合は考慮すべきなのは0〜i-1番目の村までとi番目の村と村Aだけです。他の村はどこにいても良いので全体は(i+2)!通りと解釈しても良いです。この中で,村Aと村iはi->Aという順序で並んでなければならず,かつ0からi-1番目の村はAの後に並ばなければなりません(これはi!通り)。
よって,i番目の村とA村との距離が採用される確率は,

\frac{i!}{(i+2)!} = \frac{1}{(i+1)(i+2)}

です。これを用いてすべての村についてその村をconnectするときかかるコストの期待値を求め,その和を取れば答えを求めることが出来ます。

以下ソースコード

ll square(int x) {
    return (ll)x*x;
}

ll getDist(int x, int y, int X, int Y) {
    return (square(X-x) + square(Y-y));
}

double dist[55];

class KingdomXCitiesandVillages {
public:
    double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
        int n = cityX.size();
        int m = villageX.size();
        for (int i = 0; i < m; i++) {
            ll mindist = 1ll<<55;
            for (int j = 0; j < n; j++) {
                mindist = min(mindist, getDist(cityX[j], cityY[j], villageX[i], villageY[i]));
            }
            dist[i] = sqrt(1.*mindist);
        }
        double ans = 0;
        for (int i = 0; i < m; i++) {
            vector<double> dd;
            for (int j = 0; j < m; j++) {
                if (i == j) continue;
                dd.push_back(sqrt(getDist(villageX[i], villageY[i], villageX[j], villageY[j])));
            }
            sort(dd.begin(), dd.end());
            ans += dist[i]/m;
            for (int j = 0; j < m-1; j++) {
                cout << dd[j] << endl;
                double d = min(dd[j], dist[i]);
                ans += d/((j+2)*(j+1));
            }
            cout << ans << endl;
        }
        return ans;
    }
};