Codeforces Round #490 (Div. 3) F. Cards and Joy

お題箱より。

Problem - F - Codeforces

問題概要

$n$ 人のプレイヤーに $k$ 枚ずつのカードを配る。 $nk$ 枚のカードそれぞれにかかれている数字 $c_{1}, ..., c_{nk}$ と、プレイヤー $j$ が好きな数字 $f_{j}$ が与えられる。

それぞれのプレイヤーは、配られたカードのうち好きな数字が書かれたものが $i$ 枚存在すると $h_{i}$ の幸福度を得る。1枚も存在しない場合の幸福度は $0$ である。

全プレイヤーの幸福度の総和の最大値を求めよ。

制約

$1 \le n \le 500$
$1 \le k \le 10$
$1 \le c_{i} \le 10^{5}$
$1 \le f_{i} \le 10^{5}$
$1 \le h_{1} \lt \cdots \lt h_{k} \le 10^{5}$

解法

各プレイヤーには、その人が好きなカードだけを $k$ 枚以下配ると考えてしまって良いです。その操作によって配られなかったカードを適当に配分することで、幸福度を変えずに「各プレイヤーちょうど $k$ 枚」にできるからです。

同じ数字が好きな人ごとに分けて考えましょう。そうすると各数字について、「プレイヤー $x$ 人に、その人達が好きなカードを合計 $y$ 枚以下配るときの最大幸福度はいくつになるか？」という問題を解けば良いです。これを各数字について別々に計算するのではなく、取り得る $(x, y)$ の組み合わせ全てについて最大幸福度を前計算してしまうという方針を取ります。

各値の取り得る範囲を制約から確認しておくと、 $x$ は人数なので $x \le n \le 500$ 、 $y$ はカードの枚数なので $y \le nk \le 5000$ です。この全ての $(x, y)$ の組み合わせについて最大幸福度を求めるために、以下のDPを組みます。

$dp\lbrack x\rbrack\lbrack y\rbrack =$ プレイヤー $x$ 人に合計 $y$ 枚以下のカードを配る時の最大幸福度

$y$ 枚「以下」とするためには、余らせる分を最初に消化するつもりで初期条件を $dp\lbrack 0\rbrack\lbrack 0\rbrack = \cdots = dp\lbrack 0\rbrack\lbrack nk\rbrack = 0$ とします。（実際には $x$ についても $x$ 人「以下」と見なせるので、全ての $dp\lbrack x\rbrack\lbrack y\rbrack$ を $0$ で初期化しても良いです）

そして $dp\lbrack x\rbrack\lbrack y\rbrack$ からの遷移は、次のプレイヤーに配るカードの枚数を $j$ として、 $h_{j}$ を加算して $dp\lbrack x+1\rbrack\lbrack y+j\rbrack$ に遷移すれば良いです。ここでの $j$ は $0 \le j \le k$ の範囲を動きます。