ABC 215 H — Cabbage Master

考察

会社 j の B_j 個の注文を区別可能な一個注文へ分けると、各注文を許可品種のどれか一個へ割り当てる二部マッチングとして充足可能性を表せる。 Hall の条件は、全注文部分集合 T に対する供給量 f(S_T) と |T| の比較であり、同じ許可集合を持つ注文をまとめれば品種部分集合 S だけの条件へ移せる。 g(S) を許可品種集合が S に含まれる一個注文の総数とすると、全注文を満たせる条件は全 S で f(S)−g(S) が非負であることになる。一方、破壊対象は注文が存在するg(S)>0の集合に限り、d=min_{g(S)>0}(f(S)−g(S))とする。実行可能ならその最小集合からd+1個食べられる(g(S)≥1よりd+1≤f(S))。既に不可能ならX=0、そうでなければX=d+1である。

棄却する候補: 食べるキャベツの各組合せについて、残りの供給から全注文を満たせるか最大流で判定する。

キャベツ個体の選択肢が膨大で、候補ごとにフローを解く列挙はできない。

採用する候補: Hall の定理で最小余裕を品種部分集合上の f(S)−g(S) に変換し、subset zeta・Möbius 変換で最小個数と選び方を集約する。

品種数 N は 20 以下なので全品種部分集合を扱え、会社の大きな注文数は許可マスクへの重みとしてまとめられる。

許可マスク別注文数をsubset zeta変換して実際の注文数g(S)を求める。全SのHall条件で実行可能性を判定し、不可能なら(X,Y)=(0,1)。可能ならg(S)>0に限った最小余裕dと集合族F={S:g(S)>0かつf(S)−g(S)=d}を作る。X=d+1とし、C(f(S),X)のMöbius反転で台集合がちょうどSの個体選択数h(S)を求める。Fのsuperset zeta変換が正のSについてh(S)を一度ずつ加える。

典型の発動条件

Hall の定理による供給可能性判定

発動条件: 複数種類の資源を、各要求が受け入れる種類のいずれかへ一対一に割り当てるとき。

注文集合の近傍品種が持つ総供給量と注文数を比較し、品種部分集合ごとの余裕へ変形する。

subset zeta・Möbius 変換

発動条件: ビット集合ごとに部分集合からの重み総和や、包含で集約された個数から正確な台集合別個数を求めるとき。

許可マスク別注文数から g(S) を作り、C(f(S),X) から選択品種集合がちょうど S の方法数を復元する。

問題固有の要素

最小個数 X の選択が称号を壊すのは、選んだ品種の台集合が f(S)−g(S) の最小化集合のどれかに含まれる場合に限られる。

別の問題へ持ち帰る視点: 最小障害集合が複数あるときは、個体選択をその台集合で分類し、最小化集合族との包含関係を集合変換で判定する。

正当性

Hall条件は全品種subset Sで供給f(S)≥注文g(S)。注文のある集合の最小余裕dを一つ破るにはd+1個食べる必要があり、その集合内で食べれば達成可能。食べる個体集合の台SをMöbiusで一意分類し、最小余裕集合のどれかに含まれる台だけ合計すると複数witnessによる二重計上がない。

実装上の注意

  • 会社 j は B_j 個の注文を実際に展開せず、許可品種マスクに重み B_j を足して g の基礎配列を作る。
  • X=0 なら空選択の一通りだけを返し、X>0 では C(f(S),X) の Möbius 反転と最小集合の上位集合判定の向きを混同しない。

復習の核

  • 注文部分集合が巨大なら、近傍がある品種集合 S に含まれる注文を全て選ぶのが最悪になることから量化対象を入れ替える。
  • 選び方の重複は「選択に使った品種集合がちょうど S」で分割し、いずれかの最小化集合に含まれるかで一度だけ数える。

計算量と制約

時間

品種N≤20、会社M、供給総和A。mask作成O(NM)、subset/superset zeta・Möbius O(N2^N)、二項係数階乗表O(A)。

空間

mask表O(2^N)、階乗O(A)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 20; 1 \leq M \leq 10^4; 1 \leq A_i \leq 10^5; 1 \leq B_j \leq 10^5; c_{i, j} \in \lbrace 0, 1 \rbrace; For every 1 \leq j \leq M, there exists 1 \leq i \leq N such that c_{i, j} = 1.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Cabbage Master の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 二部matching・Hall・Kőnig

主題
  • 二部matching・Hall・Kőnig: 二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。
追加で学ぶ技能
    なし
    既習技能
    • subset zeta・Möbius変換: Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 二部matching・Hall・Kőnig

    補助タグ: subset zeta・Möbius変換

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

    学習の位置

    体系上の位置: 二部matching・Hall・Kőnig

    • 二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。

    先に読む単元:

    • 二部彩色と成分構造を扱う — 無向グラフを探索できることを前提に二部性と部の交換対称性を扱い、連結二部グラフの彩色重複も補正する。
    • subset zeta・Möbius変換 — 集合上の包除原理・部分集合・bitmask状態DPで得た考え方と実装を再利用し、subset zeta・Möbius変換の発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題