ABC219E Moat - geam1113’s diary

解説ありで解きました。

メモ

コンテスト中はDFSや全探索など実装方針がたたず、解けませんでした。

コンテスト後にbit全探索で解いてみましたが、入力例1があわず、公式解説とユーザー解説を確認し、多角形は穴があってはいけないことがわかりました。

そこまでわかって、さらに取りこぼしを乗り越えてようやくACでした。

以下、解法

問題文の条件3,4,5から、ドット絵の要領で4×4マスのマスを塗りつぶし、塗りつぶしたマスを多角形として外周にお堀を作れば良いです。

マスの数は16個なので、二次元マスを2進数とみなしたbit全探索ができそうです。bitが1のところを塗り潰すことにします。

二次元マス $B$ が構成する多角形が条件に適合するか判定します。

(1) 内部に自己交差がない

$1 \leq i \leq 3,\ 1 \leq j \leq 3$ のマス $(i,j)$ を左上とする2×2マスに以下のようなものがなければ良いです。

10 01
01 10

(2) 内部にすべての村を含む

$A$ を2進数表現としたとき(1に村がある)、以下が成り立てばよいです。

$A\ AND\ B = A$

(3) 1の領域は連結

1の領域が非連結だと、お堀は多角形とはいえません。

実装としては、 $B$ を二次元マスとして、マス $(i,j)$ が1ならBFSをして、1つの1の領域について、ビットを1から0に反転します。一回のBFSで $B$ が0になれば連結な1の領域は連結です。

以下は非連結の例です。

-> 0000
-> 0000
-> 0000
-> 0110

(4) 多角形に穴がない

多角形の定義として、穴を含んではいけないそうです。(自己交差が許されればできると思います。)

3と同様にマス $(i,j)$ が0のとき、BFSして0の領域を反転させ、1回のBFSで $B$ が $2^{16}$ になるかどうかを判定したくなります。

しかし、これは例えば、以下で誤判定してしまいます。

つまり、外周に関しては、0が独立していても問題ありません。

よって、外周のマスの内、0であるもの全てからBFSします。それでもなお、 $B$ が $2^{16}$ にならない場合は穴があると判定できます。

上記全てで条件に適合するものをカウントしていきます。

計算量はざっくり $16×2^{16} \simeq 10^7$ くらいでしょうか。