考察
缶切りも品物一個分の選択枠を使うので、満足度の高い缶だけを選んでも開けられるとは限らない。そこで、缶切りが不要な缶と、缶切りが必要な缶・缶切りの組とに選択枠を分ける。後者では、開けられる間は価値の高い缶を取り、開けられなくなったときだけ容量の大きい缶切りを追加すると、各枠数での最大満足度を一度の走査で求められる。
以下、缶切りが不要な缶を type0、必要な缶を type1、缶切りを type2 と呼ぶ。type0・type1 の価値は満足度、type2 の容量は開けられる缶の個数である。缶の単品価値だけで上位を選ぶ方針では、缶切りのためにどの缶を何個諦めるかを決められない。まず同種類の品物同士を比較し、選択の自由度を減らそう。
同種類の選択個数を固定すると、缶は満足度が高いものへ交換しても必要な選択枠数は変わらず、缶切りは容量が大きいものへ交換しても開けられる缶を失わない。三種類をそれぞれ降順に並べた配列を 、その要素数を とする。配列の添字は1始まりで、各種類では先頭から何個取るかだけを考えればよい。
ここで、品物不足を扱うため、選択個数を「高々」として考える。高々 個を選ぶ最適値は、ちょうど 個を選ぶ元の問題の最適値と等しい。実際、 なので、足りない個数だけ未選択の品物を追加できる。缶切りや開けない缶は満足度0として追加でき、type0 の満足度も非負なので、既に得た満足度を失わない。
に対して、type0 に高々 枠を使うときの最大満足度を と置く。初期値は で、
である。type0 が尽きたら末尾の値をそのまま延長する。したがって は、実在する缶の個数を超える添字でも定義される。
同様に、type1 と type2 に合わせて高々 枠を使うときの最大満足度を と置く。開けない type1 は価値0なので、この側の最適値を求める間は選ばずに済む。 を求めるには、これまで選んだ缶切りでまだ開けられる缶の個数 capacity に注目する。
capacity > 0 で type1 が残っているなら、次の type1 を取る。開封の準備は既にできているので、満足度を直ちに増やせる。追加の缶切りを先に取る必要はない。
capacity = 0 で type1 が残っているなら、次の type2 を取る。より多くの缶を開けられるものほど、以後の選択を妨げない。
前者で缶を先に選べる理由を、固定した枠数の最適解から考える。既に選んだ品物を含む最適解が次の缶を含まないとする。そこに別の未確定の缶があれば、最大満足度の次の缶へ交換できる。未確定の缶がなく追加の缶切りだけがあれば、その一個を次の缶へ交換できる。既に確保した容量だけでこの缶まで開けられるため、満足度は下がらない。選択枠が余っていれば、そのまま缶を追加できる。こうして、使える容量がある間は缶を先に確定してよい。
具体的には 、capacity = 0、 の未使用先頭を指す添字 から始め、 の順に次を行う。
- まず とする。
- なら値を変えずに進む。缶が残っていないので追加の缶切りは不要である。
- そうでなく
capacity > 0 なら、 を に加え、 を1増やし、capacity を1減らす。
- そうでなく なら、 を
capacity に加え、 を1増やす。缶切りにも一枠を使うので、この回には缶を取らず、満足度は増えない。
capacity = 0 で未使用の缶切りも残っていなければ、以後も値を変えない。開けられない缶を選んでも満足度は増えない。
例えば なら、 は となる。一枠目で最後の缶切りを選んでも、開封容量は3残っているので、二枠目・三枠目では缶を選んで満足度を増やせる。三枠を使った後は缶が尽きるため、容量が1余っても、それ以降の値は14のままである。最後の二枠では、実際に品物を追加したと解釈する必要はない。
最後に、type1・type2 側へ渡す枠数 をすべて試し、
を答えとする。二つの配列はともに「高々その枠数での最適値」なので、どちらかの品物が足りなくても同じ式で評価できる。
典型の発動条件
種類別 sort と個数固定
発動条件: 同種類の品を一対一で交換しても必要な枠数が変わらず、価値または能力の大きい品へ替えても他の選択を妨げないとき。
種類ごとに降順の先頭部分へ圧縮し、残った種類間の枠の配分を探索する。品物が不足する場合は、配列の添字が「ちょうど選ぶ個数」か「使ってよい枠数」かを区別する。
resource 解禁型の貪欲
発動条件: 報酬品には容量が必要で、容量を与える補助品も同じ選択枠を消費するとき。
利用可能な容量があるなら報酬品を先に取れることと、容量不足なら最大容量の補助品を選んでよいことを別々に示す。この二つの交換が成立すれば、一方向に選択を伸ばして各枠数の最適値を作れる。
問題固有の要素
開封容量が余ることと、選択枠が余ることは異なる。缶切り一個で何缶でも選べるわけではなく、選ぶ缶にも一枠ずつ必要である。type1・type2 側では、type1 が尽きた場合、または capacity = 0 で未使用の type2 も尽きた場合に、以後の選択枠を増やしても満足度は増えない。未使用の type2 が尽きても、開封容量と type1 が残っていれば、枠を増やして缶を選び、満足度を増やせる。
「高々」の最適値へ緩められる理由は、余った選択枠を無価値の品物でも埋められる点にある。ちょうどの個数が要求される別問題へ持ち帰る際は、追加できる品物の数と、追加して目的値が悪化しないことを確認する。
正当性
種類内の交換により、type0 は満足度降順の先頭から選べばよく、品物が尽きた後も は高々 枠の最適値を表す。
type1・type2 側について、任意の上限 を固定する。満足度に寄与しない未開封缶は取り除けるので、選んだ缶をすべて開ける最適解を考えてよい。貪欲法が選んだ品物を含む最適解が存在することを、選択を進めながら保つ。容量が正で缶が残る場合は、考察で示した交換または追加により、次の最大満足度の缶を含む最適解へ移れる。
容量が0の場合、まだ選択枠が残っていても、現在の品物だけでは新たな缶を開けられない。最適解がこの先に缶を選んで満足度を増やすなら、未選択の缶切りを少なくとも一個含む。その缶切りを未選択の最大容量のものへ交換しても、選択枠数は変わらず開封能力は下がらない。最適値が既に達成されている場合も、一枠を使って缶切りを追加してよい。よって、この選択を含む最適解が存在する。缶が尽きた場合、または容量0で缶切りが尽きた場合は、これ以上満足度を増やせない。以後の値を据え置けば、すべての で が求まる。
各 は、異なる種類の品物を合わせて高々 個選ぶことで実現できる。一方、任意の高々 個の選び方で、type1・type2 の選択個数を とすれば、満足度はこの和以下になる。従って全 での最大値が高々 個の最適値であり、未選択品の追加によりちょうど 個へ拡張できるので、元の問題の答えでもある。
実装上の注意
- は長さ で作り、初期値をともに0とする。各側でこれ以上満足度を増やせなくなっても、配列の構築を打ち切らず、直前の値を末尾までコピーする。
- type1 がなければ が続く。type2 がなければ、type1 があっても が続く。公式サンプル2は全品が type1、 なので、 がともに全要素0となり、答えも0である。
- type0 が不足しても の値を延長する。 や容量余りにも同じ手順を使い、実際には選んでいない品物を配列外から参照しない。
- 缶切りを追加した回も一枠を使う。
capacity は選択可能な残り品数ではなく、まだ開けられる缶数である。
- 満足度の合計には64 bit整数を使う。上限は であり、32 bit整数には収まらない。
復習の核
- 補助品も選択枠を使うときは、種類内の支配関係と種類間の枠配分を分けて考える。
- 貪欲では「次の選択を含む最適解へ交換できるか」を問う。容量が余っているときと不足しているときでは、交換する対象が異なる。
- 添字を「使ってよい枠数」と定義すれば、品物枯渇後も最適値を延長できる。「ちょうど」の問題へ戻すには、余った枠を悪化なく埋められる根拠が必要である。
計算量と制約
時間
三種類のソートに合計 時間、 の構築と枠配分の全列挙に 時間を使う。 より、全体で 時間。
空間
三種類の配列に合計 、最適値の配列 に を使い、全体で 空間。
制約との対応
公式制約は 、、 で、入力はすべて整数である。この規模では部分集合の全探索は使えないが、ソート後に各品物を高々一度選ぶ上記の手順なら処理できる。満足度が非負であることは、「高々」の解をちょうど 個へ拡張する際にも使っている。
出典