概要

商品数 \(M\) が最大 \(14\) と小さいことを利用し、売れた商品の集合をビットマスクで管理する DP を行います。
ただし来場者数 \(N\) は大きいので、各商品について「利益が大きい上位 \(M\) 人」だけを候補に絞るのがポイントです。

考察

商品 \(j\) を来場者 \(i\) に売ったときの利益は

\(V_{i,j} - C_j\)

です。利益が負になる取引はできず、利益 \(0\) の取引もしてもしなくても合計利益は変わらないため、実装では利益が正のものだけを考えます。

---

素朴な DP は間に合わない

商品数 \(M\) が小さいので、売れた商品の集合をビットマスクで表す DP を考えたくなります。

例えば、

\(dp[mask] =\) すでに売った商品の集合が \(mask\) のときの最大利益

として、来場者を \(1\) 人ずつ処理するとします。

この場合、各来場者について各商品を試すので、計算量はおよそ

\(O(N \times M \times 2^M)\)

になります。

しかし、最大で

\(N = 10^5,\ M = 14\)

なので、

\(10^5 \times 14 \times 2^{14}\)

となり、これは大きすぎます。

---

各商品について上位 \(M\) 人だけ見ればよい

重要な観察は次です。

各商品 \(j\) について、利益が大きい上位 \(M\) 人だけを候補に残せば十分です。

なぜなら、売れる商品数は最大でも \(M\) 個なので、最適解で商品を買う来場者も最大 \(M\) 人です。

例えば、ある商品 \(j\) が「上位 \(M\) 人に入っていない来場者 \(i\)」に売られていたとします。

商品 \(j\) に対する利益が大きい上位 \(M\) 人を考えます。
来場者 \(i\) はその中にいません。

最適解全体で使われている来場者は高々 \(M\) 人です。
もし上位 \(M\) 人全員がすでに何かを買っているなら、それに加えて来場者 \(i\) も商品 \(j\) を買っていることになり、合計 \(M+1\) 人が使われてしまいます。これは不可能です。

したがって、上位 \(M\) 人の中に「まだ何も買っていない人」が必ずいます。
その人に商品 \(j\) を売り先変更しても、商品 \(j\) の利益は下がりません。

よって、各商品について利益上位 \(M\) 人だけを残しても、最適解の値は変わりません。

---

これにより、候補となる来場者数は最大でも

\(M \times M = M^2\)

人になります。

\(M \leq 14\) なので、最大でも \(196\) 人です。
この人数なら、ビット DP が十分間に合います。

アルゴリズム

1. 各商品ごとに利益が正の来場者を集める

商品 \(j\) について、来場者 \(i\) に売ったときの利益

\(p = V_{i,j} - C_j\)

を計算します。

\(p > 0\) の場合だけ、商品 \(j\) の候補リストに \((p, i)\) を追加します。

---

2. 各商品について利益上位 \(M\) 人だけ残す

商品 \(j\) ごとに候補リストを利益の大きい順に並べ、上位 \(M\) 人だけ残します。

このとき残った来場者を全体の候補集合に追加します。
同じ来場者が複数の商品で候補になることもあるので、来場者ごとに各商品の利益を配列で持ちます。

---

3. 候補来場者に対してビット DP

候補来場者を順番に処理します。

\(dp[mask] =\) これまで処理した来場者だけを使い、売れた商品の集合が \(mask\) のときの最大利益

とします。

\(mask\) は \(M\) ビットの整数で、\(j\) ビット目が \(1\) なら商品 \(j\) はすでに売れています。

各来場者について、選択肢は次のいずれかです。

• 何も買わない
• まだ売れていない商品 \(j\) を 1 つ買う

遷移は次のようになります。

商品 \(j\) の利益を \(w\) とすると、

\(dp[mask \cup \{j\}] = \max(dp[mask \cup \{j\}], dp[mask] + w)\)

ただし、\(mask\) に商品 \(j\) が含まれていない場合だけです。

最後に、すべての商品を売る必要はないので、

\(\max dp[mask]\)

が答えです。

計算量

各商品 \(j\) について、利益が正の候補数を \(L_j\) とします。

• 時間計算量: \(O(NM + \sum_j L_j \log L_j + M^3 2^M)\)
  • 入力を見て利益を計算する部分が \(O(NM)\)
  • 各商品の候補をソートする部分が \(O(\sum_j L_j \log L_j)\)
  • 候補来場者数は最大 \(M^2\) 人で、DP が \(O(M^3 2^M)\)
• 空間計算量: \(O(NM + M2^M + M^3)\)

制約では \(NM \leq 2 \times 10^5\)、\(M \leq 14\) なので十分高速です。

実装のポイント

• 利益が \(0\) 以下の取引は答えを改善しないため、候補に入れません。

• DP 更新では、同じ来場者が複数の商品を買わないようにする必要があります。

  • そのため、現在の dp を old として参照し、更新先はコピーした new にします。
  • 直接 dp を上書きすると、1 人の来場者が複数の商品を買ったことになってしまう可能性があります。

• 答えは dp[(1 << M) - 1] ではなく max(dp) です。

  • すべての商品を売る必要はないためです。

• masks_without[j] として、商品 \(j\) がまだ売れていない mask の一覧を事前計算しておくと、遷移時のビット判定を省けます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0
    N = data[idx]
    M = data[idx + 1]
    idx += 2

    C = data[idx:idx + M]
    idx += M

    profits_by_item = [[] for _ in range(M)]

    for i in range(N):
        for j in range(M):
            p = data[idx] - C[j]
            if p > 0:
                profits_by_item[j].append((p, i))
            idx += 1

    cand = {}

    for j in range(M):
        lst = profits_by_item[j]
        if len(lst) > M:
            lst.sort(reverse=True)
            lst = lst[:M]

        for p, i in lst:
            if i not in cand:
                cand[i] = [0] * M
            cand[i][j] = p

    if not cand:
        print(0)
        return

    size = 1 << M
    masks_without = []
    for j in range(M):
        b = 1 << j
        masks_without.append([mask for mask in range(size) if (mask & b) == 0])

    visitor_edges = []
    for arr in cand.values():
        edges = []
        for j, w in enumerate(arr):
            if w:
                edges.append((j, 1 << j, w))
        visitor_edges.append(edges)

    dp = [0] * size

    for edges in visitor_edges:
        old = dp
        new = old.copy()

        for j, b, w in edges:
            mw = masks_without[j]
            for mask in mw:
                v = old[mask] + w
                to = mask + b
                if v > new[to]:
                    new[to] = v

        dp = new

    print(max(dp))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。