D - アルファベット探し Editorial by maspy


8 方向を近傍と見なして o のマスを連結成分に分解すると,アルファベットと連結成分が対応します.

あとは,各連結成分がどのアルファベットに対応するかを判定すればよいです.これは,例えば連結成分の大きさを見れば判定できます.つまり,連結成分の大きさを \(n\) とするとき,

  • \(n = 11k^2\) となる自然数 \(k\) が存在するならば A
  • \(n = 16k^2\) となる自然数 \(k\) が存在するならば B
  • \(n = 12k^2\) となる自然数 \(k\) が存在するならば C

です(素因数 \(3, 11\) の個数を考えれば,これらは重複しないことが分かります).

実装例:https://atcoder.jp/contests/arc006/submissions/42109846

posted:
last update: