概要

各来場者は最大 \(1\) 個、各商品は最大 \(1\) 人に売れるという条件のもとで、利益 \(V_{i,j}-C_j\) の合計を最大化する問題です。これは「重み付き二部マッチングの最大化」に相当し、商品数 \(M \leq 14\) が小さいことを利用したビットマスク DP で解きます。

考察

利益の定義

商品 \(j\) を来場者 \(i\) に売ったときの利益は \(w_{i,j} = V_{i,j} - C_j\) です。利益が負になる取引は行わないので、実際に売却対象となるのは \(w_{i,j} > 0\) のペアだけです。

素朴なアプローチと問題点

「どの商品がすでに売れたか」を \(M\) ビットの集合 mask で表し、来場者を \(1\) 人ずつ処理する DP を考えます。

• \(dp[\text{mask}]\) = これまで処理した来場者の中で、mask が表す商品集合を売ったときの利益の最大値

各来場者について「何も買わない」か「まだ売れていない商品 \(j\) を \(1\) つ買う」を選びます。

しかし来場者数は \(N \leq 10^5\) と多く、全来場者について DP を回すと \(O(N \cdot 2^M \cdot M)\) となり、\(10^5 \times 16384 \times 14 \approx 2.3\times10^{10}\) で TLE します。

重要な観察：候補となる来場者は少ししかいない

最適解で実際に商品を購入する来場者は高々 \(M\) 人（商品が \(M\) 個しかないため）です。ここから、次のことが言えます。

各商品 \(j\) について、利益 \(w_{i,j}\) が大きい上位 \(M\) 人だけを候補にすれば、その中に必ず最適解が含まれる。

理由（交換論法）: ある最適解で、来場者 \(i\) が商品 \(j\) に割り当てられているが \(i\) が商品 \(j\) の上位 \(M\) 人に入っていないとします。すると商品 \(j\) に対して \(w_{i,j}\) 以上の利益を持つ来場者が少なくとも \(M\) 人います。一方、最適解で商品を買っている来場者は（\(i\) を除いて）高々 \(M-1\) 人なので、その上位 \(M\) 人の中に「誰にも割り当てられていない人」が最低 \(1\) 人いるはずです。その人を \(i\) の代わりに商品 \(j\) に割り当てても利益は減りません。この置き換えを繰り返せば、上位 \(M\) 人の候補だけを使った最適解が構成できます。

したがって、候補となる来場者は高々 \(M \times M = M^2 \leq 196\) 人に絞れます。

アルゴリズム

1. 候補の選出 各商品 \(j\) について、\(w_{i,j} = V_{i,j} - C_j > 0\) となる来場者のうち、利益上位 \(M\) 人を選ぶ。サイズ \(M\) の最小ヒープを使い、上位 \(M\) 人を効率よく管理する（新しい値がヒープ最小値より大きければ入れ替える）。選ばれた来場者を集合 candidates にまとめる。

2. ビットマスク DP \(dp[\text{mask}]\) を「売れた商品の集合が mask のときの最大利益」とする。候補の来場者を \(1\) 人ずつ処理し、各 mask について

   • その来場者を使わない（\(dp[\text{mask}]\) をそのまま維持）
   • まだ売れていない商品 \(j\) に割り当てる（\(dp[\text{mask} \mid (1{\ll}j)] \leftarrow dp[\text{mask}] + w_{i,j}\)）

来場者を重複して使わないよう、tmp = dp[:] にコピーしてから更新します（\(1\) 人の来場者が同じ処理で複数商品に割り当てられないようにするため）。

1. 最終的に \(dp\) の最大値が答え。すべての商品を売らない選択も含むため、初期値 \(0\) の \(dp[0]\) から自然に「利益 \(0\)」も候補になります。

計算量

候補数を \(K \leq M^2\) とします。

• 時間計算量: 候補選出に \(O(N M \log M)\)、DP に \(O(K \cdot 2^M \cdot M) = O(M^3 \cdot 2^M)\)。\(M=14\) で約 \(4.5\times10^7\) 程度で十分高速。
• 空間計算量: DP テーブルに \(O(2^M)\)。

実装のポイント

• 候補選出のヒープ: heapq は最小ヒープなので、サイズが \(M\) 未満なら heappush、それ以上なら「最小値より大きい場合のみ」heapreplace することで上位 \(M\) 件を保持できます。

• DP のコピー更新: tmp = dp[:] を用意し、tmp へ書き込むことで、同じ来場者が同一処理内で複数の商品へ割り当てられる誤りを防ぎます。

• 正の利益のみ扱う: \(w \leq 0\) のペアは無視することで、無駄な遷移を避けられます。

• 入力の高速化: \(N \times M \leq 2\times10^5\) の入力を sys.stdin.buffer.read() で一括読み込みすると安全です。

  ソースコード

import sys
import heapq

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    C = [int(data[idx + j]) for j in range(M)]
    idx += M
    V = [int(x) for x in data[idx:idx + N * M]]

    # 各商品について重みw=V-C>0の上位M人の来場者を候補に選ぶ
    candidates = set()
    for j in range(M):
        cj = C[j]
        h = []
        base = j
        for i in range(N):
            w = V[i * M + j] - cj
            if w > 0:
                if len(h) < M:
                    heapq.heappush(h, (w, i))
                elif w > h[0][0]:
                    heapq.heapreplace(h, (w, i))
        for w, i in h:
            candidates.add(i)

    full = 1 << M
    dp = [0] * full

    for i in candidates:
        base = i * M
        pairs = []
        for j in range(M):
            w = V[base + j] - C[j]
            if w > 0:
                pairs.append((j, w))
        if not pairs:
            continue
        tmp = dp[:]
        for mask in range(full):
            cur = dp[mask]
            for j, w in pairs:
                if not (mask >> j) & 1:
                    nm = mask | (1 << j)
                    val = cur + w
                    if val > tmp[nm]:
                        tmp[nm] = val
        dp = tmp

    print(max(dp))

main()

---

この解説は claude4.8opus-high によって生成されました。