ABC 295 Ex — E or m

考察

行の左prefixと列の上prefixの長さをそのまま選ぶと、同じ完成グリッドを複数の選択で表せるため重複する。列prefixを可能な限り伸ばす標準形を考える。行 i の左から最初の0より前は行prefixで覆え、それ以降の1は列prefixで覆う必要がある。

上から行を処理し、maskのbit j を「列 j はここまで全行で1なので、列prefixを次行へ伸ばせる」とする。初期は全bitが1、dp[all]=1。現在行の実際のbit列 b を選んだ後は newmask=mask AND b。既にmaskのbitが0の列へ1を置くには、その列までの全マスが1で、行prefixで覆えることが必要十分である。

素朴には各maskから2^M個のbを試す。次の分類なら列方向の一回のsweepへまとめられる。bがmaskの部分集合なら、列ごとにbit1を残すか0へ落とす遷移で処理できる。それ以外は「maskで0だがbで1となる最も右の列 j」が一意に存在する。列0,…,jは全て1、それより右ではbはmaskの部分集合でなければならない。

各行の開始時の dp を保存し、work=dp とする。j=0,…,M−1 の順に、入力文字に許される選択で全maskを走査して次配列を作る。

0を置ける: next[mask & ~(1<<j)] += work[mask]
1を置ける、かつ maskのbit j=1: next[mask] += work[mask]
列0,…,jを全て1にできるなら:
    maskのbit j=0 の全maskについて next[mask] += dp[mask]
work=next

最後の加算は新たなprefixケースの開始である。prefix内は全て1なのでold maskのbitは変わらず、未処理の後ろのbitもそのまま。必ず行開始時の dp から加え、既に遷移した work から加えない。後続sweepではmaskが0の位置に1を置けないため、jが最も右の新しい1である条件も保たれる。

prefixを全て1にできるかは、そこまで固定0がないかを一つのbooleanで更新する。各列の全mask走査を O(2^M) に抑え、全体 O(NM2^M)、空間 O(2^M)。全行後の全maskの和が答えであり、最終maskが0でも、既に列prefixが停止した合法グリッドなので除外しない。

持ち帰る典型は、同じ構成を持つ対象を標準形へ寄せ、残る候補を一意な境界で分類してsubset変換へまとめることである。

典型の発動条件

bitmask frontier DP

発動条件: 幅が小さい格子を行単位で処理し、将来に影響する境界だけを保持する。

各列が上から伸長可能かをmaskにする。

subset zeta transform

発動条件: 全maskからその部分集合への和が必要。

行遷移の多数の部分集合和をO(M2^M)で求める。

問題固有の要素

行・列prefixの長さの選び方は一意ではないが、完成グリッドの「列の最初の0まで」という最大の列prefixは一意に決まる。行の合法性はこの標準形で判定し、行遷移はmaskの外に置く最も右の1で排他的に分類する。

別の問題へ持ち帰る視点: 構成方法の数と完成対象の数を区別し、標準形と一意な境界を定義してからsubset変換へまとめる。

正当性

列prefixをその列の最初の0の直前まで伸ばす標準形を選べる。各行で行prefixの外にある1が全て上から伸びる列で覆われることが必要十分なので、maskと現在行bから合法性を判定し、次maskをmask AND bとしてよい。bがmaskの部分集合の場合と、maskで0だがbで1の最も右の列jを持つ場合は排他的かつ全てを覆う。後者はprefix全1と後ろのsubsetを一通りだけ処理する。列sweepの加算はこの分類に一致するため完成グリッドを一度ずつ数え、固定文字に許される選択だけを行うので入力との整合も保つ。

実装上の注意

  • 初期maskは全1、最終解は全maskの総和。0のmaskも合法になり得る。
  • 各列のnextを0で初期化し、0/1の許可を入力文字から決める。prefixケースは行開始時のdpから加える。
  • prefixに固定0が一つでもあれば、その列以降のprefixケースは追加できない。法998244353で加算する。

復習の核

  • 小格子の全?埋めと比較し、全0・全1、固定値が遷移を遮る行、M=1を確認する。

計算量と制約

時間

O(NM2^M)。各行でsubset zeta sweepとprefix別遷移を行う。

空間

O(2^M)。行DPをrollingする。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: N and M are integers.; 1 \le N,M \le 18; X is a grid with N rows and M columns consisting of 0, 1, and ?.

出典

分類・前提・執筆情報

掲載状態: 収録済み

E or m の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: subset zeta・Möbius変換

主題
  • subset zeta・Möbius変換: Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • frontier/profile DP・境界状態圧縮: 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。

    主タグ: subset zeta・Möbius変換

    補助タグ: frontier/profile DP・境界状態圧縮

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

    学習の位置

    体系上の位置: subset zeta・Möbius変換

    • Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題