【AtCoder Beginner Contest 145】C – Average Length (300点)

2019年12月3日AtCoder順列,全探索,300点

問題

平面上でN個の座標が与えられる。全ての点を１回ずつ通るような動き方は\(N!\)通りあるが、これらの総移動距離の平均を求めよ。

元の問題: C – Average Length

解き方

二通りの方法が考えられます。

1. 順列を使って解く方法

順列(N!)の全探索を行って、それぞれの場合の移動距離を計算し、最後に平均を求めれば終了です。C++などでは、next_permutation などを使うと順列を生成できます。

2.各ノード間の移動が何回あるかを考える方法

特定の2つの頂点間の移動は、\(N!\)通り中に、\(2(N-1)!\)回だけ生じます。

これは、2頂点を1つの頂点とみなすと、\((N-1)!\)通りの移動の仕方があるので、2頂点間の順序も含めると2倍の\(2(N-1)!\)通りになるからです。

よって、それぞれの頂点間の距離の総和 sum に対して、

$$ sum \cdot \frac{2(N-1)}{N!} = sum \cdot \frac{2}{N}$$

で答えが求まります。

注意

今回はNが8以下なので、1つ目の順列を用いたプログラムでも計算できました。

ですがNが大きな値になった時は、2つ目の方法で解かないと実行時間がオーバーしてしまうでしょう。

プログラム例

順列を使って解くC++でのプログラムです。

#include <bits/stdc++.h>
using namespace std;

double distance(double xi, double yi, double xj, double yj) {
    // ２点間の距離を求める関数
    return sqrt((xi - xj) * (xi - xj) + (yi - yj) * (yi - yj));
}

int main() {
    // 入力
    int N;
    cin >> N;
    vector<double> x, y;
    for (int i = 0; i < N; i++) {
        double tmp_x, tmp_y;
        cin >> tmp_x >> tmp_y;
        x.emplace_back(tmp_x);
        y.emplace_back(tmp_y);
    }

    // 距離を計算して distance_table に格納しておく
    double distance_table[10][10]; // distance_table[i][j]: i,jの距離
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            distance_table[i][j] = distance(x[i], y[i], x[j], y[j]);
            distance_table[j][i] = distance(x[i], y[i], x[j], y[j]);
        }
    }

    // 順列の始めのケースを作成: {0,1,2,...,n-1}
    vector<int> one_permutation_case;
    for (int i = 0; i < N; i++) {
        one_permutation_case.emplace_back(i);
    }

    double sum_distance = 0; // 総移動距離の合計
    int case_number = 0;     // 何通りあったか
    do {
        // 移動距離を sum_distance に加えていく
        case_number++;
        int now = one_permutation_case[0];
        for (int i = 1; i < N; i++) {
            int next = one_permutation_case[i];
            sum_distance += distance_table[now][next];
            now = next;
        }
    } while (next_permutation(one_permutation_case.begin(), one_permutation_case.end()));

    // setprecision(10) が無いと精度が足りない
    cout << setprecision(10) << sum_distance / case_number << endl;

    return 0;
}

AtCoder順列,全探索,300点