C – Average Length解説 abc-145

Atcoder

Atcoder

こんにちは！seiです！
・Atcoderの提出済み解答をみてもよく分からない…
・もっとわかりやすい解説が知りたい！

この記事は初心者向けにAverage Lengthを詳しく解説した記事です。
Atcoderを始めて17日が経過しました！

1 問題概要と制約条件の理解
2 「Average Length」問題の解法
3 Average Lengthの計算量
4 まとめ

問題概要と制約条件の理解

問題はこちら↓

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

この問題では、N個の点が与えられ、それらを全て一度ずつ訪れるときの経路の長さの平均値を求める問題です。

制約条件は以下の通りです。

2≤N≤8
-1000≤xi≤1000
-1000≤yi≤1000
(xi,yi)≠(xj,yj) (i≠jのとき)

解法のポイント：順列全探索を使用する

順列全探索は、与えられた数列の全ての順列を生成する方法です。C++のSTLには、順列全探索を行う関数であるnext_permutation()が用意されています。

「Average Length」問題の解法

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

int main()
{
    int n, x[10], y[10];

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
    }

    vector<int> indices(n);
    iota(indices.begin(), indices.end(), 0);
    double cnt = 0, total_distance = 0;
    do
    {
        double tmp_distance = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int now = indices[i], next = indices[i + 1];

            tmp_distance += sqrt(pow(x[next] - x[now], 2) + pow(y[next] - y[now], 2));
        }
        cnt++;
        total_distance += tmp_distance;
    } while (next_permutation(indices.begin(), indices.end()));

    printf("%.10f\n", total_distance / cnt);

    return 0;
}

この問題は、全ての町の番号の順列を生成し、それぞれの順列において経路の距離を求め、それを平均することで解けます。
21行目までは標準入力から値を受け取っている部分です。

vector<int> indices(n);
iota(indices.begin(), indices.end(), 0);

ここでは、indicesという名前のvectorを定義しています。このvectorは、順列全探索に用いる数列を格納するためのものです。iota()関数は、indicesに0からn-1までの数値を順番に格納しているだけです。indicesは[0,1,…,n-1]の配列となります。

double cnt = 0, total_distance = 0;

次に、経路の総距離を求めるための変数cntとtotal_distanceを宣言しています。cntは順列全探索において、生成された順列の総数をカウントするために使用されます。total_distanceは、順列全探索で求めた全経路の総距離を格納するために使用されます。

do{
        double tmp_distance = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int now = indices[i], next = indices[i + 1];

            tmp_distance += sqrt(pow(x[next] - x[now], 2) + pow(y[next] - y[now], 2));
        }
        cnt++;
        total_distance += tmp_distance;
    } while (next_permutation(indices.begin(), indices.end()));

ここで、do-whileループを用いて、順列全探索を行っています。do内の処理は必ず一回以上行われ、あとはwhileの条件を満たすまで繰り返されます。

next_permutation()関数ではindicesを昇順における次の順列に書き換えています。

next_permutation()関数は、指定された要素が全て違う場合、昇順における次の順列を生成し、trueを返します。もし、指定された要素が全て同じ場合は、falseを返します。昇順における最後の順列に用いた場合もfalseを返します。

例えば、{1, 2, 3}という要素を持つ配列があった場合、next_permutation()関数を5回呼び出すことによって、次のような順列が順番に生成されます。

{1, 2, 3} → {1, 3, 2} → {2, 1, 3} → {2, 3, 1} → {3, 1, 2} → {3, 2, 1}　（昇順）

※{3, 2, 1}は最後の順列なので、これにnext_permutation()を使うとfalseを返す。

このように、next_permutation()関数は昇順における最初の順列を与えれば、全ての順列を生成することができます。

ループ内では、順列全探索で生成された順列に対して、以下の処理を行います。

double tmp_distance = 0;
for (int i = 0; i < n - 1; i++)
{
    int now = indices[i], next = indices[i + 1];

    tmp_distance += sqrt(pow(x[next] - x[now], 2) + pow(y[next] - y[now], 2));
}

① 順列に対応する経路の総距離を求める

順列に対応する経路の総距離を求めるために、forループを用いて、隣り合う町の距離を計算しています。計算方法は、sqrt(pow(x[next] – x[now], 2) + pow(y[next] – y[now], 2))で求めています。ここで、nowは現在いる町のインデックス、nextは次に移動する町のインデックスを表しています。

cnt++;

② 経路の総数をカウントする

順列全探索で生成された順列の総数をカウントするために、変数cntに1を加算しています。

total_distance += tmp_distance;

③ 全経路の総距離をカウントする全経路の総距離をカウントするために、変数total_distanceに順列全探索で生成された順列に対する経路の距離を足しています。

printf("%.10f\n", total_distance / cnt);

④ 平均値を計算して出力する

全経路の総距離を全経路の総数で割ることで、平均値を求め、小数点以下10桁まで出力しています。total_distanceをdouble型で定義するのを忘れないように！

Average Lengthの計算量

順列全探索では、全ての順列を生成するため、O(N!)の計算量が必要です。普通にforで全探索をする場合は、Nの数によって入れ子のforの数が異なってくるので、実装できません。例えばN=8の時は8回forを書く必要があるし、N=4だったら4回forを書く必要があります。
こういう場合は再起関数を用いると解ける場合があります。再起関数は僕のような初心者は間違えやすいし、実装に時間がかかると思うので、まずは順列全探索から固めるのをお勧めします！

まとめ

「Average Length」問題は、座標平面上にある複数の点を巡回する最適な経路を求める問題でした。順列全探索を用いることで、全ての順列を生成しながら最適な経路を求めることができます。いままで取り組んできた全探索は「問題文の通りに全探索する」、「答えとして考えられるものから全探索する」、「全探索する対象をずらす」問題を解いてきました。いままでは「値」を全探索していましたが、順列全探索では「インデックス」を全探索しているところが難しいポイントかなと思います。
引き続きAtcoder取り組んでいきます！