AtCoder Beginner Contest 215 H問題メモ

AtCoder Beginner Contest 215

H - Cabbage Master

• $N$ 品種のキャベツがある
  • 品種 $i$ は $A_i$ 個ある
  • 全てのキャベツは区別できる
• キャベツの出荷先が $M$ 個ある
  • $i$ 番目の出荷先に $B_i$ 個のキャベツを納めるというノルマがある
• 各品種は出荷できる先が決まっていて、$i=1～N,j=1～M$ につき、
  • $c_{i,j}=1$ の時、品種 $i$ のキャベツは出荷先 $j$ に出荷できる
  • $c_{i,j}=0$ の時、品種 $i$ のキャベツは出荷先 $j$ に出荷できない
• どのようにしても全ての出荷先のノルマを同時に満たすことができないようにキャベツを減らしたい
• 減らす個数の最小値と、その時のキャベツの選び方の個数をそれぞれ求めよ
• $1 \le N \le 20$
• $1 \le M \le 10^4$
• $1 \le A_i,B_i \le 10^5$

Hallの結婚定理と、高速ゼータ変換・メビウス変換を組み合わせて解く。

まず、二部グラフのマッチング問題として考える。
キャベツ1玉を1頂点として、左に出荷先、右に品種を置く。

• 二部グラフのマッチング

出荷先      品種
B1=3  o     o  A1=2    この上で、たとえば出荷先1に品種1を出荷可能なら、
      o     o          B1とA1の各頂点間に辺を張る
      o
            o  A2=4
B2=2  o     o
      o     o
            o
B3=4  o
      o     o  A3=4
      o     o
      o     o
            o

頂点数と辺数がとんでもないことになるので実際にこのまま実装はしないが、 理論上はこのグラフで全ての出荷先側の頂点に、辺で繋がった別々のキャベツ頂点を結びつけられれば、ノルマ達成となる。

二部グラフで一方の集合を全てカバーするマッチングが存在するかどうかの判定方法として、Hallの定理がある。

• Hallの結婚定理とその証明 | 高校数学の美しい物語

• 左側から任意の頂点集合を選んできて、$S$ とする
• その中の少なくとも1つと辺でつながった右側頂点の集合を $\Gamma(S)$ とする
• どのように $S$ を選んでも $|S| \le |\Gamma(S)|$ なら、左側頂点を全てカバーするマッチングが存在する

今回の二部グラフでHallの定理を考える場合、各頂点は出荷先・品種のグループ毎にまとめて考えることができる。
たとえば「同じ出荷先の2頂点 $i,j$ で、$i$ が入っていて $j$ が入っていない集合」というのは考える必要が無い。

• 理由
  • $i$ が入っていて $j$ が入っていない頂点集合（$A$ とする）に $j$ を加えても、$\Gamma(A)$ は変わらない
  • Hallの定理では $|A| \le |\Gamma(A)|$ が満たされるかがポイント
  • 一番条件のきつくなる場合さえ考えればよいので、$\Gamma(A)$ が同じなら $|A|$ が最も大きくなる場合だけ見ればよい
  • それは、同じ出荷先なら全ての頂点が入っている集合となる

また、同様に $\Gamma(A)$ となりえるキャベツ側の頂点集合も、同じ品種なら全て含まれるか、含まれないかに限られる。

従って場合分けとしては、「出荷先の集合」「品種の集合」で考えてよいことがわかる。
（もちろん、$|A| \le |\Gamma(A)|$ を評価する際には、頂点集合としてのサイズで評価する必要がある）

$N$ が小さいので、品種の部分集合を全探索することを考える。
これは、Hallの定理において $\Gamma(A)$ の方を全探索していることになる。

考察の上で、「品種の集合」「出荷先の集合」と、「二部グラフ上でそれらに属する頂点集合」を区別したい。

品種  A1=3  A2=2   A3=4    品種の集合 {1, 3}
      ooo   oo     oooo                 ↕
