ABC 415 G — Get Many Cola

考察

交換で失う瓶の本数を重さ、追加で飲める本数を価値と見ると、同じ交換を何度でも使えるナップサックに近い。容量は巨大だが、一回の交換で失う本数は小さい。そこで、効率が最良の交換以外を使う部分だけを有限範囲へ押し込めたい。ただし、交換に必要な瓶がそろうまでの初動は、効率だけで置き換えてはならない。

空き瓶が減る過程を逆向きにする

持っているコーラを先に飲んでも交換の選択肢は減らない。最初の NN 本をすべて飲み、その後も交換でもらったコーラをすぐに飲む形で考える。交換 ii で失う空き瓶数を Di=Ai−BiD_i=A_i-B_i と置く。空き瓶が xx 本あるとき、x≥Aix\geq A_i なら交換して BiB_i 本を飲め、空き瓶は x−Dix-D_i 本になる。

この操作を最後から戻す。操作後の空き瓶が xx 本なら、操作前は x+Dix+D_i 本である。順向きの条件 x+Di≥Aix+D_i\geq A_i は x≥Bix\geq B_i と同値なので、逆向きの一手は

x⟶x+Di,追加飲酒数 Bix\longrightarrow x+D_i,\qquad \text{追加飲酒数 }B_i

であり、使える条件は x≥Bix\geq B_i かつ x+Di≤Nx+D_i\leq N となる。逆向きの xx は、使った瓶数ではなく、その時点で復元した空き瓶数である。出発点は順向きで最後に残す空き瓶数なので、0≤x≤N0\leq x\leq N から自由に選べる。逆向きに NN へ戻りきった列が、元問題の交換列に対応する。求める答えは、最初に飲む NN 本と逆向きの最大追加飲酒数の和である。

同じ AiA_i の交換が複数あれば、BiB_i が最大のものだけを残す。順向きでは同じ条件で交換でき、より多く飲め、交換後の空き瓶も多く残るので劣らない。K=max⁡iAiK=\max_i A_i と置くと、残る種類数は高々 KK であり、1≤Di≤K−11\leq D_i\leq K-1、Bi<KB_i<K となる。

小さい範囲のDPと、最良の交換による延長

逆向きでは資源が必ず増えるため、xx を昇順に処理できる。dp[x]dp[x] を「任意の初期残量から合法な逆向き操作で資源 xx へ達するときの、最大追加飲酒数」とする。どの xx も操作なしの出発点にできるので、全要素を 00 で初期化する。各交換について x≥Bix\geq B_i を満たせば、

dp[x+Di]←max⁡(dp[x+Di], dp[x]+Bi)dp[x+D_i]\gets\max\bigl(dp[x+D_i],\ dp[x]+B_i\bigr)

と更新する。NN まで計算すれば答えは N+dp[N]N+dp[N] だが、N≤1015N\leq 10^{15} なので、そのままでは間に合わない。

一方、x≥Kx\geq K になれば全交換の条件 x≥Bix\geq B_i が満たされ、その後は重さ DiD_i・価値 BiB_i の通常の無制限ナップサックになる。密度 Bi/DiB_i/D_i が最大の交換を一つ選び、基準品物と呼ぶ。その値を D∗,B∗D^*,B^* と書く。同率ならどれを選んでもよい。

ここで使うのは、「最良密度だけを選ぶ」貪欲法ではない。後の証明で、初動と基準品物以外の例外を先にまとめ、その到達資源を

T=K(K+1)T=K(K+1)

未満にできることを示す。その後に置く基準品物の反復を、以下では後半と呼ぶ。

したがってDPは 0≤x≤min⁡(N,T−1)0\leq x\leq\min(N,T-1) だけを昇順に処理し、x≥Bix\geq B_i かつ x+Di≤min⁡(N,T−1)x+D_i\leq\min(N,T-1) のときだけ更新する。

  • N<TN<T なら、逆向きに NN へ達する全経路が範囲内なので、答えは N+dp[N]N+dp[N]。
  • N≥TN\geq T なら、後半の開始資源を K≤x<TK\leq x<T から選び、次の最大値を取る。
N+max⁡K≤x<T(dp[x]+⌊N−xD∗⌋B∗)N+\max_{K\leq x<T} \left(dp[x]+\left\lfloor\frac{N-x}{D^*}\right\rfloor B^*\right)

各候補は x≥K>B∗x\geq K>B^* から始めるので、基準品物を最初の一回から合法に使える。割り切れず最後の資源が NN 未満になっても、足りない分だけ逆向きの初期残量を増やし、全状態を同じ量だけ上へずらせばよい。各下限条件は保たれ、終点は NN になるため、追加飲酒数はそのまま実現できる。

開始条件を無視する危険は一種類でも現れる。N=5N=5、交換が (A,B)=(5,4)(A,B)=(5,4) だけなら、順向きでは一回交換して合計 99 本飲める。逆向きは x=4→5x=4\to5 であり、dp[5]=4dp[5]=4 となる。ところが、x=0x=0 から重さ 11・価値 44 の反復を許すと、実行できない五回の交換を数えて 5+5×4=255+5\times4=25 を返してしまう。小さい資源の実行条件はDPで守り、条件が消えた範囲からだけ後半へ延長する。

典型の発動条件

best density itemによる大容量knapsack

容量だけが巨大で各品物の重さが小さいとき、最大密度の品物を基準に選ぶ。密度が最良でも端数や初動まで貪欲に決められるとは限らない。例外部分の上界を証明できれば、そこだけDPして残りを基準品物で埋められる。

鳩の巣原理による交換

非基準品物が多数あるなら、累積重さを基準品物の重さで割った余りに注目する。同じ余りの二点の間は、同じ総重さの基準品物へ価値を減らさず置換できる。ただし、使用条件がある問題では、その置換と並べ替えが合法になる範囲を先に確保する。

支配optionの除去

同じ必要量の選択肢のうち、報酬と残資源がともに劣らないものだけを残す。この問題では同じ AiA_i の最大 BiB_i へ統合でき、種類数を入力件数ではなく必要量の上限で抑えられる。

問題固有の要素

順向きでは空き瓶を減らす交換を、逆向きでは資源を増やす品物として扱う。初期残量を自由に選べることが全状態の基底 00 に対応し、x≥Kx\geq K から使用条件が消える。小さいのは総資源 NN ではなく、一手の増分を抑える KK である。この二つの性質を組み合わせると、初動を保護したまま例外を有限範囲へ閉じ込められる。

正当性

DPの各遷移は、交換と直後の飲酒を逆にした一手そのものである。Di>0D_i>0 なので、昇順に処理した時点で dp[x]dp[x] への全遷移は終わっている。全状態の基底 00 が任意の初期残量を表すため、有限範囲内の合法な逆向き操作列を過不足なく評価できる。以下では、大きい NN の最適解も有限DPと後半の反復へ変形できることを示す。

最初にKへ達するまでを保護する

N≥TN\geq T の最適な逆向き操作列を一つ取る。初期残量が KK より大きければ、これを KK へ下げ、同じ操作列を使ってもよい。全状態が KK 以上なので使用条件は満たされ、終点は下がるだけで NN を超えず、追加飲酒数も変わらない。終点が NN 以下の列も、考察で述べた平行移動により元問題で実現できる。

そこで初期残量は KK 以下としてよい。全操作を通じても KK に達しない列なら、終点が KK 未満のままなので、資源を KK にして基準品物をさらに一回使える。実際、K+D∗<T≤NK+D^*<T\leq N であり、B∗>0B^*>0 だから最適性に反する。

初めて資源が KK 以上になるまでの操作列を、その順序のまま保存する。その到達資源を pp とすると、直前は KK 未満で、一手の増分も KK 未満だから、

K≤p<2KK\leq p<2K

である。最初から資源 KK なら、保存する操作は空列で p=Kp=K となる。以後の操作はすべて資源 KK 以上で行われるため、任意に並べ替えても使用条件を満たす。資源は単調増加し、総増分は変わらないので、途中で終点や NN を超えることもない。

保護した部分より後で、例外を減らす

保存部分の後だけを考え、非基準品物を先に、基準品物を末尾に並べる。非基準品物が D∗D^* 個以上あれば、その先頭 D∗D^* 個の累積重さを S0=0,S1,…,SD∗S_0=0,S_1,\ldots,S_{D^*} とする。余りは D∗D^* 種類なので、ある 0≤l<r≤D∗0\leq l<r\leq D^* について

Sl≡Sr(modD∗)S_l\equiv S_r\pmod{D^*}

となる。間の非空な品物列の総重さは Sr−Sl=qD∗S_r-S_l=qD^* と書ける。これを基準品物 qq 個へ替える。取り除く品物の価値の合計を VV とすると、密度の最大性から

V≤B∗D∗(Sr−Sl)=qB∗V\leq \frac{B^*}{D^*}(S_r-S_l) =qB^*

