考察
交換で失う瓶の本数を重さ、追加で飲める本数を価値と見ると、同じ交換を何度でも使えるナップサックに近い。容量は巨大だが、一回の交換で失う本数は小さい。そこで、効率が最良の交換以外を使う部分だけを有限範囲へ押し込めたい。ただし、交換に必要な瓶がそろうまでの初動は、効率だけで置き換えてはならない。
空き瓶が減る過程を逆向きにする
持っているコーラを先に飲んでも交換の選択肢は減らない。最初の 本をすべて飲み、その後も交換でもらったコーラをすぐに飲む形で考える。交換 で失う空き瓶数を と置く。空き瓶が 本あるとき、 なら交換して 本を飲め、空き瓶は 本になる。
この操作を最後から戻す。操作後の空き瓶が 本なら、操作前は 本である。順向きの条件 は と同値なので、逆向きの一手は
であり、使える条件は かつ となる。逆向きの は、使った瓶数ではなく、その時点で復元した空き瓶数である。出発点は順向きで最後に残す空き瓶数なので、 から自由に選べる。逆向きに へ戻りきった列が、元問題の交換列に対応する。求める答えは、最初に飲む 本と逆向きの最大追加飲酒数の和である。
同じ の交換が複数あれば、 が最大のものだけを残す。順向きでは同じ条件で交換でき、より多く飲め、交換後の空き瓶も多く残るので劣らない。 と置くと、残る種類数は高々 であり、、 となる。
小さい範囲のDPと、最良の交換による延長
逆向きでは資源が必ず増えるため、 を昇順に処理できる。 を「任意の初期残量から合法な逆向き操作で資源 へ達するときの、最大追加飲酒数」とする。どの も操作なしの出発点にできるので、全要素を で初期化する。各交換について を満たせば、
と更新する。 まで計算すれば答えは だが、 なので、そのままでは間に合わない。
一方、 になれば全交換の条件 が満たされ、その後は重さ ・価値 の通常の無制限ナップサックになる。密度 が最大の交換を一つ選び、基準品物と呼ぶ。その値を と書く。同率ならどれを選んでもよい。
ここで使うのは、「最良密度だけを選ぶ」貪欲法ではない。後の証明で、初動と基準品物以外の例外を先にまとめ、その到達資源を
未満にできることを示す。その後に置く基準品物の反復を、以下では後半と呼ぶ。
したがってDPは だけを昇順に処理し、 かつ のときだけ更新する。
- なら、逆向きに へ達する全経路が範囲内なので、答えは 。
- なら、後半の開始資源を から選び、次の最大値を取る。
各候補は から始めるので、基準品物を最初の一回から合法に使える。割り切れず最後の資源が 未満になっても、足りない分だけ逆向きの初期残量を増やし、全状態を同じ量だけ上へずらせばよい。各下限条件は保たれ、終点は になるため、追加飲酒数はそのまま実現できる。
開始条件を無視する危険は一種類でも現れる。、交換が だけなら、順向きでは一回交換して合計 本飲める。逆向きは であり、 となる。ところが、 から重さ ・価値 の反復を許すと、実行できない五回の交換を数えて を返してしまう。小さい資源の実行条件はDPで守り、条件が消えた範囲からだけ後半へ延長する。
典型の発動条件
best density itemによる大容量knapsack
容量だけが巨大で各品物の重さが小さいとき、最大密度の品物を基準に選ぶ。密度が最良でも端数や初動まで貪欲に決められるとは限らない。例外部分の上界を証明できれば、そこだけDPして残りを基準品物で埋められる。
鳩の巣原理による交換
非基準品物が多数あるなら、累積重さを基準品物の重さで割った余りに注目する。同じ余りの二点の間は、同じ総重さの基準品物へ価値を減らさず置換できる。ただし、使用条件がある問題では、その置換と並べ替えが合法になる範囲を先に確保する。
支配optionの除去
同じ必要量の選択肢のうち、報酬と残資源がともに劣らないものだけを残す。この問題では同じ の最大 へ統合でき、種類数を入力件数ではなく必要量の上限で抑えられる。
問題固有の要素
順向きでは空き瓶を減らす交換を、逆向きでは資源を増やす品物として扱う。初期残量を自由に選べることが全状態の基底 に対応し、 から使用条件が消える。小さいのは総資源 ではなく、一手の増分を抑える である。この二つの性質を組み合わせると、初動を保護したまま例外を有限範囲へ閉じ込められる。
正当性
DPの各遷移は、交換と直後の飲酒を逆にした一手そのものである。 なので、昇順に処理した時点で への全遷移は終わっている。全状態の基底 が任意の初期残量を表すため、有限範囲内の合法な逆向き操作列を過不足なく評価できる。以下では、大きい の最適解も有限DPと後半の反復へ変形できることを示す。
最初にKへ達するまでを保護する
の最適な逆向き操作列を一つ取る。初期残量が より大きければ、これを へ下げ、同じ操作列を使ってもよい。全状態が 以上なので使用条件は満たされ、終点は下がるだけで を超えず、追加飲酒数も変わらない。終点が 以下の列も、考察で述べた平行移動により元問題で実現できる。
そこで初期残量は 以下としてよい。全操作を通じても に達しない列なら、終点が 未満のままなので、資源を にして基準品物をさらに一回使える。実際、 であり、 だから最適性に反する。
初めて資源が 以上になるまでの操作列を、その順序のまま保存する。その到達資源を とすると、直前は 未満で、一手の増分も 未満だから、
である。最初から資源 なら、保存する操作は空列で となる。以後の操作はすべて資源 以上で行われるため、任意に並べ替えても使用条件を満たす。資源は単調増加し、総増分は変わらないので、途中で終点や を超えることもない。
保護した部分より後で、例外を減らす
保存部分の後だけを考え、非基準品物を先に、基準品物を末尾に並べる。非基準品物が 個以上あれば、その先頭 個の累積重さを とする。余りは 種類なので、ある について
となる。間の非空な品物列の総重さは と書ける。これを基準品物 個へ替える。取り除く品物の価値の合計を とすると、密度の最大性から
であり、価値は減らない。置換前後で総増分が等しく、すべて資源 以上で行うため、新しい操作も合法である。
置換後の基準品物も末尾へ移し、同じ交換を繰り返す。非基準品物の個数が毎回減るので、密度が同率でも停止する。最終的には保存部分より後の非基準品物は高々 個となる。保存部分には、基準品物を含めて一切手を加えない。
保存部分と残った非基準品物を実行し終えた資源を とする。 かつ各増分が高々 なので、
となる。つまり、初期残量を含む開始部分と例外の合計が 未満へ収まり、その後は基準品物だけを使う最適形がある。
この形の先頭部分を有限DPは評価できるので、その資源 における は先頭部分の価値以上である。基準品物を使えるだけ使う候補は最適形以上の価値を持ち、逆にすべての候補は合法な列として実現できる。したがって考察の最大値は真の最適値に等しい。 の場合は、そもそも全状態がDP範囲に含まれるため交換論を使わずに正しい。
実装上の注意
- DPの配列末尾は とし、 の昇順で更新する。 と を両方確認する。全要素を で初期化し、 だけを出発点にしない。
- では を返す。 からは を調べる。小さい に反復式を一律適用しない。
- 密度は浮動小数点で割らず、 と の交差積で比べる。後半の回数、積、答えは符号付き64 bit整数で扱う。
- 入力を読みながら同じ の最大 だけを保存すれば、元の 組を保持する必要はない。
復習の核
- 巨大容量と小さい一手の増分が並んだら、基準品物との剰余衝突で例外を有限化できないか考える。
- 密度による置換の価値比較と、操作を実行できる条件は別に確認する。初動を守り、条件が消えた後だけを交換・並べ替えする。
- 逆向きDPでは、添字が何を復元した量か、どこから出発できるかを先に定める。それが基底と反復を始められる範囲を決める。
計算量と制約
時間
入力 組の統合に 。残る高々 種類を選別し、最大密度を求めるのに 。DPは高々 状態から高々 種類へ遷移し、後半の開始点も高々 個調べる。全体で 時間であり、巨大な に比例する反復はない。
空間
DP配列が 、入力を統合する表と品物列が 。入力を逐次処理する場合、全体で 空間。
制約との対応
公式制約は 、、 で、入力はすべて整数。実行時間制限は2秒、メモリ制限は1024 MiB。 なので 、DPの遷移候補は高々約 個である。
一回の交換で瓶は必ず一つ以上減るため、交換回数は高々 。一回の追加飲酒数は高々 なので、答えは 以下であり、符号付き64 bit整数に収まる。
出典