Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 278 E問題 Grid Filling

AtCoder ABC278 ABC E問題 500 pts

問題

提出解答

問題の概要

縦 $H$ 行, 横 $W$ 列からなるグリッドがある. 上から $i$ 行目, 左から $j$ 行目にあるマス目を $(i,j)$ と書く.

$(i,j)$ には整数 $A_{i,j}$ が書かれている. ただし, $1 \leq A_{i,j} \leq N$ である.

$0 \leq k \leq H-h, 0 \leq l \leq W-w$ を満たす整数の組 $(k,l)$ 全てについて次の問に答えよ.

$k \lt i \leq k+h, l \lt j \leq l+w$ を満たす $(i,j)$ を塗りつぶす. 塗りつぶされていないマスに書かれている整数の種類数を求めよ.

制約

$1 \leq h \leq H \leq 300$
$1 \leq w \leq W \leq 300$
$(h,w) \neq (H,W)$
$1 \leq N \leq 300$
$1 \leq A_{i,j} \leq N$

解法

$k \lt i \leq k+h, l \lt j \leq l+w$ を満たす $(i,j)$ を塗りつぶすことを塗りつぶし $(k,l)$ ということにする.

$a=1,2, \dots, N$ それぞれに対して, 塗りつぶした後, 残ったマスに $a$ が存在するかどうかを判定する.

$A_{i,j}=a$ となる $(i,j)$ の個数を $\chi_a$ とする.

このとき, 以下は全て同値である.

塗りつぶし $(k,l)$ の後, 残ったマスに $a$ が存在しない.
$A_{i,j}=a$ となる $(i,j)$ は全て $k \lt i \leq k+h, l \lt j \leq l+w$ を満たす.
$A_{i,j}=a, k \lt i \leq k+h, l \lt j \leq l+w$ を満たす $(i,j)$ の組の個数は $\chi_a$ である.

$A_{i,j}=a, k \lt i \leq k+h, l \lt j \leq l+w$ を満たす $(i,j)$ の組の個数 $v^{(a)}_{i,j}$ を高速に求める方法を考える. $B^{(a)}_{i,j}$ を

$B^{(a)}_{i,j}=\begin{cases} 1 & (A_{i,j}=a) \\ 0 & (A_{i,j} \neq 0) \end{cases}$

とすると,

$\displaystyle v^{(a)}_{k,l}=\sum_{k \lt i \leq k+h \\ l \lt j \leq l+w} B^{(a)}_{i,j}$

である.

この [tex: v^{(a)}{k,l}] は正しく [tex: B^{(a)}{i,j}] による2次元の区間和である.

このような2次元の区間和は2次元の累積和を利用することによって, 高速化できる.

計算量について, 各 $a$ ごとに2次元の累積和の前計算を $O(HW)$ 時間, 累積和1回求めるためには $O(1)$ 時間であり, これを $O(HW)$ 回行う. よって, 合計 $O(HW)$ 時間である.

これを $a=1,2, \dots, N$ に対して行うので, 合計で $O(NHW)$ 時間で計算できた.