ABC 332 G — Not Too Many Balls

考察

ボールの配分は最大流で表せるが、色と箱の組が多すぎて、そのままでは辺を持ちきれない。そこで最大流と同じ値を持つ最小カットを考える。色と箱を隔てる辺の容量が「色の番号×箱の番号」という積なので、カットの容量を式にすると、色集合を一つの添字和へ圧縮できる。

収納を表すネットワークからカットへ移る

始点を ss、終点を tt とし、各色と各箱に対応する頂点を作る。色の番号を i=1,…,Ni=1,\ldots,N、箱の番号を j=1,…,Mj=1,\ldots,M として、次の有向辺を置く。

  • ss から色 ii へ容量 AiA_i:その色の供給上限。
  • 色 ii から箱 jj へ容量 ijij:その色をその箱へ入れる個数の上限。
  • 箱 jj から tt へ容量 BjB_j:箱全体の容量。

色から箱への整数流量を収納個数とすれば、流量保存と各辺の容量が問題の制約に一致する。逆に合法な収納から同じ値の整数フローを作れるため、答えはこのネットワークの最大流である。しかし中間の辺だけで最大 NM=2.5×108NM=2.5\times10^8 本ある。Dinic 法などを直接適用するより、最大流最小カット定理を使って、同じ最適値を別の形で求めたい。

カットとは、ss を始点側、tt を終点側に置く頂点の分割であり、始点側から終点側へ向かう辺の容量を合計する。始点側に置く色の番号の集合を PP とする。PP に含まれない色については、ss からの辺がカットを横切るので、まず ∑i∉PAi\sum_{i\notin P}A_i が加わる。

次に箱 jj の所属側を決める。PP を固定すれば、二つの選択による寄与は次の通りである。

箱の所属側カットを横切る辺容量の寄与
始点側箱 jj から ttBjB_j
終点側PP に含まれる各色から箱 jj∑i∈Pij=j∑i∈Pi\sum_{i\in P}ij=j\sum_{i\in P}i

箱同士を結ぶ辺はないので、各箱で小さい方を独立に選べる。ここで色の個数でも供給量の和でもなく、番号の和を

k=∑i∈Pi,L=N(N+1)2k=\sum_{i\in P}i,\qquad L=\frac{N(N+1)}2

と置くと、0≤k≤L0\leq k\leq L であり、PP を固定したときの最小カット容量は

∑i∉PAi+∑j=1Mmin⁡(jk,Bj)\sum_{i\notin P}A_i+\sum_{j=1}^{M}\min(jk,B_j)

となる。箱側の値を F(k)=∑j=1Mmin⁡(jk,Bj)F(k)=\sum_{j=1}^{M}\min(jk,B_j) と呼ぶ。箱側からは、どの色を選んだかという詳細は見えず、kk さえ分かればよい。同じ kk になる色集合が複数ある場合は、色側の寄与が最小のものだけを残せばよい。

箱ごとに収納を貪欲に決める方法では、複数の箱で同じ色の供給を取り合うため、局所的な選択を正当化できない。カットの式に移る利点は、こうした配分の競合を、色側の選択と箱側の独立な最小値へ分離できることにある。

色の番号の和を添字にして DP する

全色の供給和を S=∑i=1NAiS=\sum_{i=1}^{N}A_i とする。色を番号順に処理し、dp[k] を「処理済みの色から選んだ集合 PP の番号の和がちょうど kk であるときの、S−∑i∈PAiS-\sum_{i\in P}A_i の最小値」と定義する。未処理の色もいったん SS に含めておき、色を選ぶたびにその供給量を引く定義である。

一つも処理していないときは空集合だけが選べるので、初期値は

dp[0]=S,dp[k]=∞(1≤k≤L)\mathrm{dp}[0]=S,\qquad \mathrm{dp}[k]=\infty\quad(1\leq k\leq L)

である。色 ii を処理するとき、選ばなければ値はそのまま、選べば番号の和が ii 増えて値が AiA_i 減る。したがって、k=L,L−1,…,ik=L,L-1,\ldots,i の降順に

dp[k]←min⁡(dp[k], dp[k−i]−Ai)\mathrm{dp}[k]\gets\min\bigl(\mathrm{dp}[k],\ \mathrm{dp}[k-i]-A_i\bigr)

と更新する。ただし dp[k-i] が到達不能を表す無限大なら、この遷移は行わない。小さい添字の参照元はまだ色 ii を処理する前の値なので、同じ色を二度選ばずに済む。昇順だと今選んだ色をさらに使う更新が起こり、0/1 選択を表せない。

全色を処理すると、dp[k] は番号の和が kk となる色集合のうち、∑i∉PAi\sum_{i\notin P}A_i が最小の値になる。例えば番号の和が3になる P={3}P=\{3\} と P={1,2}P=\{1,2\} は箱側の寄与が同じでも、色側はそれぞれ S−A3S-A_3 と S−A1−A2S-A_1-A_2 なので、小さい方を採る必要がある。番号の和の到達可否だけでは足りない。

箱の切替を評価前にまとめて処理する

各 kk で全箱を調べると O(ML)O(ML) 時間かかる。そこで、箱 jj の寄与 min⁡(jk,Bj)\min(jk,B_j) が変わるタイミングに注目する。kk を増やす間、最初は直線 jkjk を使い、これが BjB_j を初めて超えた整数から定数 BjB_j を使えばよい。その最初の整数は

qj=⌊Bjj⌋+1q_j=\left\lfloor\frac{B_j}{j}\right\rfloor+1

である。k=qj−1k=q_j-1 では jk≤Bjjk\leq B_j、k=qjk=q_j では jk>Bjjk>B_j となる。特に BjB_j が jj の倍数なら、k=Bj/j=qj−1k=B_j/j=q_j-1 では両方の値が等しく、まだ直線側に残す。切替はその次の整数である。

切替時点を添字にした二つの配列 slopeDrop[0..L]、constantAdd[0..L] を0で初期化する。各箱について qj≤Lq_j\leq L なら、slopeDrop[q_j] に jj、constantAdd[q_j] に BjB_j を加える。同じ時点で切り替わる箱をこの配列に合算する。qj>Lq_j>L の箱は走査範囲内ではずっと直線側なので、配列への登録は不要である。

未切替の箱の番号の和を aa、切替済みの箱の容量の和を cc とする。最初は全箱が直線側なので

a=∑j=1Mj=M(M+1)2,c=0a=\sum_{j=1}^{M}j=\frac{M(M+1)}2,\qquad c=0

とし、答えの初期値を SS にする。k=0,1,…,Lk=0,1,\ldots,L を昇順に走査し、各 kk では次の順に処理する。

  1. 評価前に、slopeDrop[k] を aa から引き、constantAdd[k] を cc に加える。これで qj=kq_j=k の全箱が定数側へ移る。
  2. F(k)=ak+cF(k)=ak+c を求める。
  3. dp[k] が到達可能なら、dp[k]+F(k)\mathrm{dp}[k]+F(k) で答えの最小値を更新する。

Bj≥0B_j\geq0 より qj≥1q_j\geq1 なので、k=0k=0 では切替はなく F(0)=0F(0)=0 である。Bj=0B_j=0 の箱は qj=1q_j=1 に登録し、k=1k=1 の評価前に傾きから除く。範囲外の切替を登録しなかった箱も、初期傾き aa には必ず含める。

二つの配列から答えを取り出す

独自例として N=2, A=(5,4), M=2, B=(3,5)N=2,\ A=(5,4),\ M=2,\ B=(3,5) を考える。S=9, L=3S=9,\ L=3 で、色1の処理後の dp は (9,4,∞,∞)(9,4,\infty,\infty)、色2の処理後は (9,4,5,0)(9,4,5,0) となる。箱の切替は q1=4q_1=4、q2=3q_2=3 なので、最初の傾きは a=3a=3、k=3k=3 の評価前に箱2だけを切り替えて a=1,c=5a=1,c=5 とする。

kkdp[k]F(k)F(k)dp[k]+F(k)\mathrm{dp}[k]+F(k)
0909
1437
25611
3088

最小は k=1k=1 の7である。これは P={1}P=\{1\} に対応し、色2の供給4と、箱側の寄与 1+2=31+2=3 を足したカット容量になる。実際、色1を各箱に1個・2個、色2を各箱に2個・2個入れれば合計7個を収納できる。

求める値は

min⁡0≤k≤L(dp[k]+F(k))\min_{0\leq k\leq L}\bigl(\mathrm{dp}[k]+F(k)\bigr)

そのものである。このカット容量は収納数の上限であり、最大流最小カット定理によって達成も保証される。ここからさらに SS を引いたり、SS からこの値を引いたりする必要はない。

典型の発動条件

max-flow min-cutによる双対化

配分を最大流で表せても、辺が密すぎて構築できないときは、最小カットの容量を式で書いてみる。集合を固定すると反対側の選択が独立になるなら、ネットワークを持たずに最適値を計算できる場合がある。

subsetを十分統計量へ圧縮するknapsack

選んだ集合が残りの部分へ与える影響が一つの小さな重み和だけで決まるときは、その和を DP の添字にする。同じ和を作る集合のうち、目的値が最良のものを残す。0/1 選択を一次元配列で更新する場合は、参照元を処理前の値に保つ更新方向を確認する。

piecewise-linear minのsweep

整数引数に対する「直線と定数の小さい方」の総和を求めるときは、各項が一度だけ切り替わる時点をまとめ、総傾きと定数和を保つ。切替を登録する添字と、評価の前後どちらで反映するかを一組で決める。

問題固有の要素

色から箱への容量が ijij という積なので、カットを横切る容量は j∑i∈Pij\sum_{i\in P}i と因数分解できる。さらに色の番号の和は最大でも N(N+1)/2N(N+1)/2 であり、供給量の上限とは無関係に小さい。可分な形と、圧縮後の値域の小ささの両方が重要である。

