ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

codeFlyer (bitFlyer Programming Contest)予選 D - ハンコ

問題
提出コード

解法

基本方針は、いもす法を利用して移動したときに黒くなる部分を求めていくことです。
紙の左上にまずはハンコを合わせます。すると、
(i,j)マスが黒かったとき、右にw-mマス、下にh-nマスの範囲内がすべて黒く塗られることになります。
ということで、これを1次元いもす法を2回適用、もしくは2次元のいもす法を適用することで黒く塗りつぶされている場所がわかります。
ですが、もちろんO(HW)が間に合うわけがないので、効率化します。 f:id:emtubasa:20181110175409p:plain 紙全体を図のように場合分けして考えます。

  • 白い部分
    1つ1つの四角は、多くて10^{6}マスなので、そのまま求めてしまって十分です。

  • オレンジの部分
    オレンジの部分は、どちらもw-2×m列存在します。
    元々のハンコの上からi行目のmマスは、それぞれのオレンジの部分についての上からi行目のマスを通過します。ということで、元々のハンコについて、i行目で1つでも黒い部分が存在していたら、オレンジの部分についてのi行目はすべて黒くなり、そうでなければすべて白くなっています。
    全てのiについて同じことが言えます。ので、オレンジの部分は1列に圧縮することができます。
    そして、最後にオレンジの部分を圧縮した1列の個数を、w-2×m倍することで、個数を数え上げることができます。

  • 青の部分
    青の部分は、どちらもh-2×n行存在します。
    オレンジの縦横逆バージョンです。なので、1行に圧縮することができ、最後にh-2×n倍してあげることで、数え上げることができます。

  • 黄色の部分
    この部分は、縦がh-2×n行、横がw-2×m列になっています。
    ハンコのn×mマスはすべてこの黄色の部分を少なくとも1度は通ります。
    ので、n×mマスのうち1つでも黒い部分が存在していれば、黄色の部分はすべて黒になります。
    黄色の部分を1マスに圧縮し、最後に(h-2×n)×(w-2×m)倍してあげると、この部分を数え上げることができます。

ということで、最終的には、
min(h,2×n+1)min(w,2×m+1)列の長方形についていもす法によって状態をつくりあげ、最後に圧縮している部分を拡大することで、答えを求めることができます。