h3mky0's blog

主に競プロについて書きます

CSAcademy Round #46 D. Count Gigel Matrices

問題リンク：

https://csacademy.com/contest/archive/task/cntgigelmat

問題概要：

0と1を含む $n*m$ の行列が与えられる. 主対角線と境界が全て1であるような部分正方行列の個数を数えてください.

解法：

まず「対角線を結ぶ2点を固定して, 条件を満たすかどうか」を考えてみましょう. これは事前に累積和をとることで, 1が並んでいるかどうかを前計算 $O(n^2)$ , クエリ $O(1)$ で判定できます. しかしながら, 全てのペア候補について求める場合, 固定する部分がボトルネックとなり全体計算量は $O(n^3)$ となります.

高速化のために「ある1点を固定したとき対角線上の点として条件を満たすものの個数をまとめて数え上げられないか」を考えます. 便宜上, 左上の点をA, 右下の点をBとします. Bを固定したとき, 条件を満たすAの個数を数え上げたいです.

Aの候補はBの左方向に並ぶ1の数, 上方向に並ぶ1の数, 右上に並ぶ1の数の最小値(これを $c$ とします)の範囲にある点となります.一方で, Bの候補はAの右方向に並ぶ1の数, 下方向に並ぶ1の数の最小値(これを $d$ とします)の範囲にある点となります.

以上のことから次のような数え上げが考えられます.

・各対角線上について独立に見ていく.

・Aならば $[x,x+d$ ]まで $y$ に1加算する

・Bならば $x$ について $[y-c+1,y$ ]までの区間和を求める.

二次元のクエリっぽくなりますが, xの小さい順にクエリをソートしておくことで1次元で対応できます. 区間和はsegment treeやBITを使って $O(logn)$ 求めることができることから全体計算量は $O(n^2log(n))$ となります.

提出コード：

gist92c7e540965178af8fe8cc1fc6f180fa

感想：

TLがかなり怪しかった.