別の問題へ持ち帰る視点は、密なネットワークを諦める前に、カットの式で容量行列が少数の積へ分離できないかを調べること。ただし分離できても、その後に残る状態数が計算可能かは別に確認する。

正当性

整数容量のネットワークの整数フローと合法な収納は、色から箱への流量を収納個数とすることで双方向に対応する。したがって最大流が求める最大収納数である。

色集合 PP を固定すると、各箱の所属側は他の箱と独立に選べ、その最小寄与は min⁡(jk,Bj)\min(jk,B_j) となる。箱側の寄与は k=∑i∈Pik=\sum_{i\in P}i だけで決まるので、同じ kk の色集合のうち色側寄与が最小のものだけを残してよい。

DP は空集合から始め、各色を選ばない場合と一度だけ選ぶ場合を比較する。降順更新により選ぶ遷移の参照元はその色の処理前の値となり、全色の処理後には各 kk の色側最小寄与が得られる。走査では qj≤kq_j\leq k の箱だけが定数側へ切り替わるため、評価時の ak+cak+c は必ず F(k)F(k) に一致する。

よって全 kk に対する dp[k]+F(k)\mathrm{dp}[k]+F(k) の最小値は全カットの最小容量であり、最大流最小カット定理から最大収納数に等しい。

実装上の注意

  • dp[k] は最小カットの色側寄与を最小化する値であり、選択した色の供給量の最大値と混同しない。初期値は dp[0]=S である。
  • 無限大から AiA_i を引く遷移を禁止する。有限値は 0≤dp[k]≤S≤5×10140\leq\mathrm{dp}[k]\leq S\leq5\times10^{14} なので、例えば64 bit 符号付き整数で 2622^{62} を無限大に使える。
  • Ai=Bj=0A_i=B_j=0 がすべてで成り立つ場合も同じ処理でよい。DP の有限値は0、箱はすべて k=1k=1 で切り替わり、答えは0になる。
  • Ai,BjA_i,B_j だけでなく、傾き、定数和、積 akak、答えにも64 bit 符号付き整数を使う。M(M+1)/2M(M+1)/2 は32 bit を超えるので、積を取る前に型を広げる。切替点は浮動小数点を使わず整数除算で求め、qj≤Lq_j\leq L を確認してから配列の添字にする。

復習の核

  • 密な配分問題では、最大流を実行する前にカット容量を書き、片側の集合を固定すると何が独立になるかを見る。
  • 集合を圧縮する際は、反対側から区別されない情報と、圧縮後も最適化して残す値を分ける。今回は番号の和と色側の最小寄与である。
  • 切替点は「直線が定数を厳密に超える最初の整数」。その時点の評価前に全切替を反映する。
  • フローを直接表すネットワークの最小カット値は、最大収納数そのものである。利益から損失を引く別の帰着と取り違えない。

計算量と制約

時間

色の DP は各色で高々 L+1L+1 状態を調べるため O(NL)O(NL)。箱の切替の登録は O(M)O(M)、DP・切替用配列の初期化と全 kk の走査は O(L)O(L) なので、入力処理も含めて全体は O(NL+M+L)=O(N3+M)O(NL+M+L)=O(N^3+M) 時間である。切替点のソートは不要である。

空間

DP と二つの切替用配列は O(L)O(L)。色の入力を保持し、箱の入力は読みながら切替用配列へ加算すれば、全体で O(N+L)=O(L)O(N+L)=O(L) 空間となる。箱の入力もすべて配列に保持する実装では O(N+M+L)O(N+M+L) 空間である。

制約との対応

1≤N≤500, 1≤M≤5×105, 0≤Ai,Bj≤10121\leq N\leq500,\ 1\leq M\leq5\times10^5,\ 0\leq A_i,B_j\leq10^{12}。L≤125250L\leq125250 なので、DP の更新回数は高々 NL=62625000NL=62625000、箱の登録と走査は O(M+L)O(M+L) に収まる。制限は3秒・1024 MiBである。

総供給は S≤5×1014S\leq5\times10^{14}、総箱容量は ∑jBj≤5×1017\sum_jB_j\leq5\times10^{17}。走査中の a≤125000250000a\leq125000250000、ak<1.6×1016ak<1.6\times10^{16} であり、ak+cak+c とそれに DP の有限値を足す計算も64 bit 符号付き整数に収まる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Not Too Many Balls の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最大流・最小カット

主題
  • 最大流・最小カット: 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 最大流・最小カット

    補助タグ: event・値順のオフライン走査 資源軸knapsack DP

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

    学習の位置

    体系上の位置: 最大流・最小カット

    • 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 資源・容量DP — 最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。
    • event順にactive集合を更新する — 値・時刻・座標順にeventを並べ、同値eventの処理順を決めてactive集合を増分更新する。逆向き処理や寄与分解とは不変量が異なるため独立に学ぶ。
    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題