next_permutation 順列 atcoder

ABC145 C - Average Length

ABC145 C - Average Length
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc145/tasks/abc145_c

$N$個の町の座標$(x_i, y_i)$が与えれるので、町を訪問するすべての道順について距離の平均値を求める問題です.

解説

ある順番での町の訪問においてその総距離は各町間の距離の合計です.
これはすべての町間について計算すれば良いので単純に$O(N)$となります.
すべての町の並べ方は順列なので$P_N$.

C++では配列の順列はalgorithmライブラリに入っているnext_permutationという関数で簡単に生成出来ます.
これはソート済みの配列を与えると破壊的に並べ替えていく関数です.
使い方は解答のソースコードを見てください.

計算量

$$
$O(N \cdot N!)$.
$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define MAX_N 8

Int N;
vector<Vector2> C(MAX_N);

void input() {
  cin >> N;
  loop(n,0,N) cin >> C[n];
  C.resize(N);
}

double distance() {
  double d = 0;
  loop(n,0,N-1) {
    d += (C[n+1] - C[n]).length();
  }
  return d;
}

void solve() {
  sort(span_all(C));
  double d = 0;
  Int p = 0;
  do {
    p++;
    d += distance();
  } while (next_permutation(span_all(C)));
  cout << d / p << endl;
}

int main(void) {
  cout.precision(15);
  input();
  solve();
  return 0;
}