読者です 読者をやめる 読者になる 読者になる

問題解決の宝石箱

競技プログラミング/数学ネタ置き場

SRM691 Div1Medium : Moneymanager

2016年 Topcoder ☆6

問題

SRM691 Div1Medium : Moneymanager

【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 * 105 になるから、考えるべき状態数が 109 程度となり、計算が間に合わない。別の方法を考える必要がある。

ここで制約を見ると、経験値にかかる倍率 ( {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*105 程度、DPでの遷移は  {O(1)}。 Y の種類数は高々 250*2 だから、これを最大で 250 回繰り返す。 8 * 107 回程度の計算となり、ギリギリだが許容範囲内だろう。

解答コード

SRM691 Div1Medium : Moneymanager

*1:N=6の例で、合宿前に振り分けたタスクを (a0,b0), (a1,b1), (a2,b2), 合宿後のタスクを (a0',b0'), (a1',b1'), (a2',b2') とおいた。これらは効率順にソート済とする。次の図も同様。

*2:実際は bi が1以上なのでこれより1割ほど少ない