ABC 273 G — Row Column Sums 2

考察

rowを上から埋める途中、各columnのremaining sumは0,1,2のいずれかで、同じremaining sumを持つcolumnsは将来について交換可能である。

remaining-2 columns数xが分かれば、remaining-1 columns数yは total column remainder−2x=ΣC−Σ_{k≤i}R_k−2xから一意に決まる。

棄却する候補: 各rowのN個のentriesまたは各column remainder vectorを列挙する。

column identitiesを保持すると状態数が指数的になり、matrix entriesの配置列挙も巨大である。

採用する候補: dp[i][x]をi rows後にremaining sum 2のcolumnsがx個であるwaysとし、R_i∈{0,1,2}ごとのconstant patternsを組合せ係数付きで遷移する。

yもxから復元でき、一rowのsumが高々2なので使うcolumn種別のpatternが定数個しかない。

R_i=1ではremaining 2または1のcolumnを一つ選び、R_i=2では一columnへ2、または二columnsへ1ずつ置く全patternを数える。

各patternのmultiplicityはx、y、C(x,2)、C(y,2)、xyのいずれかで、column labelsを失ったstateでも正確なwaysを復元できる。

具体的な遷移は次の表になる。行を i 本処理した時点の残余総和 T_i=ΣC−Σ_{k≤i}R_k、y=T_i−2x とし、次行の和 R_{i+1} を使う。

次行の和配置次の x係数
0何も置かないx1
1残余2の列へ1x−1x
1残余1の列へ1xy
2残余2の一列へ2x−1x
2残余2の二列へ1ずつx−2x(x−1)/2
2残余2と1の列へ1ずつx−1xy
2残余1の二列へ1ずつxy(y−1)/2

ΣR≠ΣC なら答えは0。そうでなければ dp[0][#{j:C_j=2}]=1、他は0とし、表の係数を掛けて加算する。答えは dp[N][0]。行処理後の総残余が0なので、この状態では残余1の列も残らない。

典型の発動条件

exchangeable objectsの個数DP

発動条件: 個体identityではなく少数の状態classごとの個数だけが将来遷移を決めるとき。

columnsをremaining 0/1/2に分類し、remaining-2の個数xだけを明示stateにする。

小さいrow sumの組合せ遷移

発動条件: 一stepで配る総量が小定数で、選ぶclass patternを全列挙できるとき。

0,1,2 unitsの配り方を列挙し、該当columnsの選択数をbinomial coefficientsで掛ける。

問題固有の要素

ΣR≠ΣCなら即0で、等しい場合は最終x=0ならremaining totalも0なのでyも自動的に0となりdp[N][0]が答えになる。

別の問題へ持ち帰る視点: 圧縮stateで省いたclass countは保存量のconservation lawから復元し、終端条件も同じ保存量で簡約する。

正当性

一行の和は0,1,2だけなので、その行を置く前の各列の残余は0,1,2のいずれかである。残余2の列数と残余1の列数を状態とすると、同じ残余の列は交換対称である。一行の2を一列へ置く場合と二列へ1ずつ置く場合を、それぞれ選ぶ列の組合せ数で遷移すれば、各行の配置を全て一回ずつ数えられる。残余総和から片方の列数は復元できるため二次元DPに圧縮でき、全行処理後の残余0状態が答えとなる。

実装上の注意

  • 式から得るx,yが0…Nの範囲外ならそのstateを無効とし、組合せ係数もnegative countへ適用しない。
  • row indexごとにold/new arraysを分けてzero clearし、全waysをmodulo 998244353で加算する。

復習の核

  • 残容量が少数値しか取らない割当問題は、itemsのidentityを捨ててcapacity class countsへ圧縮する。
  • stateを一変数まで減らす際は、残りのclass countが総和保存から一意に戻ることを式で示す。

計算量と制約

時間

O(N²)、行番号×remaining2列数、remaining1数は総残量から復元。

空間

O(N)、rolling行DP。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5000; 0 \leq R_i \leq 2; 0 \leq C_i \leq 2; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Row Column Sums 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: DPの最小十分状態

    補助タグ: 組合せ係数・数え上げ

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

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

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

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題