codeFlyer (bitFlyer Programming Contest)予選 D - ハンコ
解法
基本方針は、いもす法を利用して移動したときに黒くなる部分を求めていくことです。
紙の左上にまずはハンコを合わせます。すると、
マスが黒かったとき、右にマス、下にマスの範囲内がすべて黒く塗られることになります。
ということで、これを1次元いもす法を2回適用、もしくは2次元のいもす法を適用することで黒く塗りつぶされている場所がわかります。
ですが、もちろんが間に合うわけがないので、効率化します。
紙全体を図のように場合分けして考えます。
白い部分
1つ1つの四角は、多くてマスなので、そのまま求めてしまって十分です。オレンジの部分
オレンジの部分は、どちらも列存在します。
元々のハンコの上から行目のマスは、それぞれのオレンジの部分についての上から行目のマスを通過します。ということで、元々のハンコについて、行目で1つでも黒い部分が存在していたら、オレンジの部分についての行目はすべて黒くなり、そうでなければすべて白くなっています。
全てのについて同じことが言えます。ので、オレンジの部分は1列に圧縮することができます。
そして、最後にオレンジの部分を圧縮した1列の個数を、倍することで、個数を数え上げることができます。青の部分
青の部分は、どちらも行存在します。
オレンジの縦横逆バージョンです。なので、1行に圧縮することができ、最後に倍してあげることで、数え上げることができます。黄色の部分
この部分は、縦が行、横が列になっています。
ハンコのマスはすべてこの黄色の部分を少なくとも1度は通ります。
ので、マスのうち1つでも黒い部分が存在していれば、黄色の部分はすべて黒になります。
黄色の部分を1マスに圧縮し、最後に倍してあげると、この部分を数え上げることができます。
ということで、最終的には、
行列の長方形についていもす法によって状態をつくりあげ、最後に圧縮している部分を拡大することで、答えを求めることができます。