AHC006 解説

Seed=0 の出力

京セラプログラミングコンテスト（AtCoder Heuristic Contest 006） の解説です。

コンテスト中は1,764,699点で57位、コンテスト後は2,110,386点で10位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

紹介する解法は一例です。もっといい解法があるかもしれません。

問題概要

デリバリーサービスを題材とした問題です。

注文が1000件入っており、 番目の注文は にあるレストランから への配達依頼です。移動にはマンハッタン距離の分だけ時間がかかります。また、任意個の料理を同時に運ぶことができます。

50件の注文を処理できるような配達ルートで、移動時間が短いものを求めてください。

方針

貪欲法で得られた解をベースに、注文の入れ替えと2-optで焼きなましました。

なお、この方針はWriterであるwataさんのツイートを参考にしています。 https://twitter.com/wata_orz/status/1459840344062050304

TSP（巡回セールスマン問題）に帰着する

50件の注文を固定した場合、TSPに訪問順序の制約をつけたものとみなすことができます。"訪問順序の制約"というのが厄介ですが、条件付きで2-optという強力な手法を用いることができます。2-optがわからない人は"TSP 2-opt"などで検索するといいと思います。

注文の入れ替え

まず、50件の注文のうち1件を削除します。

次に、採用していない950件のうち何件かを選択し、最適位置に挿入したときのコストが最も小さいものを選び、それを追加します。（"何件か選択し"というのは1件でもいいと思います。）

焼きなまし法のスケジューラーにかけて、採用の場合は変更を保存し、不採用の場合は元に戻すようにします。

挿入最適位置を求めるアルゴリズム

注文の個数を とします。 の全探索をせずとも、 で最適位置を求めることができます。

レストランを 番目より前に挿入したときの最小コスト

配達先を 番目以降に挿入したときの最小コスト

レストランと配達先の両方を 番目に挿入したときのコスト

とすると、最小コストは となります。 は前から、 は後ろから でそれぞれ求められるため、全体の計算量も になります。

の操作を何度か行うことになるため、この処理がボトルネックになりやすいと思います。精度を犠牲にして、より速いアルゴリズムを用いたほうがよいかもしれません。

初期解に貪欲法を用いたと述べましたが、その貪欲法とは、この最適挿入を50回繰り返すだけです。うまく実装すれば同じ関数を使えます。

2-opt

訪問順序の制約により、単純な2-optは使えません。そこで、繋ぎ直しても順序が逆転しない場合にのみ処理を行うようにすればよいです。

ある範囲の順番を入れ替えるときに、レストランと、その対応する配達先のペアが両方範囲に含まれている場合には、繋ぎ直したときに順序が逆転してしまうので2-optを適用できません。それ以外の場合には2-optを適用できます。

提出コード

atcoder.jp 約300行です。最適挿入位置を求めるところで少し苦労しました。

最後に

「いくつかの点を選んでTSPに帰着する」というのはAHC005と似ていますが、注文の選び方が難しく、また、単純な2-optが使えないので、今回ならでは難しさがあるなあと思いました。

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

AHC005 解説

Seed=0 の出力

AtCoder Heuristic Contest 005 の解説です。

コンテスト中は10,370,989点で231位、コンテスト後は22,301,086点で2位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

紹介する解法は一例です。もっといい解法があるかもしれません。

問題概要

の二次元グリッドが与えられます。各マスは道路か障害物です。指定されたマス からスタートして、 に戻るような経路で、全ての道路を一度は視界に入れるようなもののうち、移動距離が短いものを求める問題です。

制約

方針

交差点をうまく選んでTSP（巡回セールスマン問題）に帰着しました。

貪欲法で求めた解をベースにして、交差点の入れ替え、3-opt、Double-Bridgeを繰り返しました。

交差点を全列挙する

交差点を"上または下、かつ、左または右に道路が続いているマス"と定義します。道路と道路は交差点で接続しています。

道路と交差点

例えば上の図では道路（青）が交差点（赤）で接続していることがわかると思います。

よって、全ての道路を網羅するように交差点を選ぶことで、TSPに帰着することができます。TSPを解くためのアルゴリズムは非常によく研究されており、それらを使用することができます。

交差点間の距離を求める

全ての交差点間の距離を求めます。私はワーシャルフロイド法を使いましたが、ダイクストラ法を 回適用しても同様の結果を得られます。いずれにせよ、後から経路復元を行えるようにしておく必要があります。

も交差点として扱うと実装が楽になります。また、後でSymmetric TSPに帰着するために、交差点のコストを0とみなすとよいと思います。（コスト計算のときは交差点のコストも考えます。）

貪欲法で初期解を得る

全ての道路を網羅するためには、各道路が含む交差点のうち、最低1つの交差点を通る必要があります。下の図を例に見てみましょう。

道路と交差点

最下段の横の道路は、3,4,5番の交差点のうち1つを通れば十分です。

最も右の縦の道路はどうでしょうか。この道路は5番の交差点しか含まないので、5番は必ず通る必要があります。このように、必ず通る必要がある交差点を"必須交差点"と呼ぶことにします。

必須交差点を1つずつ最適位置に挿入し、その後、無駄にならない交差点を1つずつ最適位置に挿入することで、1つの貪欲解を得ることができます。

貪欲法のやり方は人それぞれだと思うので、参考程度にしていただけたらと思います。

ILS（反復局所探索法）を行う

交差点の入れ替えと3-optで山登り法を行い、たまにDouble-BridgeでKickを行いました。3-optやDouble-Bridgeなどがわからない人は下記のサイトを読むといいと思います。

future-architect.github.io

回数の割合としては、Double-Bridge、交差点の入れ替え、3-optの順に 1 : 2,000 : 10,000 にしました。

また、下のグラフのように、スコアが激しく振動し続けるため、最良の解をコピーしておくとよいと思います。

スコアの推移

交差点の入れ替え

必須交差点以外の交差点をランダムに1つ削除します。削除した交差点を含む道路が縦と横に1本ずつあるので、それぞれの道路について、視界に入らなくなってしまった場合にランダムに1つだけ交差点を追加します。山登り法ですので、スコアが悪化した場合には元に戻すようにします。

3-opt

ランダムに3ヶ所を選び、最適な順序に入れ替えます。

例えば、ランダムに3ヶ所選んだ結果、A,B,C,Dの4つの範囲に分解されたとします。Xの逆順をX'と表記すると、次の8つのパターンが考えられます。

1	2	3	4
A	B	C	D
A	B	C'	D
A	B'	C	D
A	B'	C'	D
A	C	B	D
A	C	B'	D
A	C'	B	D
A	C'	B'	D

これらを全て試し、最もよかったものを採用します。

なお、2-optでもかなりの高スコアを出すことができるうえ、2-optのほうが実装が楽なため、時間が短いコンテストでは2-optを使用するのが現実的かもしれません。

Double-Bridge

ランダムに4ヶ所選んだ結果、A,B,C,D,Eの5つの範囲に分解されたとします。

の順に入れ替えます。

このような処理によって、局所解から脱出できる場合があるのだと思います。

提出コード

atcoder.jp 約500行です。実装には4時間以上の時間がかかりました。

最後に

かなり頑張ったつもりなのですが、コンテスト1位のc7c7さんのスコアを上回ることができませんでした。c7c7さん強すぎ！

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

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();
}

最後に

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

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

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