AtCoder Beginner Contest 045 D - すぬけ君の塗り絵 / Snuke's Coloring
問題概要
全て白色のグリッドの数個のマスを黒色に塗りつぶす。その上で、考えうる全ての3*3のグリッドについて、そのグリッド内に黒いマスが丁度個(
)含まれるグリッドの個数を求める。
解法
より、素直に配列を用意することはできない。試しに広いグリッド上で1マス塗った時を考える。ここから下図を用いて説明していく。
このように、右下1マスを塗った時、このマスを含む3*3のグリッドというのは9通りしか考えられない。その考えうるグリッドの最も左上のマスは上図で〇が描かれている(当然塗ったマスも最も左上のマス足り得るがスペースの関係上省略している)。このように塗られたマスが含まれ得る全てのグリッドの左上のマスの位置を全列挙するとその数は最大でも個しか存在しないため、配列を保持することができる。
このように全ての左上のマスを列挙した後、そのデータの入った配列をsortし、同じマスを指しているものの個数を数え上げればよい。
これを実装して、AC。sortがネックなので。
