与えられたペア \((x,y)\) それぞれについて、魔法使い \(x,y\) の強さは \(\min (b_x,b_y)\) 以上である必要があります。以降、この条件を満たすように操作を行ってあるものとします。

自分の強さよりも倒そうとしているモンスターの強さが大きいような魔法使いの集合を \(X\)、そうでない魔法使いの集合を \(Y\) とします。まだ良いペアでないようなペア \((x,y)\) は、(必要なら \(x,y\) を入れ替えることで)魔法使い \(x\) が \(X\)、魔法使い \(y\) が \(Y\) に属していて、このペアを良いペアにするには魔法使い \(x,y\) のうち少なくとも一方の強さを \(b_x\) 以上にする必要がある、と記述できます。

以上を考えると、すべてのペアを良いペアにするために必要な操作回数の最小値は以下のような有向グラフの \(S-T\) 最小カットに等しいといえます。

• 頂点集合は以下のように記述される頂点からなる
  • 頂点 \(S,T\)
  • 各 \(x \in X\) に対し、\(x\) に対応する頂点
  • 各 \(y \in Y\) と整数 \(i \, (1 \leq i \leq 100)\) に対し、組 \((y,i)\) に対応する頂点
• 辺集合は以下のように記述される辺からなる
  • \(S\) から \(x\) に対応する頂点への重み \(b_x-a_x\) の辺
  • \((y,i)\) に対応する頂点から \(T\) への重み \(1\) の辺
  • \(i\geq 2\) に対し、\((y,i)\) に対応する頂点から \((y,i-1)\) に対応する頂点への重み \(\infty\) の辺
  • 良いペアにするべきペア \((x,y)\) に対し、\(x\) に対応する頂点から \((y,b_x-a_y)\) に対応する頂点への重み \(\infty\) の辺

実際、ペア \((x,y)\) ごとに \(x\) の強さを \(b_x\) 以上にすることが \(S\) から \(x\) に対応する頂点への辺に、\(y\) の強さを \(b_x\) 以上にすることが \(i=1,\ldots,b_x-a_y\) それぞれに対する \((y,i)\) に対応する頂点から \(T\) への辺に対応します。

計算量を考えます。\(a_i\) や \(b_i\) の上限を \(A\) とすると、このグラフに対する \(S-T\) フローは流量が \(\mathrm O(NA)\)、辺数が \(\mathrm O(N^2 + NA)\) なので、\(\mathrm O(N^3A + N^2A^2)\) となります。