頂点  123   45     6789    頂点の集合 {1,2,3,6,7,8,9}

そのため、以下を定義する。

• 品種の部分集合の1つを $T$ とする
  • $T$ に含まれる頂点集合を $Cab(T)$ とする
  • $\displaystyle |Cab(T)| = \sum_{i \in T} A_i$
• 出荷先の部分集合の1つを $S$ とする
  • $S$ に含まれる頂点集合を $Shp(S)$ とする
  • $\displaystyle |Shp(S)| = \sum_{i \in S} B_i$

また、出荷先の集合を $S$ とした時、 その中の少なくとも1つに出荷できるキャベツの品種の集合を $\gamma(S)$ と表すことにする。
（Hallの定理における $\Gamma$ の概念を、品種と出荷先の集合にも適用している）

ノルマ達成を阻止する最小個数は、以下で求められる。

まず、品種の集合 $T$ を決め打つ。

Hallの定理より、ノルマ達成には $\gamma(S)=T$ になるような全ての $S$ で、$|Shp(S)| \le |Cab(T)|$ が成り立つ必要がある。
そのような $S$ のうち、$|Shp(S)|$ が最大になるものだけ確認すればよい。

$T$ に対して「$\gamma(S)=T$ になる $S$ の集合」を $\mathbb{S}_{T}$ と表すことにする。

達成を阻止するためには、少なくともどれか1つの $T$ につき、 $\max_{S \in \mathbb{S}_T}(|Shp(S)|) \gt |Cab(T)|$ となればよい。

そのために減らす個数は $|Cab(T)| - \max_{S \in \mathbb{S}_T} (|Shp(S)|) + 1$ なので、 全ての $T$ に対してこれを計算し、その最小値が答えとなる。

各 $T$ に対する $\mathbb{S}_T$ を知りたい。
ただ、ぴったり $\gamma(S)=T$ になる $S$ を求めるのは難しい。$T$ によっては存在しないこともある。

ここで、ぴったりでなくても $\gamma(S) \subseteq T$ となる $S$ を考えても問題ない。

なぜなら、$|Cab(T)| - |Shp(S)| + 1$ は、同じ $S$ に対しては、ぴったり $\gamma(S)=T$ になる $T$ で最小となる。 $T$ を全探索して最小値を取るため、どこかでは正しい値が求まり、嘘の値より優先される。

よって、より計算しやすい方で考える。
$\gamma(S) \subseteq T$ が成り立つ $S$ の集合を $\mathbb{S}'_T$、その中での $|Shp(S)|$ の最大値を $smax[T]$ とする。

これは、以下のように求められる。

ある品種集合 $T$ に対して、それに含まれない品種も受け入れる出荷先は、$\mathbb{S}'_T$ に含まれ得ない。
逆に、$T$ に含まれる品種しか受け付けない出荷先は含んでもよく、$smax[T]$ を求める上では含めるなら含むのがよい。

bit集合で考える
                      T  101101
出荷先1が受け付ける品種  010100    × S_Tには含まれない
出荷先2が受け付ける品種  101001    ○ S_Tには含まれ得る

従って、出荷先ベースで考えて、ある出荷先 $i$ が例えばbit集合で 101001 の品種を受け付けるとしたとき、 この上位集合、つまり 101101 や 111011 等に対して、$smax[T] += B_i$ としてやればよい。

この操作は高速ゼータ変換で可能となる。
高速ゼータ変換にも2種類あるが、上位集合の方に足し込んでいく方を使う。

• 高速ゼータ変換 高速メビウス変換
• 高速ゼータ・メビウス変換 - Mister雑記

• $smax[T]$ を0で初期化
• 出荷先 $i$ がたとえば品種集合 001101 を受け付けるとした場合、$smax[001101] += B_i$ とする
• 高速ゼータ変換を適用する

これで目的の $smax[T]$ が得られた。

$d = \min_{T} (smax[T] - Cab(T) + 1)$ を計算すれば、$d$ が減らすべき最小個数となる。