であり、価値は減らない。置換前後で総増分が等しく、すべて資源 KK 以上で行うため、新しい操作も合法である。

置換後の基準品物も末尾へ移し、同じ交換を繰り返す。非基準品物の個数が毎回減るので、密度が同率でも停止する。最終的には保存部分より後の非基準品物は高々 D∗−1D^*-1 個となる。保存部分には、基準品物を含めて一切手を加えない。

保存部分と残った非基準品物を実行し終えた資源を xx とする。D∗≤K−1D^*\leq K-1 かつ各増分が高々 K−1K-1 なので、

K≤x≤p+(D∗−1)(K−1)<2K+K(K−1)=TK\leq x \leq p+(D^*-1)(K-1) <2K+K(K-1)=T

となる。つまり、初期残量を含む開始部分と例外の合計が TT 未満へ収まり、その後は基準品物だけを使う最適形がある。

この形の先頭部分を有限DPは評価できるので、その資源 xx における dp[x]dp[x] は先頭部分の価値以上である。基準品物を使えるだけ使う候補は最適形以上の価値を持ち、逆にすべての候補は合法な列として実現できる。したがって考察の最大値は真の最適値に等しい。N<TN<T の場合は、そもそも全状態がDP範囲に含まれるため交換論を使わずに正しい。

実装上の注意

  • DPの配列末尾は L=min⁡(N,T−1)L=\min(N,T-1) とし、x=0,…,Lx=0,\ldots,L の昇順で更新する。x≥Bix\geq B_i と x+Di≤Lx+D_i\leq L を両方確認する。全要素を 00 で初期化し、dp[0]dp[0] だけを出発点にしない。
  • N<TN<T では N+dp[N]N+dp[N] を返す。N=TN=T からは K≤x<TK\leq x<T を調べる。小さい xx に反復式を一律適用しない。
  • 密度は浮動小数点で割らず、BiD∗B_iD^* と B∗DiB^*D_i の交差積で比べる。後半の回数、積、答えは符号付き64 bit整数で扱う。
  • 入力を読みながら同じ AiA_i の最大 BiB_i だけを保存すれば、元の MM 組を保持する必要はない。

復習の核

  • 巨大容量と小さい一手の増分が並んだら、基準品物との剰余衝突で例外を有限化できないか考える。
  • 密度による置換の価値比較と、操作を実行できる条件は別に確認する。初動を守り、条件が消えた後だけを交換・並べ替えする。
  • 逆向きDPでは、添字が何を復元した量か、どこから出発できるかを先に定める。それが基底と反復を始められる範囲を決める。

計算量と制約

時間

入力 MM 組の統合に O(M)O(M)。残る高々 KK 種類を選別し、最大密度を求めるのに O(K)O(K)。DPは高々 T=K(K+1)T=K(K+1) 状態から高々 KK 種類へ遷移し、後半の開始点も高々 TT 個調べる。全体で O(M+K3)O(M+K^3) 時間であり、巨大な NN に比例する反復はない。

空間

DP配列が O(K2)O(K^2)、入力を統合する表と品物列が O(K)O(K)。入力を逐次処理する場合、全体で O(K2)O(K^2) 空間。

制約との対応

公式制約は 1≤N≤10151\leq N\leq 10^{15}、1≤M≤2×1051\leq M\leq 2\times10^5、1≤Bi<Ai≤3001\leq B_i<A_i\leq300 で、入力はすべて整数。実行時間制限は2秒、メモリ制限は1024 MiB。2≤K≤3002\leq K\leq300 なので T≤90,300T\leq90{,}300、DPの遷移候補は高々約 2.71×1072.71\times10^7 個である。

一回の交換で瓶は必ず一つ以上減るため、交換回数は高々 NN。一回の追加飲酒数は高々 K−1K-1 なので、答えは N+N(K−1)=KN≤3×1017N+N(K-1)=KN\leq3\times10^{17} 以下であり、符号付き64 bit整数に収まる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Get Many Cola の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 大容量unbounded knapsackのeventual linearity

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 大容量unbounded knapsackのeventual linearity

    補助タグ: 貪欲法と交換論

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

    学習の位置

    体系上の位置: 大容量unbounded knapsackのeventual linearity

    • 剰余の鳩の巣原理と密度交換で非基準itemの使用量を界し、有限prefix DPと最大密度itemの反復から巨大capacityの最適値を求められる。

    先に読む単元:

    • 資源・容量DP — 最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。
    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題