AtCoder Beginner Contest 332 G問題メモ

AtCoder Beginner Contest 332

G - Not Too Many Balls

• $N$ 色のボールがたくさんある。色 $i=1,...,N$ のボールは $A_i$ 個ある
• $M$ 個の箱がある。箱 $j=1,...,M$ にはボールを $B_i$ 個まで入れられる
• 色 $i$ のボールは、箱 $j$ に $i \times j$ 個までしか入れられない
• 箱に入れられるボールの最大数を求めよ
• $1 \le N \le 500$
• $1 \le M \le 5 \times 10^5$
• $0 \le A_i,B_i \le 10^{12}$

$M$ が十分に小さければ、最大流問題で解ける。

    ボール  箱
      ①--->①        ボールと箱を結ぶ辺の容量は、頂点番号の積
  A1↗ \＼  / ＼B1
  ／    \ ×    ↘
ⓢ       X  ②-B2-ⓣ
  ＼    / ×    ↗
  A2↘ /／  \ ／B3
      ②--->③

でもさすがに $M=5 \times 10^5$ は無理。
なので、ボール-箱間のコストが法則的なことを使わないといけない。
最大フロー最小カット定理 より、最小カットの考え方で解く。

最小カットは、以下で定義される。

• 全頂点を $S,T$ グループに分ける
• 始点ⓢと終点ⓣはそれぞれ $S,T$ 固定
• $Sグループの頂点→Tグループの頂点$ に張られた辺の容量の合計が「カット」
• $S,T$ への分け方を上手く決めた場合のカットの最小値が「最小カット」

カットとなり得る辺を分類すると、以下のようになる。

  a)     b)    c)
  ↓     ↓    ↓
    ボール  箱
      ●    ●          ○:Sに属する頂点
  A1↗     ↗           ●:Tに属する頂点
  ／      /      
ⓢ       /  ○-B2->ⓣ
        /
       /
      ○--->●

ここで、

• $U:={1,2,...,N}$ 全てのボール頂点からなる集合
• $V:={1,2,...,M}$ 全ての箱頂点からなる集合
• $P:=S$ に属するボール頂点の集合
• $\overline{P}:=T$ に属するボール頂点の集合
• $Q:=S$ に属する箱頂点の集合
• $f(A):=$ 頂点集合 $A$ に属する頂点の、番号の総和

とする。

$P,Q$ を固定した時のカットを式で表すと、以下になる。これを最小化したい。

• $\displaystyle \sum_{i \in \overline{P}}A_i + \sum_{i \in P}\sum_{j \in \overline{Q}}i \times j + \sum_{j \in Q}B_j$ …(1)

真ん中のb)を示す項 $\sum_{i \in P}\sum_{j \in \overline{Q}}i \times j$ は、 分配法則によってまとめて $\sum_{j \in \overline{Q}} f(P) \times j$ とできる。

すると、式(1)の3項のうち右2項は $\sum_{j \in \overline{Q}} f(P) \times j + \sum_{j \in Q}B_j$ となり、各 $j$ は $Q$ と $\overline{Q}$ のどっちかには属するので、

• 頂点 $j$ が $Q$ に属するとき、$B_j$
• 頂点 $j$ が $Q$ に属しないとき、$f(P) \times j$

結局、$f(P)$ が決められたとき「各 $j$ について $B_j,f(P)j$ のどっちか小さい方を選べばよい」ということになる。

左の1項 $\sum_{i \in \overline{P}}A_i$ を考える。これも、上記と同じく $f(P)$ を軸にまとめたい。

• $g(t)=f(\overline{P})$ が $t$ となるような $\overline{P}$ における、$\displaystyle \sum_{i \in \overline{P}}A_i$ の最小値

とすると、これは $N \times f(U)=O(N^3)$ のDPで事前計算できる。
すると、$f(\overline{P})=f(U)-f(P)$ なので、$f(P)$ を決めると求めることができる。

$f(P)$ を固定することでカットが計算できるようになったので、あとは実際に $f(P)=k$ として $k=0,1,...,f(U)$ を試す。
「$k \times j \gt B_j$ となるような $j$ の集合」を $Q$ として、

• $g(f(U)-k) + k \times f(\overline{Q}) + \sum_{j \in Q}B_j$

がカットとなり、全ての $k$ を試した上での最小値が答え。

$k$ が増加する毎に $Q$ は増えていく一方なので、 $f(\overline{Q})$ と $\sum_{j \in Q}B_j$ は、 はじめ $Q=\phi,\overline{Q}=V$ からはじめて順次 $Q$ に移していけばよい。
$k=\lfloor \frac{B_j}{j} \rfloor$ であるような $j$ を $k$ の処理が終わったタイミングで $Q$ に移していけば、$k$ を全て試す過程を通して $O(M)$ で管理できる。

全体で $O(N^3+M)$

Python3