ただし、$d \le 0$ となった場合は1個も減らさなくてもはじめから不可能なので、0個となる。

減らす個数すら難しかったのに、パターン数まで求めないといけない。

最小値 $d$ を達成する $T$ は1通りでなく、複数の $T$ で同じ値になる可能性がある。

$d$ を達成する $T$ の集合を、$\mathbb{T}$ とする。

$T$ が1通りの場合なら簡単で、 $|Cab(T)|$ 個のキャベツから減らす $d$ 個を選べばよいので、${}_{|Cab(T)|}C_{d}$ 個となる。
（全てのキャベツは区別されるという問題設定は、ここで「品種毎に何個使うか」を考えなくてよいためにあったのだ）

ただ $T$ が複数あると互いに共通する品種を持っている可能性がある。

• $\mathbb{T} =${ {1,2,3}, {1,2,4}, {1,5} } のとき、以下のいずれかを行えばよい
  • ① 品種 {1,2,3} から $d$ 個選ぶ
  • ② 品種 {1,2,4} から $d$ 個選ぶ
  • ③ 品種 {1,5} から $d$ 個選ぶ

この時、単純にさっきの二項係数を足し合わせると、 「①で品種3が選ばれず、1,2のみから $d$ 個選ばれたパターン」と 「②で品種4が選ばれず、1,2のみから $d$ 個選ばれたパターン」が重複してしまう。

さらにその中でも「1のみから $d$ 個選ばれたパターン」は③とも重複する可能性があって……と複雑になる。

包除原理っぽい考え方を持ってくると、以下のようにすれば重複を省けそうである。

• $pattern[T]$: 品種集合 $T$ から「それぞれの品種を必ず1つは使い」$d$ 個選ぶ方法の数
• $flag[T]$: 品種集合 $T$ の中から $d$ 個選ぶと、ノルマ達成を阻止できるかフラグ

$(flag[T]=True)$ の $T$ に対し $pattern[T]$ を足し合わせると、重複を除いて答えが導ける。

集合の包含関係で包除原理を行いたい際、メビウス変換が使える。
（これは、先ほど出てきたゼータ変換を元に戻す操作とも解釈できる）

$pattern[T]$ を、品種集合 $T$ からの $d$ 個の選び方 ${}_{|Cab(T)|}C_{d}$ で初期化し、 メビウス変換を適用すると、目的の値となっている。
（メビウス変換も2種類あるが、部分集合を引いていく方）

一見、メビウス変換を使わなくても「あらかじめ各品種から1つずつ選んでから残りの選び方を考える」方法で上手くいくかも、 と思えるが、今回は全てのキャベツを区別するため、それだと重複が発生し、いずれにしろ包除原理が必要となる。

たとえば「品種 {1,2,3} から $d$ 個選ぶ」ことは、以下のいずれかを行うことと等しい。

• 品種 {1,2,3} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ
• 品種 {1,2} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ
• 品種 {1,3} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ
• 品種 {2,3} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ
• 品種 {1} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ
• 品種 {2} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ
• 品種 {3} のそれぞれの品種を必ず1つは使って、$d$ 個選ぶ

要は、{1,2,3} の部分集合 $T'$ 全てについて、$flag[T']$ をTrueにすればよい。

その際、{1,2,4} でも {1,2} や {1} などを部分集合に含むが、 1つの $T'$ につき全体で $pattern[T']$ を足すのは1回とすれば、重複がのぞける。

これは、以下のようなフラグを初期化して

• $flag[T]=$ $\mathbb{T}$ に含まれる $T$ は1、他は0

ゼータ変換（今度は、部分集合の方に足し合わせていく方）を適用すると、 $flag[T'] \gt 0$ となっている $T'$ が、「$\mathbb{T}$ に含まれる何らかの $T$ の部分集合になっている」とわかるので、 それらについて $pattern[T']$ を足し合わせれば、答えとなる。

Python3