AtCoder Beginner Contest 241 C問題 Connect 6

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 行 $N$ 列のマス目にはそれぞれ白または黒で塗られている. 高々 $2$ 個の白マスを黒マスに塗り替えることにより, 縦横斜めの向きに $6$ 個以上黒マスを連続させることは可能か?

制約

$6 \leq N \leq 1000$

解法

ある方向に連続する6マスにおいて, そこにある黒マスが $4$ 個以上ならば, 残りの高々 $2$ 個の白マスを黒マスに塗り替えることにより目標を達成できる.

逆に, ある方向に連続する6マスにおいて, そこにある黒マスが $3$ 個以下ならば目標を達成できない.

よって, 連続する6マスにおける黒マスの数を数えることになる. 縦方向の連続する $6$ マスの選び方は一番上のマスを選ぶと, 残りが自動的に決まるので, $N(N-5)$ 通り. 横についても同様で, $N(N-5)$ 通り. 斜めについても右上か左上のマスを選ぶことになるので, $2 \times (N-5)^2$ 通り.