ABC 424 G — Set list

考察

選択songを必要人数Bの降順に並べた時、割当可能性は全prefix kについてΣ_{first k}B≤R_k=Σ_i min(A_i,k)である。この条件は各idol capacityを持つbipartite degree sequenceの必要十分条件になる。大きいBからk曲選んだprefixで必要な延べ人数sがR_k以下なら、全kでのGale型条件が保たれ、capacityの大きいidolから割り当てる帰納構成が可能である。

採用する候補: B降順songを、選択数k・必要人数累積sのknapsack DPで選ぶ

prefix feasibilityをsong追加時のs≤R_kとして逐次保証し、excitement最大化を有限状態で解ける。

棄却する候補: 総必要dance回数ΣB≤ΣAだけを確認する

一部songが多人数を要求すると同じidolを一曲に重複配置できず、prefix条件を満たさない場合がある。

songsをB降順sortしR_kを前計算する。dp[k][s]を処理済みsongsからk曲選び全prefix条件を満たす最大C和とし、skipまたはchooseで(k+1,s+B_j)へ遷移する際s+B_j≤R_{k+1}を課す。全dp最大を出す。

典型の発動条件

degree sequence feasibility

発動条件: 各itemがB_j個の異なるresourceを使い、resource iの総capacityがA_iである。

需要降順prefixとΣmin(A_i,k)のmajorization条件で割当可否を特徴付ける。

制約付きknapsack DP

発動条件: songごとに選択/非選択し、選択数と需要和がprefix feasibilityを決める。

(k,s)状態でexcitementを最大化し、R_kでinvalid stateを切る。

問題固有の要素

誰が踊るかをDPに含めず、選択songのB列がcapacity列に割当可能かをprefix不等式へ完全に射影できる。

別の問題へ持ち帰る視点: 複雑なassignmentはmajorization条件があればitem selection DPから分離できる。

正当性

選曲をB降順にすると任意k曲の最大需要は先頭k曲の需要和である。idol iはk曲へ高々min(A_i,k)回参加できるためprefix条件は必要。bipartite b-matchingの容量cutを全song部分集合へ見ると、需要最大集合がprefixなのでこれらの条件だけで全cutを満たし十分。処理順もB降順に固定し、曲を追加する時だけ新prefixを検査すれば過去prefixは不変。DPは全可行選曲集合を一回ずつ検査しC和最大を保つ。

実装上の注意

  • 同じj iterationでsongを二度選ばないようcopyまたはk,s降順更新し、-INF状態をskipする。B=0も扱う。

復習の核

  • N,M小でsong subsetとidol assignment max-flowを全比較しprefix条件を検証する。

計算量と制約

時間

idol N、song M、総参加枠 S=ΣA_i≤NM。容量表 O(NM)、dp遷移 O(M²S)(song×選曲数×総必要人数)、sort O(Mlog M)。

空間

rollingで O(MS)、R表O(M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 100; 1\leq M\leq 100; 0\leq A_i\leq M; 0\leq B_i\leq N; 0\leq C_i\leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Set list の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能
    • 二部matching・Hall・Kőnig: 二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。

    主タグ: 資源軸knapsack DP

    補助タグ: 二部matching・Hall・Kőnig

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

    学習の位置

    体系上の位置: 資源・容量DP

    • 資源軸の上限と更新順を選び、選択の重複を避けられる。

    先に読む単元:

    • 二部matching・Hall・Kőnig — 二部グラフの彩色と成分構造で得た考え方と実装を再利用し、二部matching・Hall・Kőnigの発動条件・正当化・境界を重複なく学ぶ。
    • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。

    この解説で扱わないこと:

    • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題