AtCoder Beginner Contest 145 C - Average Length

遅いですが部屋にコタツを出しました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc145/tasks/abc145_c)にて開催されました、AtCoder Beginner Contest 145 C問題「C - Average Length」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

座標平面上に N 個の町があります。町 i は、座標 ( x[i] , y[i] ) に位置しています。町 i と町 j の間の距離は √( ( x [i] − x [j] )² + ( y [i] − y [j] )²) です。

これらの町を全て 1 回ずつ訪れるとき、町を訪れる経路は全部で N ! 通りあります。 1 番目に訪れる町から出発し、 2 番目に訪れる町、 3 番目に訪れる町、 … 、を経由し、 N 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの N ! 通りの経路の長さの平均値を計算してください。

2.制約

• 2 ≤ N ≤ 8
• − 1000 ≤ x[i] ≤ 1000
• − 1000 ≤ y[i] ≤ 1000
• ( x i , y i ) ≠ ( x j , y j ) ( i ≠ j のとき)
• 入力中の値はすべて整数である。

3.入力例

• 入力

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

• 出力

7641.9817824387

4.初見の感想

• 「町1→町2→町3」と「町3→町2→町1」は実は経路の長さが同じ
• つまり出発地と到着地を入れ替えたら経路の長さが同じ！
• 経路は半分だけ考えればよい

5.学びポイント

• 「町1→町2→町3」の時なら「町3→町1」の距離を3つの町のループ から引いたとも考えられる
• 平均をとることを考えると、それぞれの経路が使われる回数は「N個の連続する点の中から連続する2点の選び方」になるのでN-1回になる
• それぞれの経路和×(N-1)/総数で平均計算

6.コードと簡単な解説

using System;

class Program
{
    static void Main(string[] args)
    {
//入力値のパース
        int N = int.Parse(Console.ReadLine());
        int[] x = new int[N];
        int[] y = new int[N];
        for(int i = 0; i < N; i++)
        {
            string[] input = Console.ReadLine().Split();
            x[i] = int.Parse(input[0]);
            y[i] = int.Parse(input[1]);
        }
//経路の総和計算
        double ans = 0;
        double count = 0;
        for(int i = 0; i < N - 1; i++)
        {
            for(int j =i+1; j < N; j++)
            {
                ans += Math.Sqrt(Math.Pow(x[i] - x[j], 2) + Math.Pow(y[i] - y[j], 2));
                count++;
            }
        }
//平均の計算
        Console.WriteLine(ans * (N-1)/ count);
    }
    
}

7.最後に

頭では理解しているのに、説明するのは難しい…