【競プロ】1日1AC : ABC145 C問題 Average Length

今日の問題はこちら。

提出コードと考え方

距離を求める部分は問題ないはずなので、経路を全列挙すれば終わりです。

やったことがないと困るかもしれませんが、C++ならnext_permutationを使うのが楽です。Pythonならitertools.permutationsでしょうか。

機能を軽く説明します。

next_permutation(first, last)のように配列の範囲[first, last)を渡すと、その部分を辞書順が次に大きい順列に置き換えます。

また、この関数は次の順列が存在するときtrue、存在しないときfalseを返します。そのため、提出コードのようにdo-whileで書くのが便利です。

具体的な処理部分についてはこれで終わりですが、もう一つ。

iota(first, last, value)は配列の範囲[first, last)に「value, value+1, …」を前から順に代入するものです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < n;i++)

vector<pair<int,int>> p(8);

double dist(int from, int to) {
    int dx = p[to].first - p[from].first;
    int dy = p[to].second - p[from].second;
    return pow(dx * dx + dy * dy, 0.5);
}

int fact(int n){
    int res = 1;
    for(int i = 2;i <= n;i++) res *= i;
    return res;
}

int main() {
    int n;
    cin >> n;
    rep(i,n) cin >> p[i].first >> p[i].second;
    vector<int> root(n);
    iota(root.begin(),root.end(),0);
    double ans = 0;
    do {
        rep(i,n-1) ans += dist(root[i],root[i+1]);
    } while (next_permutation(root.begin(),root.end()));
    ans /= fact(n);
    printf("%.10lf\n",ans);
}

全列挙する問題は意外と差がつきやすいので、この機会に覚えましょう。