考察
同じ色の商品をまとめて処理すれば、「その色を初めて買う」ときだけボーナスを足せる。色の処理中は、その色をまだ買っていない状態と、すでに一つ以上買った状態を分けておく。
商品 の価格を 、効用を 、色を 、予算を 、一色あたりのボーナスを とする。効用の和だけなら、価格を軸とする0/1ナップサックDPが使える。しかし、各商品の効用を としてしまうと、同じ色を二つ買っただけでボーナスを二回加えてしまう。
例えば、同色の二商品が価格・効用 、予算が 、ボーナスが なら、両方買った満足度は である。二商品の色が異なれば 、何も買わなければ0となる。必要なのは、商品を追加する際に「この色のボーナスをすでに加えたか」を判別することだ。
入力順のままでは、以前買った色の集合を覚えたくなる。だが、購入する集合が同じなら、商品を見る順序で満足度は変わらない。色ごとにまとめて処理すれば、処理を終えた色は二度と現れず、今の色を買ったかだけを一時的に覚えればよい。
価格の添字 は とする。dp[p] を、処理済みの色だけで合計価格ちょうど の商品を買ったときの満足度の最大値と定義する。最初は dp[0]=0、それ以外は到達不能を表す とする。
次の色 を処理するときは、これまでの dp を prev として固定し、別の配列 cur をすべて で始める。
prev[p]: 色 を一つも買わず、それ以前の色だけで価格ちょうど を使った最大値。色 の処理中は書き換えない。
cur[p]: それ以前の色と、色 のうちここまで見た商品から選び、色 を一つ以上買って価格ちょうど を使った最大値。色 のボーナスはすでに一回含む。
色 の商品 を一つずつ見る。各商品について、 の降順で価格を走査し、次の三候補の最大値で cur[p] を上書きする。
- 商品 を買わない: 現在の
cur[p]。
- 色 の初購入: 。
- 同色の追加購入: 。
初購入だけにボーナスを加え、追加購入では効用だけを加える。遷移元が の候補は使わない。
価格が正なので 。降順なら、参照する cur[p-P_j] はまだ商品 で更新されておらず、同じ商品を二度使わない。昇順にすると、今の商品を買って作った状態から再び同じ商品を買えてしまう。
上の同色二商品の例では、初めは prev=(0,−∞,−∞)、cur=(−∞,−∞,−∞) である。一商品目の後は cur[1]=12。二商品目では、先に cur[2]=12+3=15 を作り、その後で cur[1]=13 に更新する。追加購入ではボーナスを加えず、二商品目自身も再利用していない。
その色の全商品を処理し終えたら、各 について次のように合流する。
ここで初めて「色 を買わない」選択を混ぜる。商品処理中の cur へ prev をコピーすると、cur が「現色を一つ以上買った」という意味を失うので、ここで説明する方式ではコピーしない。
すべての色を処理した後、答えは である。予算は使い切る必要がないので dp[X] だけを見てはいけない。dp[0]=0 は合流のたびに残り、何も買わない選択も含まれる。
典型の発動条件
grouped knapsack
グループを一度でも選ぶとボーナスや費用が発生し、それ以降は各要素の寄与だけが加わるときに使う。グループ内で複数の要素を選べる場合も、未選択の層と一つ以上選択した層を分ければ、初回だけの効果を表せる。不選択の合流はグループを処理し終えてから行う。
0/1 knapsackの降順更新
各商品を高々一度選ぶ価格DPを同じ配列で更新するときに使う。価格が正なら、大きい価格から更新することで、遷移元を「今の商品をまだ使っていない値」に保てる。
問題固有の要素
色のボーナスは、その色の商品を一つ以上買ったかだけで決まる。色を連続して処理できるため、使用済みの全色の集合を状態に持つ必要はない。処理済みの色の寄与は満足度へ織り込み、処理中の一色についてだけ未購入・購入済みを区別する。
商品を見る順序を選び直せるなら、履歴のどの部分を処理済みとして忘れられるかに注目したい。
正当性
ある色の処理前に、prev[p] が、それ以前の色だけから価格ちょうど で選ぶ満足度の最大値を表すと仮定する。その色の商品を一つも見ていない時点では、現色を一つ以上買った選択は存在しないので、cur をすべて にするのが正しい。
商品 を見た後の、現色を一つ以上買う任意の選択を考える。商品 を含まなければ、更新前の cur[p] に含まれる。含むなら、商品 を取り除いた選択が現色を含むかで二分できる。含まなければ prev[p-P_j] から効用と初回ボーナスを加え、含むなら更新前の cur[p-P_j] から効用だけを加える。この三通りで全選択を覆い、どの遷移もボーナスを各使用色に一回だけ加える。降順更新により商品 を二度使わないので、更新後も cur の定義が保たれる。
色を買わない選択は prev、一つ以上買う選択は処理後の cur がすべて覆う。その最大を取れば、その色まで処理した dp の定義が成立する。初期状態は空集合だけで定義を満たすため、この議論を全色へ繰り返せる。最後に価格0から までの最大を取ると、空集合を含む予算内の全選択の最大満足度が得られる。
実装上の注意
- 色番号は なので、色ごとの商品リストへ直接振り分けられる。商品がない色は飛ばしてよい。
prev は一色の処理中ずっと固定し、cur は色が変わるたびに全要素を へ戻す。配列は色ごとに全履歴を保存せず、二本を使い回せる。
- 到達不能の番兵から加算する候補は除外する。満足度は最大でも なので、符号付き64 bit整数で保持する。
cur[0] は到達不能のまま、色終了後の dp[0] は0のままである。未購入の0を cur に入れず、prev 側で保つ。
復習の核
- 「初めて選んだときだけ加点」なら、要素をグループごとに処理し、未選択と選択済みを分ける。
- 各配列が許す選択を言葉にする。「一つ以上選ぶ」配列へ空集合を混ぜると、不変条件が変わる。
- 降順更新は、今の商品を遷移元に混ぜないために行う。「価格ちょうど」で持ったDPから「予算以下」の答えを取る範囲も確認する。
計算量と制約
時間
商品を色別リストに振り分けるのに 。各商品の降順更新は で、全商品では 。色ごとの配列初期化と不購入の合流も、一色につき 、色数は高々 なので合計 。答えの取り出しの を含め、全体で 時間。
空間
価格 に対する prev と cur の二本を使い回すので、DPの作業領域は 。色別の商品保持に を使い、合計 空間。
制約との対応
、 なので、商品ごとの価格走査は高々 回である。 より、降順更新の参照先は必ず小さい価格になる。 なので満足度には64 bit整数が必要となる。色番号の範囲 を使えば、整列なしでグループ分けできる。
出典