概要

フリーマーケットにおいて、来場者と商品を適切にペアリングし、全体の利益を最大化する問題です。この問題は、グラフ理論における「最大重み二部マッチング問題」に帰着でき、最小費用流アルゴリズムを用いて効率的に解くことができます。

考察

1. 問題の整理

各来場者は最大1つの商品を購入でき、各商品は最大1人の来場者に売ることができます。 商品 \(j\) を来場者 \(i\) に売ったときの利益は \(P_{i, j} = V_{i, j} - C_j\) 円です。利益が負になる取引は行わないため、 \(P_{i, j} \geq 0\) となるペアのみを考慮します。

これは、来場者の集合と商品の集合の間で、利益の合計が最大になるようにペア（マッチング）を作る最大重み二部マッチング問題です。

2. 単純な最大マッチングとの違い

「できるだけ多くのペアを作る（最大マッチング）」を求めればよいわけではありません。なぜなら、無理に取引数を増やすと、利益の低い取引を含めることになり、全体の利益が減ってしまう可能性があるからです。

例えば、以下のようなケースを考えます。 - 取引A：利益 \(100\) 円 - 取引B：利益 \(10\) 円（ただし、取引Aと同時に行うことはできない）

この場合、取引数を2にするために無理な組み合わせを選ぶより、取引数を1にして取引Aのみを行う方が全体の利益は大きくなります。 したがって、「取引の数（流量）を \(f\) としたときの最大利益」をすべての \(f\) について考え、その中で最も利益が大きくなるものを選ぶ必要があります。

3. 最小費用流への帰着

「最大化」の問題を「最小化」の問題（最小費用流）に変換します。 最小費用流アルゴリズム（特にDijkstra法を用いるもの）では、辺の費用が非負である必要があります。しかし、利益 \(P_{i, j}\) をそのまま負の費用（ \(-P_{i, j}\) ）にすると、負の辺が発生してしまいます。

そこで、十分大きな定数 \(U = 10^9\) （利益の最大値以上）を導入し、利益 \(P_{i, j}\) を費用 \(W_{i, j} = U - P_{i, j}\) に変換します。 \(P_{i, j} \geq 0\) であるため、変換後の費用 \(W_{i, j}\) は必ず非負（ \(0 \leq W_{i, j} \leq U\) ）になり、最小費用流アルゴリズムが適用可能になります。

取引数を \(f\) としたとき、 - 変換後の総費用： \(\sum (U - P_{i, j}) = f \times U - \sum P_{i, j}\) - 実際の総利益： \(\sum P_{i, j} = f \times U - (\text{変換後の総費用})\)

となります。つまり、取引数 \(f\) における最小費用 \(c\) を求めれば、そのときの最大利益は \(f \times U - c\) と計算できます。

4. 取引数 \(f\) の決定

商品の数 \(M \leq 14\) と非常に少ないため、最大取引数（最大流量）は高々 \(14\) です。 ACL（AtCoder Library）の slope 関数を使用すると、流量 \(f\) を \(0\) から最大流量まで変化させたときの、それぞれの最小費用 \(c\) を折れ線グラフの形で一挙に取得できます。 得られたすべての \((f, c)\) のペアに対して \(f \times U - c\) を計算し、その最大値が答えとなります。

アルゴリズム

1. ネットワークの構築

   • 超源点 \(S\)、超終点 \(T\) を用意します。
   • 各来場者 \(i\) に対して、 \(S \to i\) に容量 \(1\)、費用 \(0\) の辺を張ります。
   • 各商品 \(j\) に対して、 \((N+j) \to T\) に容量 \(1\)、費用 \(0\) の辺を張ります。
   • \(V_{i, j} \geq C_j\) を満たすペア \((i, j)\) に対して、 \(i \to (N+j)\) に容量 \(1\)、費用 \(U - (V_{i, j} - C_j)\) の辺を張ります。

2. 最小費用流の実行

   • ACL の mcf_graph を用いて、 \(S\) から \(T\) への slope を取得します。

3. 最大利益の計算

   • slope で得られた各（流量 \(f\), 費用 \(c\)）のペアについて、実際の利益 \(f \times U - c\) を計算し、その最大値を求めます。

計算量

• 時間計算量: \(O(F \cdot E \log V)\)

  • 頂点数 \(V = N + M + 2 \approx 10^5\)
  • 辺の数 \(E \leq N + M + N \times M \approx 2 \times 10^5\)
  • 最大流量 \(F \leq M \leq 14\)
  • Successive Shortest Path アルゴリズムにより、最大 \(F\) 回の最短路探索（Dijkstra法）を行います。 \(F \le 14\) と非常に小さいため、実行時間制限に対して十分高速に動作します。

• 空間計算量: \(O(V + E)\)

  • グラフの頂点と辺を保持するためのメモリであり、十分に制限内に収まります。

実装のポイント

• オフセット \(U\) の大きさ: \(V_{i, j} - C_j\) の最大値は \(10^9\) なので、 \(U = 10^9\) とすれば費用が負になることを防げます。

• オーバーフローの防止: 費用や利益の計算では、最大で \(14 \times 10^9\) 程度の値になるため、long long 型（64ビット整数）を使用する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/mincostflow>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> C(M);
    for (int j = 0; j < M; ++j) {
        cin >> C[j];
    }

    vector<vector<long long>> V(N, vector<long long>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> V[i][j];
        }
    }

    // グラフの構築
    // 超源点 S = 0
    // 来場者 i = 1 から N
    // 商品 j = N + 1 から N + M
    // 超終点 T = N + M + 1
    int S = 0;
    int T = N + M + 1;
    atcoder::mcf_graph<int, long long> g(N + M + 2);

    for (int i = 1; i <= N; ++i) {
        g.add_edge(S, i, 1, 0);
    }

    // 費用を非負にするためのオフセット U
    // 利益 P = V[i][j] - C[j] の最大値は 10^9 なので、U = 10^9 とすれば
    // 費用 U - P は常に非負となる。
    long long U = 1000000000LL;

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (V[i-1][j-1] >= C[j-1]) {
                long long P = V[i-1][j-1] - C[j-1];
                g.add_edge(i, N + j, 1, U - P);
            }
        }
    }

    for (int j = 1; j <= M; ++j) {
        g.add_edge(N + j, T, 1, 0);
    }

    // 最小費用流の slope を取得
    auto result = g.slope(S, T);

    long long max_profit = 0;
    for (auto [f, c] : result) {
        // 流量 f、費用 c のときの実際の利益
        long long profit = (long long)f * U - c;
        max_profit = max(max_profit, profit);
    }

    cout << max_profit << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。