AHC007 解説

Seed=0 の出力

THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）の解説です。

コンテスト中は14,140,583,158点で57位、コンテスト後は14,245,269,557点で1位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

紹介する解法は一例です。特にWriter解は私と異なっており、私よりも高い得点を出しています。
atcoder.jp

問題概要

頂点数が 、辺の数が の無向グラフが与えられ、コストが低くなるように全域木を構築する問題です。

インタラクティブ形式で、辺の長さを入力として受け取るたびに、その辺を採用するか否かを決める必要があります。

方針

モンテカルロ法を使用しました。

乱数を用いて辺の長さをシミュレートし、クラスカル法で不採用時のコストを計算しました。

以下、方針にたどり着くまでの考察、および実装の工夫について解説します。

簡単な問題に帰着する

「〜なら解けるのに！」という反実仮想を解法に結びつけるのは常套手段です（少なくとも私にとって）。

今回の問題の場合、全ての辺の長さが最初からわかっていれば、単なる最小全域木問題を解くだけなので、プリム法なりクラスカル法なりを用いて最適解を得ることができます。つまり、辺の長さを仮定すれば問題が解きやすくなります。

未知の辺の長さを、期待値である などで仮定してもよいのですが、シミュレーションを行ったほうがいい解を得ることができます。

採用するか否かの判定方法

番目の辺について考えます。 がすでに連結の場合は不採用です。そうでない場合を考えます。

採用した場合のコストは入力値 です。"不採用の場合のコスト"を求めれば、採用するか否かを決定できます。

"不採用の場合のコスト"は、クラスカル法で初めて が連結になったときに採用した辺の長さです。なぜなら、その辺の代わりに 番目の辺を用いることができるからです。 が連結にならない場合、コストを とみなすことにします。

モンテカルロ法を用いて"不採用の場合のコスト"の期待値を求めることになります。

高速化

高速化を行うと、その分シミュレーション回数を増やすことができ、期待値の精度が高くなります。

シミュレーションに用いる辺の長さを固定する

辺を毎回生成する必要はなく、最初にシミュレーション回数分の辺を生成して保持します。そうすることで、クラスカル法の前処理で必要となるソートを最初に1回行うだけでよくなります。

無駄な処理を減らす

例えば、1回目のシミュレーションでコストが になった場合、2回目以降のシミュレーションでもコストが になるため、処理を打ち切ることができます。

高速な言語を使用する

PyPyとC++を比較したところ、PyPyだと約11回、C++だと約160回のシミュレーションを行えました。どちらも高速化の余地が残っていそうなので単純な比較はできないのですが、高速な言語のほうがスコアが高くなりやすいと思います。

その他の工夫

ユークリッド距離にかける乱数は、1~3よりも、1.1~2.9のほうがスコアが高くなりました。

提出コード

C++初心者なので、冗長なところがあるかもしれません。

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

double uniform(double l, double r) {
    // l以上r以下の実数をランダムに生成する.
    return l + (r-l) * (double)rand() / RAND_MAX;
}

struct Solver {
    int N;
    int M;
    vector<int> x;
    vector<int> y;
    vector<int> u;
    vector<int> v;
    int repeat;
    double min_cost;
    double max_cost;
    vector<int> distances;
    vector<vector<pair<int,int>>> random_distances;
    dsu uf;

    int get_distance(int i, int j) {
        // Euclid distance
        return round(sqrt((x.at(i)-x.at(j))*(x.at(i)-x.at(j)) + (y.at(i)-y.at(j))*(y.at(i)-y.at(j))));
    }

    void init() {
        N = 400;
        M = 1995;
        x = vector<int>(N);
        y = vector<int>(N);
        u = vector<int>(M);
        v = vector<int>(M);
        repeat = 160; // モンテカルロ法のシミュレーション回数
        min_cost = 1.1; // ユークリッド距離にかける最小値
        max_cost = 2.9; // ユークリッド距離にかける最大値
        distances = vector<int>(M);
        random_distances = vector<vector<pair<int,int>>>(repeat, vector<pair<int,int>>(M));
        uf = dsu(N);
    }

    void input() {
        for (int i = 0; i < N; i++) {
            cin >> x.at(i) >> y.at(i);
        }
        for (int i = 0; i < M; i++) {
            cin >> u.at(i) >> v.at(i);
        }
    }

    void prepare() {
        for (int i = 0; i < M; i++) {
            distances.at(i) = get_distance(u.at(i), v.at(i));
        }
        for (int i = 0; i < repeat; i++) {
            for (int j = 0; j < M; j++) {
                random_distances.at(i).at(j) = make_pair(round(uniform(min_cost,max_cost) * distances.at(j)), j);
            }
            sort(random_distances.at(i).begin(), random_distances.at(i).end());
        }
    }

    int kruskal(dsu uf, int start, int case_number) {
        for (pair<int,int> p : random_distances.at(case_number)) {
            int cost = p.first;
            int idx = p.second;
            if (start < idx) {
                uf.merge(u.at(idx), v.at(idx));
                if (uf.same(u.at(start), v.at(start))) {
                    return cost;
                }
            }
        }
        return -1;
    }

    bool monte_carlo(int start) {
        int sum_costs = 0;
        for (int i = 0; i < repeat; i++) {
            sum_costs += kruskal(uf, start, i);
            if (i == 0 && sum_costs == -1) {
                return true;
            }
        }
        return repeat * distances.at(start) < sum_costs;
    }

    void solve() {
        for (int i = 0; i < M; i++) {
            cin >> distances.at(i);
            if (!uf.same(u.at(i),v.at(i)) && monte_carlo(i)) {
                cout << 1 << endl << flush;
                uf.merge(u.at(i), v.at(i));
            } else {
                cout << 0 << endl << flush;
            }
        }
    }
};

int main() {
    Solver solver;
    solver.init();
    solver.input();
    solver.prepare();
    solver.solve();
}

最後に

私が調べた限りだと、コンテスト中にモンテカルロ法を使用した人はかなり多かったです。それでもスコアに差が出るのは、高速化の度合いやパラメータの調整など、実装に細かな違いがあるからなのかもしれません。

最後まで読んでいただき、ありがとうございました。

はてなブログ初投稿です。