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

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

問題

平面上でN個の座標が与えられる。全ての点を1回ずつ通るような動き方は\(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++でのプログラムです。

AtCoder順列, 全探索, 300点