ABC461D - Count Subgrid Sum = K

解法

愚直にやるのは簡単なコードで実現できる。
つまり、範囲の上下左右の端を決め、その範囲内の総和を求めるループをすればよい。
しかし、それでは $O(H^3W^3)$ かかってTLE。
そこでとりあえず $O(H^2W^2)$ への高速化を目指す。

二次元 vector の矩形範囲内の高速化といえば、二次元累積和。
$O(HW)$ の事前処理をしておけば、任意の範囲の矩形和が $4$ つの数の加算減算だけで求まる。
これで、上下左右の端を決めるループの $O(H^2W^2)$ で処理できるようになる。

しかし、この四重ループで処理するには $157$ 億回のループが必要で、間に合わない。
そこでさらに高速化をする。

範囲の上下だけは同じように決めるとして、$O(H^2)$ 回のループを回す。
このとき、左右を決めるループが、これまでの方法では $O(W^2)$ 回あった。
これを尺取法で $O(W)$ にする。
すなわち、二次元累積和の差を取ることで、その上下幅内の左端から各列までの総和を事前に出しておく。
これは単調増加列になっているはずなので、「値がちょうど $K$ である組がいくつあるか？」は簡単。
尺取り法で「差が $K$ 以下の範囲」「差が $K$ 未満の範囲」を両方持てば、その差が「差が $K$ の範囲」。

ということで、左右を決めるループが $O(W)$ になったので、全体で $O(H^2W)$ となり、計算が間に合う。

入力例1での動作

入力を受け取る。

h: 3
w: 4
k: 3
s {"1001",
   "1101",
   "0110"}

二次元累積和を作る。
各行各列、先頭には $0$ を追加しておく。

vec: {"0, 0, 0, 0, 0",
      "0, 1, 1, 1, 2",
      "0, 2, 3, 3, 5",
      "0, 2, 4, 5, 7"}

累積和のうち $2$ 行を選び、列ごとに差をとる。
ここでは vec[1] と vec[3] を選んだ場合の例を示す。

vec[1]: "0, 1, 1, 1, 2"
vec[3]: "0, 2, 4, 5, 7"
diff  : "0, 1, 3, 4, 5",

尺取法を行う。
ただし、左側は diff[r]-k「未満」で動く l1 と、 diff[r]-k「以下」で動く l2 を用意する。
r が $0$ とすると、diff[r] は $0$ で、$0-k = -3$。
l1 は $0$ まで、l2 は $0$ まで進み、その差は $0$。
よって結果に $0$ を加算。

diff  : "0, 1, 3, 4, 5",
r : 0
l1: 0
l2: 0

r が $1$ とすると、diff[r] は $1$ で、$1-k = -2$。
l1 は $0$ まで、l2 は $0$ まで進み、その差は $0$。
よって結果に $0$ を加算。

diff  : "0, 1, 3, 4, 5",
r : 1
l1: 0
l2: 0

r が $2$ とすると、diff[r] は $3$ で、$3-k = 0$。
l1 は $0$ まで、l2 は $1$ まで進み、その差は $1$。
よって結果に $1$ を加算。

diff  : "0, 1, 3, 4, 5",
r : 2
l1: 0
l2: 1

r が $3$ とすると、diff[r] は $4$ で、$4-k = 1$。
l1 は $1$ まで、l2 は $2$ まで進み、その差は $1$。
よって結果に $1$ を加算。

diff  : "0, 1, 3, 4, 5",
r : 3
l1: 1
l2: 2

r が $4$ とすると、diff[r] は $5$ で、$5-k = 2$。
l1 は $2$ まで、l2 は $2$ まで進み、その差は $0$。
よって結果に $0$ を加算。

diff  : "0, 1, 3, 4, 5",
r : 4
l1: 2
l2: 2

vec[1] と vec[3] を選んだ場合、結果は $2$ だけ加算された。
全ての $2$ 行の組の選び方について同じことを行うと、答えは $8$ となる。

注意点

最大グリッドを全部 $0$ で埋めて $K=0$ とすると、答えは、int 型からはみ出る。
long long 型を用いること。

別解

四重ループで処理するには $157$ 億回のループが必要で、間に合わない。
……と解法に記載したが、実はC++なら間に合わないこともない。

AtCoderのサーバーのCPUは並列処理が可能らしい。
それを活かせるコードを書けば、ギリギリ間に合う。

具体的には、以下をやる。

• 計算は int 型で行う（$32$ ビットで処理することで、並列数を上げる）
• 連続するループで、vector の連続部分を処理していくようにする
• ループの中身を単純な計算のみで書く（.at() は不可）

実際に通った例は上部の「別解」リンク参照。