AtCoder Beginner Contest 300 C問題 Cross
問題
提出解答
問題の概要
行
列のマス目がある. 上から
行目, 下から
列目のマス目を
と書く.
各マスは のどれかが書かれており,
には
が書かれている. また,
の少なくとも一方を満たさない場合は
とする.
ここで, 正の整数 が以下の条件を全て満たすとき,
を中心とするサイズ
のバツ印という.
に対して,
は全て
である.
のうち, 少なくとも
つは
である.
また, 相異なる つのバツ印はマス同士は頂点を共有せず, 全ての
はあるバツ印を構成する.
とする.
に対して, サイズ
のバツ印は何個あるか?
制約
解法
マス があるバツ印の中心であることの必要十分条件は
が全て
であることである.
よって, 各マスについて, 中心かどうかを判定し, 中心だった場合はそのサイズを計算することによって, 全てのバツ印を漏れなく重複無く探索できる.
この方針では計算量 時間になる.