H - Defect-free Squares Editorial
by 
nesya
二次元累積和を用いた二分探索を使わない解法
https://atcoder.jp/contests/abc311/editorial/6829
この解説の二分探索パートで異なる解法を用いたものです。前半は同じなのでそちらの解説を参照してください。
左上が \((i,j)\) である正方形のうち、作ることができる最大のものの一辺の長さを\(x_{i,j}\)として、これを二分探索を用いずに求めることを考えます。
まず、左上が\((i,1)\)の場合について、二次元累積和を用いて一辺の長さが\(1\)の場合から順に調べて、\(x_{1,1}\dots x_{H,1}\)を求めます。
次に左上が\((i,j+1)\)の場合を考えます。左上が\((i,j+1)\)で一辺の長さが\(x_{i,j}-1\)の正方形は、左上が\((i,j)\)で一辺の長さが\(x_{i,j}\)の正方形に含まれるので、\(x_{i,j+1}\geq x_{i,j}-1\)が成り立ちます。よって一辺の長さが\(x_{i,j}\)以上の場合だけ作れるか調べればよいです。(\(x_{i,j}\)から順番に調べて作れなくなったところで打ち切ります。)
実はこれらを二次元累積和を用いて愚直に調べることで全体で\(O(HW)\)で求めることができます。
計算量の見積もり
便宜的に\(j=0,W+1\)の場合に\(x_{i,j}=0\)と定義します。
左上が\((i,j)\)の場合について、作れるか調べる必要のある回数は\(x_{i,j}-x_{i,j-1}+2\)回で抑えられるので、全体で調べる必要のある回数は\(\sum_{i=1}^{H}\sum_{j=0}^{W} (x_{i,j+1}-x_{i,j}+2)\)回以下です。
\(\sum_{i=1}^{H}\sum_{j=0}^{W} (x_{i,j+1}-x_{i,j}+2)\)
\(=\sum_{i=1}^{H} (2(W+1)+(x_{i,W+1}-x_{i,0}))\)
\(=\sum_{i=1}^{H} 2(W+1)\)
\(=2H(W+1)\)
よって調べる必要があるのは\(O(HW)\)回で、一回の判定は二次元累積和を用いて\(O(1)\)でできるので、計算量\(O(HW)\)で求めることができます。
posted:
last update: