概要

\(N\) 人の来場者と \(M\) 個の商品があり、各来場者に最大1つ、各商品を最大1人に売るときの利益の合計の最大値を求める問題です。

考察

この問題では、商品の個数 \(M\) が最大 \(14\) と小さいため、ビットDP（状態をビット列で表現する動的計画法）を用いることができます。

まず、\(N\) が最大 \(10^5\) と大きい点に注目します。もしすべての来場者とすべての商品のペアについてDPの更新を行うと、計算量が \(O(N \cdot M \cdot 2^M)\) となり、実行時間制限に間に合いません。 しかし、商品は全部で \(M\) 個しかなく、1つの商品を買う来場者は高々1人です。つまり、1つの商品に対して実際に売却相手として選ばれるのは高々 \(M\) 人だけです。したがって、各商品について利益が大きい順に上位 \(M\) 人だけを候補として残せば十分であり、それ以外の来場者は無視してよいことがわかります。これにより、候補となる来場者と商品のペアの数は高々 \(M^2\) 個に減ります。

次に、1人の来場者は最大1つの商品しか買えないという条件を満たす必要があります。来場者ごとに候補商品をまとめ、その来場者がどれか1つの商品を選ぶ（あるいは何も買わない）という遷移をうまくDPに組み込む必要があります。

アルゴリズム

1. 候補の絞り込み: すべての来場者 \(i\) と商品 \(j\) について、利益 \(V_{i,j} - C_j \ge 0\) となるものを調べ、商品 \(j\) ごとに利益が大きい順にソートします。各商品 \(j\) について、利益が大きい上位 \(M\) 人を売却候補として抽出し、来場者ごとに候補商品のリストを作成します。

2. ビットDP: dp[mask] を、「商品の割り当て状況が mask（ビットが立っている商品はすでに売却済み）のときの最大利益」として定義します。 候補となった各来場者について、彼らが持つ候補商品のリストを用いてDPを更新します。このとき、1人の来場者が複数の商品を買わないようにするため、来場者ごとに next_dp = dp[:] のコピーを作成します。その来場者の持つ各候補商品 \(j\) について、mask に \(j\) 番目のビットを追加した遷移 dp[mask] + p -> next_dp[mask | (1 << j)] を計算します。候補商品の追加が終わったら dp = next_dp として更新します。これにより、1人の来場者からは最大1つの商品しか選ばれなくなります。

3. 最後に max(dp) を出力します。

計算量

• 時間計算量: \(O(N \cdot M \log N + M^2 \cdot 2^M)\) 候補のソートに \(O(N \cdot M \log N)\)、DP更新に候補人数（最大 \(M^2\) 人）と各人の候補数（最大 \(M\)）、状態数 \(2^M\) で \(O(M^2 \cdot M \cdot 2^M) = O(M^3 \cdot 2^M)\) ですが、実際は1人あたりの候補数を合計しても高々 \(M^2\) に抑えられるため \(O(N \cdot M \log N + M^2 \cdot 2^M)\) 程度で十分高速に動作します。
• 空間計算量: \(O(N \cdot M + 2^M)\)

実装のポイント

• 1人の来場者が複数商品を買わないようにするため、来場者ごとに next_dp を用意して更新するのが肝要です。これにより、商品の追加を1回のループ内で複数回行っても、元の dp 配列を参照することで同一人物による複数購入を防ぐことができます。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    
    # 各商品jに対する利益が正の来場者のリスト
    profits = [[] for _ in range(M)]
    for i in range(N):
        vals = list(map(int, input().split()))
        for j in range(M):
            v = vals[j]
            if v >= C[j]:
                p = v - C[j]
                profits[j].append((p, i))
                
    # 各商品について、利益が大きい順に上位M人を候補とする
    user_items = {}
    for j in range(M):
        profits[j].sort(reverse=True, key=lambda x: x[0])
        for p, i in profits[j][:M]:
            if i not in user_items:
                user_items[i] = []
            user_items[i].append((j, p))
            
    # dp[mask] = 選ばれた商品の集合がmaskであるときの最大利益
    dp = [0] * (1 << M)
    
    # 候補となった来場者それぞれについてDPを更新
    for items in user_items.values():
        next_dp = dp[:]
        for j, p in items:
            bit = 1 << j
            for mask in range(1 << M):
                if mask & bit:
                    continue
                nxt = mask | bit
                v = dp[mask] + p
                if v > next_dp[nxt]:
                    next_dp[nxt] = v
        dp = next_dp
        
    print(max(dp))

if __name__ == '__main__':
    solve()

---

この解説は or-glm5.2-high によって生成されました。