geam1113 https://blog.hatena.ne.jp/geam1113/ geam1113’s diary https://geam1113.hatenablog.com/ ABC 二次元bit全探索 解説ありで解きました。 メモ コンテスト中はDFSや全探索など実装方針がたたず、解けませんでした。 コンテスト後にbit全探索で解いてみましたが、入力例1があわず、公式解説とユーザー解説を確認し、多角形は穴があってはいけないことがわかりました。 そこまでわかって、さらに取りこぼしを乗り越えてようやくACでした。 以下、解法 問題文の条件3,4,5から、ドット絵の要領で4×4マスのマスを塗りつぶし、塗りつぶしたマスを多角形として外周にお堀を作れば良いです。 マスの数は16個なので、二次元マスを2進数とみなしたbit全探索ができそうです。bitが1のところを塗り潰すことにします。 二次元マスが構成… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fgeam1113.hatenablog.com%2Fentry%2F2021%2F09%2F25%2F172719" title="ABC219E Moat - geam1113’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-09-25 17:27:19 rich https://geam1113.hatenablog.com/entry/2021/09/25/172719 1.0 100%