ABC 311 E — Defect-free Squares

考察

正方形を左上・右下の二点で列挙すると候補が多いが、右下マスを固定すると、存在する辺長は 1 から最大値まで途切れない。よって最大辺長一つが個数も表す。右下 (i,j) の正方形を一段拡張するには、上・左・左上を右下とする三つの正方形がすべて必要で、最小の辺長がボトルネックになる。穴マスでは dp=0、通常マスでは dp=min(dp_up,dp_left,dp_diag)+1 とすれば、新たに加わる下辺・右辺も三小正方形の和で覆われる。dp[i][j]=k なら同じ右下を持つ辺長 1..k がすべて有効なので、全 dp の総和が重複のない答えになる。

採用する候補: 各マスを右下とする穴なし正方形の最大辺長を、上・左・左上の最小値+1 で DP する。

各正方形を右下で一意に分類でき、最大辺長 k がその右下からの k 個の正方形をまとめて数えるため O(HW) になる。

棄却する候補: 各左上マスと辺長を列挙し、二次元累積和で穴数を判定する。

一回の判定は O(1) でも候補が Θ(HW min(H,W)) あり、3000×3000 では多すぎる。

穴を boolean grid に記録し、上と左に 0 の番兵行列を置く。行優先で、穴なら 0、そうでなければ三近傍の min+1 を計算して 64 bit の答えへ加算する。

典型の発動条件

最大サイズ DP で全サイズを数える

発動条件: 固定した端点に対する有効サイズが 1..k の prefix をなす図形を数えるとき。

端点ごとの最大サイズを求め、その値自体を個数として足す。

最大正方形の三近傍遷移

発動条件: grid 上で全マスが条件を満たす正方形を扱うとき。

右下を固定し、上・左・左上の最大辺長の最小値を使って一段拡張する。

問題固有の要素

「最大を求める DP」がそのまま「全部を数える」答えになるのは、辺長に関する下方閉性があるためである。

別の問題へ持ち帰る視点: 数え上げ候補がサイズで入れ子なら、端点ごとの最大有効サイズへ圧縮できないかを見る。

正当性

右下(i,j)の最大正方形は、穴なら0、空きなら上・左・左上最大長の最小+1。必要十分の領域包含でこの式が成立する。最大長kなら同じ右下の辺長1..kが全て存在し、各正方形は右下一意なのでkを足すと全個数。

実装上の注意

  • 答えは最大で HW min(H,W) 級なので 64 bit を使う。穴座標の 1-index/0-index と番兵行・列を揃える。

復習の核

  • 数えたい対象を一意な端点へ割り当て、サイズ集合が連続かを確かめる。三近傍の min が必要な理由は図に一段拡張を書いて確認する。

計算量と制約

時間

H×W、穴数N。読込・DP O(HW+N)。

空間

盤面穴flag O(HW)、rolling dp作業O(W)、全DP保存ならO(HW)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq H, W \leq 3000; 0 \leq N \leq \min(H \times W, 10^5); 1 \leq a_i \leq H; 1 \leq b_i \leq W; All (a_i, b_i) are pairwise different.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Defect-free Squares の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: グリッド・多次元表の局所DPを設計する

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

    主タグ: DPの最小十分状態 グリッド・多次元表の局所DP

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

    学習の位置

    体系上の位置: グリッド・多次元表の局所DPを設計する

    • グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。
    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

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

    • 一次元の初歩的なDP、部分集合・資源DP、および区間の分割点を列挙する区間DP。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題