ABC018 C - 菱型カウント
解法
ある地点で×な部分があると、その×を中心として作成したひし形の範囲内の任意のマス(x,y)について、(x,y)を中心とするひし形は作成できません。
ということで、
memo[i][j] = (i,j)を中心としてひし形を作成したとき、その範囲内に存在する×印の個数
とすると、
ということで、全ての×印のマスについて、その範囲内のマス目(x,y)についてmemo[x][[y]に1追加すれば、memoが完成します。
あとは、中心としてありうる(i,j)について、memo[i][j]=0となっているマス目を調べればよいです。
ここで、単純にmemo[x][y]に1を追加していたのでは間に合わないので、いもす法を用います。
(x,y)が×印だったとき、
memo[i + l][max(0, j - k + 1 + l)]には1を追加、memo[i + l][min(c, j + k - l)]からは1を減らす、という操作をしていけばよいです。
ここで、lは0~k-1になります。
あとは、横方向について累積和をとると、memoを完成させることができます。
