ケーブルの総延長を最小化するコンピューターとソケットの接続方法を数えるC++プログラム

要素数Nの2つの配列AとBがあるとします。ここで、N台のコンピューターとN個のソケットが存在すると考えます。i番目のコンピューターの座標はA[i]、i番目のソケットの座標はB[i]であり、これら2N個の座標はすべて互いに異なるものとします。

目的は、ケーブルを使って各コンピューターを1つのソケットに接続することです。ただし、1つのソケットに接続できるコンピューターは最大1台までという制約があります。このとき、ケーブルの総延長が最小となる接続方法が何通り存在するかを数える必要があります。答えが非常に大きくなる場合は、10^9 + 7で割った余りを返してください。

例として、入力がA = [0, 10]、B = [20, 30]である場合を考えてみましょう。この場合の出力は2となります。最適な接続方法は「0を20へ、10を30へ接続する」パターンと「0を30へ、10を20へ接続する」パターンの2通りがあり、どちらの場合もケーブルの総延長が40になるためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

maxn := 200005
p := 10^9 + 7
整数型ペアの配列を1つ定義
n := Aのサイズ
i := 0 から初期化し、i < n の間、i を1ずつ増やしながら繰り返す:
    a[i].first := A[i]
    a[i].second := 1
i := n から初期化し、i < 2 * n の間、i を1ずつ増やしながら繰り返す:
    a[i].first := B[i - n]
    a[i].second := -1
配列aをソート
ways := 1, val := 0
i := 0 から初期化し、i < 2 * n の間、i を1ずつ増やしながら繰り返す:
    val * a[i].second < 0 の場合:
        ways := ways * |val|
    val := val + a[i].second
waysを返す

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、コンピューターの座標に+1、ソケットの座標に-1を対応させ、すべての座標をまとめて昇順にソートする点です。その後、座標軸上を左から右へ走査しながら累積値valを更新していきます。走査中にvalの符号が反転するタイミング、つまり未接続のコンピューターとソケットが対面する瞬間には|val|通りのマッチングの選択肢が生まれるため、その都度答えwaysに掛け合わせていきます。これにより、全ての組み合わせを列挙することなく、効率的に最適接続の総数を求められます。

実装例

理解をより深めるために、以下のC++による実装を見てみましょう。

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

int solve(vector<int> A, vector<int> B){
    long maxn = 200005;
    long p = 1000000007;
    pair<int, int> a[maxn];
    int n = A.size();
    for (int i = 0; i < n; i++){
        a[i].first = A[i];
        a[i].second = 1;
    }
    for (int i = n; i < 2 * n; i++){
        a[i].first = B[i - n];
        a[i].second = -1;
    }
    sort(a, a + 2 * n);
    long long ways = 1, val = 0;
    for (int i = 0; i < 2 * n; i++){
        if (val * a[i].second < 0){
            ways = ways * abs(val) % p;
        }
        val += a[i].second;
    }
    return ways;
}
int main(){
    vector<int> A = { 0, 10 };
    vector<int> B = { 20, 30 };
    cout << solve(A, B) << endl;
}

入力

{ 0, 10 }, { 20, 30 }

出力

2