ABC 383 F — Diversity

考察

同じ色の商品をまとめて処理すれば、「その色を初めて買う」ときだけボーナスを足せる。色の処理中は、その色をまだ買っていない状態と、すでに一つ以上買った状態を分けておく。

商品 ii の価格を PiP_i、効用を UiU_i、色を CiC_i、予算を XX、一色あたりのボーナスを KK とする。効用の和だけなら、価格を軸とする0/1ナップサックDPが使える。しかし、各商品の効用を Ui+KU_i+K としてしまうと、同じ色を二つ買っただけでボーナスを二回加えてしまう。

例えば、同色の二商品が価格・効用 (1,2),(1,3)(1,2),(1,3)、予算が X=2X=2、ボーナスが K=10K=10 なら、両方買った満足度は 2+3+10=152+3+10=15 である。二商品の色が異なれば 2+3+2×10=252+3+2\times10=25、何も買わなければ0となる。必要なのは、商品を追加する際に「この色のボーナスをすでに加えたか」を判別することだ。

入力順のままでは、以前買った色の集合を覚えたくなる。だが、購入する集合が同じなら、商品を見る順序で満足度は変わらない。色ごとにまとめて処理すれば、処理を終えた色は二度と現れず、今の色を買ったかだけを一時的に覚えればよい。

価格の添字 pp は 0≤p≤X0\leq p\leq X とする。dp[p] を、処理済みの色だけで合計価格ちょうど pp の商品を買ったときの満足度の最大値と定義する。最初は dp[0]=0、それ以外は到達不能を表す −∞-\infty とする。

次の色 cc を処理するときは、これまでの dp を prev として固定し、別の配列 cur をすべて −∞-\infty で始める。

  • prev[p]: 色 cc を一つも買わず、それ以前の色だけで価格ちょうど pp を使った最大値。色 cc の処理中は書き換えない。
  • cur[p]: それ以前の色と、色 cc のうちここまで見た商品から選び、色 cc を一つ以上買って価格ちょうど pp を使った最大値。色 cc のボーナスはすでに一回含む。

色 cc の商品 jj を一つずつ見る。各商品について、p=X,X−1,…,Pjp=X,X-1,\ldots,P_j の降順で価格を走査し、次の三候補の最大値で cur[p] を上書きする。

  • 商品 jj を買わない: 現在の cur[p]。
  • 色 cc の初購入: prev[p−Pj]+Uj+Kprev[p-P_j]+U_j+K。
  • 同色の追加購入: cur[p−Pj]+Ujcur[p-P_j]+U_j。

初購入だけにボーナスを加え、追加購入では効用だけを加える。遷移元が −∞-\infty の候補は使わない。

価格が正なので p−Pj<pp-P_j<p。降順なら、参照する cur[p-P_j] はまだ商品 jj で更新されておらず、同じ商品を二度使わない。昇順にすると、今の商品を買って作った状態から再び同じ商品を買えてしまう。

上の同色二商品の例では、初めは prev=(0,−∞,−∞)、cur=(−∞,−∞,−∞) である。一商品目の後は cur[1]=12。二商品目では、先に cur[2]=12+3=15 を作り、その後で cur[1]=13 に更新する。追加購入ではボーナスを加えず、二商品目自身も再利用していない。

その色の全商品を処理し終えたら、各 pp について次のように合流する。

dp[p]=max⁡(prev[p],cur[p])dp[p]=\max(prev[p],cur[p])

ここで初めて「色 cc を買わない」選択を混ぜる。商品処理中の cur へ prev をコピーすると、cur が「現色を一つ以上買った」という意味を失うので、ここで説明する方式ではコピーしない。

すべての色を処理した後、答えは max⁡0≤p≤Xdp[p]\max_{0\leq p\leq X}dp[p] である。予算は使い切る必要がないので dp[X] だけを見てはいけない。dp[0]=0 は合流のたびに残り、何も買わない選択も含まれる。

典型の発動条件

grouped knapsack

グループを一度でも選ぶとボーナスや費用が発生し、それ以降は各要素の寄与だけが加わるときに使う。グループ内で複数の要素を選べる場合も、未選択の層と一つ以上選択した層を分ければ、初回だけの効果を表せる。不選択の合流はグループを処理し終えてから行う。

0/1 knapsackの降順更新

