htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 092

D - Grid Components

Submission #2260916 - AtCoder Beginner Contest 092

最初は面積がA+B以上になる長方形の格子を作って、格子のマス目を塗りつぶすことで連結成分を減らしていき目的の状態を作れないかなんて考えたがどう考えても面倒で、よくよく制約を見ると縦横100*100まで許されるのに対しA, B <= 500はかなり少ない。つまりかなり雑に図形を作ってもマス目が足りなくなることはなさそうだ。ということで縦横を100*100に決め打ちし

############     ┓
#.#.#.#.#.##     ┃
.#.#.#.#.#.#     ┃
############ 白消化ゾーン
#.#.#.#.#.##     ┃
.#.#.#.#.#.#     ┃
############     ┛
............     ┓
.#.#.#.#.#..     ┃
#.#.#.#.#.#.     ┃
............ 黒消化ゾーン
.#.#.#.#.#..     ┃
#.#.#.#.#.#.     ┃
............     ┛

のように不要な連結成分を増やさないように注意しながら白と黒をジグザグに配置して消化する。白消化ゾーンでは白のジグザグを右端に達しないようにし、また1行黒のみのラインを挟むことで黒の連結数を1に抑える。黒消化ゾーンは逆に白の連結数を1に抑える。各消化ゾーンでA-1,B-1まで各色を消化し、行が余ったら白で塗りつぶす(下が黒消化ゾーンなので)。A,Bの制約がもっと大きければ効率よく格子で白と黒を同時に消化していく必要があるだろうけど、この制約ではこれでOKだった。