ABC018-D バレンタインデー

ABC018-D バレンタインデー

概要

https://atcoder.jp/contests/abc018/tasks/abc018_4

N(<=18)人の男、M(<=18)人の女からそれぞれP、Q人選ぶ。

得点についての条件が、以下のような内容でR(<=N*M)個与えられる。

・男xと女yを含む選び方のとき、z(<=10000)点が得られる。

合計点を最大化せよ。

解法

　まず、男をP人選んだものとして考える。

このとき、各女を選んだときの得点がO(R)で求められる。

よって、男の選び方1つに対してO(R + MlogM)で得点が最大化できる。

　また、男の選び方は2^18通りを全探索することでP人選ぶパターンを網羅でき、26万通りの探索で最大 18P9 = 約45000通り が得られる。

　男のすべての選び方について得点を計算すると解が得られる。

https://atcoder.jp/contests/abc018/submissions/20169029