ARC 006 D - アルファベット探し

• 問題
• AC

chokudaiさんのツイートより。簡単な方針を思いつけなかった……

「文字を囲む正方形」の一辺の長さが常に$5$の倍数になることを利用する。黒マス$(i, j)$が与えられたとき、$(i, j)$を基点に黒マスだけを8方向にたどるBFSをして、連結成分の上下左右の境界$U, D, L, R$を突き止める。$D-U+1 = 5k$とすると拡大率が$k$倍とわかるので、領域$[U, D] \times [L, R]$を左上$(U, L)$を基準に$1/k$倍に縮小する。

各点に対して上の処理を行うと、図上の文字はすべて等倍になる。あとは、図上のすべての$7\times7$の正方形について、$3$文字$\times 4$方向 $= 12$パターンのいずれかに一致するか調べればよい。これは例えばローリングハッシュなどでできる。¹ 計算量は${\mathcal O}(HW)$。

---

連結成分のサイズだけ見ればよいかもというのは最初に考えたけれど、倍数では文字を1つに絞れないと思ってすぐに捨ててしまった。（実際には、文字を$k$倍に拡大すると連結成分のサイズが$k^2$倍になるので、異なる文字のサイズが重なることはない。）

---

1. プログラミングコンテストチャレンジブック 第2版, pp.333-335より。でも、よく考えると等倍に戻したタイミングで愚直にパターンマッチすれば十分だった。 ↩︎