ABC 442 F — Diagonal Separation 2

考察

条件を満たす盤面は、各行の白 prefix 長 A_i が 0..N で、A_1≥A_2≥…≥A_N となる階段形と必要十分に対応する。各行が白 prefix・黒 suffix であることに加え、列条件は下の行ほど白 prefix が長くならないことと同値である。D_{i,j+1} は境界を一マス動かす差分から O(1) で更新でき、遷移の min_{k≥j} も右からの累積最小で得られる。

採用する候補: 各行 i と境界 j の塗り替え費用 D_{i,j} を前計算し、dp[i][j]=D_{i,j}+min_{k≥j}dp[i-1][k] を suffix minimum で更新する。

列方向の条件は境界列の単調性へ完全に吸収され、行費用と前段 suffix minimum をともに一行 O(N) で列挙できる。

棄却する候補: 白黒を各マス独立に選び、完成後に行・列条件を検査する。

2^{N^2} 通りの盤面があり、条件を後から判定する方針では N≤5000 を扱えない。

各行について j=0..N の塗替え費用を累積個数で求める。前行 dp の suffix minimum を作り、全 j を更新して rolling array へ格納し、最終行の最小値を答える。

典型の発動条件

単調境界 DP

発動条件: 各行が一つの境界で二色に分かれ、隣接行の境界に単調制約があるとき。

境界位置を状態にして suffix minimum で遷移する。

問題固有の要素

二次元の局所条件を各行の境界列という一次元単調列へ置き換えると、盤面全体の自由度が大幅に減る。

別の問題へ持ち帰る視点: DP 遷移が区間 min の形なら、各状態から配るより前段の累積 min を先に作る。

正当性

可行盤面は各行白prefix長a_iが非増加の階段に一意対応する。行cost[i,j]はその行を白j個・残り黒へする変更数で、各セルの変更費用は行間独立。dp[i,j]は前行末尾k≥jの最小へその行costを足す式となる。suffix minimumはこの全k最小を一度に返すため、通常DPと同じ値を保つ。最終j最小が全階段を網羅する。

実装上の注意

  • j=0 と j=N の全黒・全白を含める。A_{i-1}≥A_i の向きに合わせ、suffix と prefix の選択を逆にしない。

復習の核

  • 列条件から A_i の単調方向を図で導き、D の境界定義と dp の k≥j が一致するかを確認する。

計算量と制約

時間

N×N。各行の全切れ目cost、suffix minima、dp更新はO(N)、全体 O(N²)。

空間

盤面保存O(N²)、rollingDPと行costの追加領域 O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5000; N is an integer.; S_i is a string of length N consisting of . and #.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Diagonal Separation 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DP遷移を因数分解・集約して加速する

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

      主タグ: DP遷移の集約・高速化

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

      学習の位置

      体系上の位置: DP遷移を因数分解・集約して加速する

      • 素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。

      先に読む単元:

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

      • 固定線形遷移の巨大回累乗。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題