問題

【SRM691 Div1Medium : Moneymanager】

$N$ 個のタスクがある。各タスクには数値 $ a_{i}, b_{i} $が決められている。
$i$番目のタスクを完了すると以下のことが順番に起こる。

- 経験値(以下、EXPと表記)が $ a_{i} $ 増える。
- お金を $ b_{i} \times EXP $ 円もらえる。

ただし、同じタスクは一度しかできないものとする。
また、タスクをちょうど N/2 個完了したとき、合宿に参加する。
合宿ではお金はもらえないがEXPが X 増える。
タスクをこなす順番をうまく選んだときの、もらえるお金の最大値を答えよ。

$1 \leq N \leq 50 $、 ${N}$ は偶数
$1 \leq a_{i} \leq 10^5 $
$1 \leq b_{i} \leq 10 $
$0 \leq X \leq 10^5 $

タスクの順番

まず、合宿を無視するとき、タスクをこなす順番は貪欲に決定できることを確かめておこう。タスクが 2つ残っており、溜まっているEXPを$E$、残りのタスク番号を 0番、1番とする。それぞれを先にこなした場合にもらえるお金を計算しておこう。

0 -> 1の順

タスク0番をクリア : $ (E+a_0) b_0 $
タスク1番をクリア : $ (E+a_0 + a_1) b_1 $
合計 : $ M_{a} = E(b_0 + b_1) + a_0 (b_0 + b_1) + a_1 b_1 $

1 -> 0の順

タスク1番をクリア : $ (E+a_1) b_1 $
タスク0番をクリア : $ (E+a_0 + a_1) b_0 $
合計 : $ M_{b} = E(b_0 + b_1) + a_1 (b_0 + b_1) + a_0 b_0 $

両者の差をとると、

$ M_a - M_b = a_0 b_1 - a_1 b_0 $

となる。これは今までもらえた経験値に関係ない。したがって、ソート順にタスクをこなせばお金を最大化できる。合宿が途中に挟まる場合はこの順番でも最適ではないケースがあるが、合宿前後にこなすタスクの集合さえ決めてしまえば、それぞれは上式でソートしてよい事がわかる。

合宿の前後に振り分ける

さて、タスクをこなすべき順番が決まったので、これらを合宿前後に振り分けることを考えよう。すぐに思いつくのは、合宿前に配ったタスクの数と、もらった経験値を状態にした次のDP(☆)だろう。

☆ dp[(タスク番号)][(合宿前のタスクの数)][(合宿前の経験値の合計)] := 今までもらえたお金の最大値

- 遷移1: i 番目のタスクを合宿前にこなす
→ dp[i+1][j+1][e+a[i]] = max(dp[i+1][j+1][e+a[i]], dp[i][j][e] + (e+a[i])*b[i])

- 遷移2: i 番目のタスクを合宿後にこなす
→ dp[i+1][j][e] = max(dp[i+1][j][e], dp[i][j][e] + ??? * b[i])
→ ??? はどうしよう…

だが、タスクを合宿後に配ったとき、そのときにもらえるべきお金は【合宿直前での経験値の合計】が分かっていないと計算できないことに気づく。また、そもそも経験値の合計が最大で 50 / 2 * 10⁵ になるから、考えるべき状態数が 10⁹ 程度となり、計算が間に合わない。別の方法を考える必要がある。

ここで制約を見ると、経験値にかかる倍率 ($b_i$) が増える経験値 ($a_i$) に比べ大幅に少ない。なんとか $b_i$ を状態に持った DP を考えられないだろうか。

答えに移る前に、以下の図を見てほしい。縦軸は経験値で、オレンジで囲った部分がもらえるお金になる。*1

f:id:hama_DU:20170103200959p:plain

☆型のDPでは、お金を上図のようにタスクごとで縦に合計していた。逆に、以下の図のように横に足していくことはできないだろうか。

f:id:hama_DU:20170103202450p:plain

合宿までの $b_i$ の合計 (=Y) さえ決め打ちしておけば、どうやらできそうである。次の形のDPが考えられる。

★ dp[(タスク番号)][(合宿前のタスクの数)][(合宿前のbの合計)] := お金の最大値

- 遷移1: i 番目のタスクを合宿前にこなす
→ dp[i+1][j+1][e+b[i]] = max(dp[i+1][j+1][e+b[i]], dp[i][j][e] + (Y-e)*a[i])

- 遷移2: i 番目のタスクを合宿後にこなす
→ dp[i+1][j][e] = max(dp[i+1][j][e], dp[i][j][e] + (Y'-e')*a[i] + X*b[i])
ただし、e' := (合宿後に振り分けた b の合計) = (i 番目までの b の合計) - e

状態数は最大で 50 * 25 * 250 ≒ 3*10⁵ 程度、DPでの遷移は $O(1)$。 Y の種類数は高々 250*2 だから、これを最大で 250 回繰り返す。 8 * 10⁷ 回程度の計算となり、ギリギリだが許容範囲内だろう。