各商品を高々一度選ぶ価格DPを同じ配列で更新するときに使う。価格が正なら、大きい価格から更新することで、遷移元を「今の商品をまだ使っていない値」に保てる。

問題固有の要素

色のボーナスは、その色の商品を一つ以上買ったかだけで決まる。色を連続して処理できるため、使用済みの全色の集合を状態に持つ必要はない。処理済みの色の寄与は満足度へ織り込み、処理中の一色についてだけ未購入・購入済みを区別する。

商品を見る順序を選び直せるなら、履歴のどの部分を処理済みとして忘れられるかに注目したい。

正当性

ある色の処理前に、prev[p] が、それ以前の色だけから価格ちょうど pp で選ぶ満足度の最大値を表すと仮定する。その色の商品を一つも見ていない時点では、現色を一つ以上買った選択は存在しないので、cur をすべて −∞-\infty にするのが正しい。

商品 jj を見た後の、現色を一つ以上買う任意の選択を考える。商品 jj を含まなければ、更新前の cur[p] に含まれる。含むなら、商品 jj を取り除いた選択が現色を含むかで二分できる。含まなければ prev[p-P_j] から効用と初回ボーナスを加え、含むなら更新前の cur[p-P_j] から効用だけを加える。この三通りで全選択を覆い、どの遷移もボーナスを各使用色に一回だけ加える。降順更新により商品 jj を二度使わないので、更新後も cur の定義が保たれる。

色を買わない選択は prev、一つ以上買う選択は処理後の cur がすべて覆う。その最大を取れば、その色まで処理した dp の定義が成立する。初期状態は空集合だけで定義を満たすため、この議論を全色へ繰り返せる。最後に価格0から XX までの最大を取ると、空集合を含む予算内の全選択の最大満足度が得られる。

実装上の注意

  • 色番号は 1≤Ci≤N1\leq C_i\leq N なので、色ごとの商品リストへ直接振り分けられる。商品がない色は飛ばしてよい。
  • prev は一色の処理中ずっと固定し、cur は色が変わるたびに全要素を −∞-\infty へ戻す。配列は色ごとに全履歴を保存せず、二本を使い回せる。
  • 到達不能の番兵から加算する候補は除外する。満足度は最大でも N×109+N×109≤1012N\times10^9+N\times10^9\leq10^{12} なので、符号付き64 bit整数で保持する。
  • cur[0] は到達不能のまま、色終了後の dp[0] は0のままである。未購入の0を cur に入れず、prev 側で保つ。

復習の核

  • 「初めて選んだときだけ加点」なら、要素をグループごとに処理し、未選択と選択済みを分ける。
  • 各配列が許す選択を言葉にする。「一つ以上選ぶ」配列へ空集合を混ぜると、不変条件が変わる。
  • 降順更新は、今の商品を遷移元に混ぜないために行う。「価格ちょうど」で持ったDPから「予算以下」の答えを取る範囲も確認する。

計算量と制約

時間

商品を色別リストに振り分けるのに O(N)O(N)。各商品の降順更新は O(X)O(X) で、全商品では O(NX)O(NX)。色ごとの配列初期化と不購入の合流も、一色につき O(X)O(X)、色数は高々 NN なので合計 O(NX)O(NX)。答えの取り出しの O(X)O(X) を含め、全体で O(NX)O(NX) 時間。

空間

価格 0,…,X0,\ldots,X に対する prev と cur の二本を使い回すので、DPの作業領域は O(X)O(X)。色別の商品保持に O(N)O(N) を使い、合計 O(N+X)O(N+X) 空間。

制約との対応

1≤N≤5001\leq N\leq500、1≤X≤500001\leq X\leq50000 なので、商品ごとの価格走査は高々 NX=2.5×107NX=2.5\times10^7 回である。1≤Pi≤X1\leq P_i\leq X より、降順更新の参照先は必ず小さい価格になる。1≤Ui,K≤1091\leq U_i,K\leq10^9 なので満足度には64 bit整数が必要となる。色番号の範囲 1≤Ci≤N1\leq C_i\leq N を使えば、整列なしでグループ分けできる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Diversity の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 資源軸knapsack DP

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: 資源・容量DP

      • 資源軸の上限と更新順を選び、選択の重複を避けられる。

      先に読む単元:

      この解説で扱わないこと:

      • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題