水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder codeFlyer (bitFlyer Programming Contest) : D - ハンコ

  • 問題

D - ハンコ

HW のマスに NM のハンコをひたすらおし、押されたマスの合計を求めよ、という問題。

 

  • 解法

H,W <= 10^9 であるため、HW の二次元配列は用意できない。しかし、N,M <= 10^3 であるため、なんかできそうだなあと思った。考えると、

ハンコのマス (i,j) が黒ならば、台紙のマスは (i,j)-(i+H-N,j+W-M) まで塗られる

ため、

座標圧縮からの二次元累積和

で解けそうとなる。座圧において、始端と末端の処理で手こずり 3WA(悲しいね)。

 

  • 解答

f:id:babcs2035:20180606215138p:plain

f:id:babcs2035:20180606215141p:plain

Submission #2626889 - codeFlyer (bitFlyer Programming Contest)