ステップ1 城壁をどこまで伸ばせるかを計算

「各マスを起点としたとき城壁を上/下/左/右の各方向に何マス伸ばせるか」を計算します。城壁が置けない場合は \(0\)、城壁をそのマスにしか置けないときは \(1\) とします。

\(U_{i,j}\)「マス\((i,j)\)を起点としたとき城壁を上方向に何マス伸ばせるか」は下記のように計算できます。他の方向にも同様に計算できます。

• 城壁がないと判明しているマスならば \(U_{i,j} = 0\)
• IOI王国の上端(\(i=1\))ならば \(U_{1,j} = 1\)
• そうでなければ、\(U_{i,j} = U_{i-1,j} + 1\)

右方向と下方向、左方向と上方向はセットとして考えることにして、

\[ RD_{i,j} = min(右に何マス伸ばせるか, 下に何マス伸ばせるか) \\ LU_{i,j} = min(左に何マス伸ばせるか, 上に何マス伸ばせるか) \]

とします。

ステップ2 城壁が有効である条件

マス\((i,j)\)が城壁の左上となるように大きさ \(s\) の城壁を置くには以下のすべての条件を満たす必要があります。

• \(s \ge L\)
• \(RD_{i,j} \ge s\)
• \(LU_{i+s-1,j+s-1} \ge s\)

このままでは座標にも条件式にも \(s\) の情報が含まれるので扱いづらいです。

そこで、\(X_{i,j}= i - LU_{i,j}\) という変形を考えます。直感的には「マス\((i,j)\)から左/上方向に伸ばす場合は\(X_{i,j}\)行目まで伸ばすことができる」ということを表します。

また、\((i+s-1)-(j+s-1)=i-j\) より \(LU_{i+s-1,j+s-1}\)は \(i-j\) が一定となる条件が有効そうです。

よって、\(Y_{i-j,i}=X{i,j}\)という数列を考慮してみます。

すると、\(LU_{i+s-1,j+s-1} \ge s\) は \(X_{i+s-1,j+s-1} = Y_{i-j, i+s-1} < i\)と書き換えられます。

ここで導出された条件式

• \(i+L-1 \le k < i+RD_{i,j}\)
• \(Y_{i-j,k} < i\)

を言い換えると、

「マス\((i,j)\)が城壁の左上となるように置ける場合の数は \(Y_{i-j,k} < i (i+L-1 \le k < i+RD_{i,j})\) をみたす \(k\) の数と等しい」となります。

ステップ3 Wavelet行列

\(Y_{i-j,k} < i (i+L-1 \le k < i+RD_{i,j})\) を高速に導出することでこの問題を解くことができるはずです。

このようなクエリを解く手段として Wavelet行列 というデータ構造があります。

Wavelet行列では、配列 \(A\) について

• インデックスが\(l \le i < r\)をみたす範囲で\(M\)以下の値の個数
• インデックスが\(l \le i < r\)をみたす範囲で\(k\)番目に小さい値

などを \(O(log(値の種類数))\) で求められるデータ構造です。

ステップ2の \(Y_{i-j,k}\) を\(k\)の一次元配列とみなすことで Wavelet行列 を適用できます。

Wavelet行列を\(i-j\)ごとに事前計算しておくことで、各マス \(O(log(H+W))\) での場合の数を導出できるので、合計で \(O((H+W)^2 log(H+W))\) で全体の場合の数を導出することができます