AtCoder codeFlyer (bitFlyer Programming Contest) : D - ハンコ
-
問題
HW のマスに NM のハンコをひたすらおし、押されたマスの合計を求めよ、という問題。
-
解法
H,W <= 10^9 であるため、HW の二次元配列は用意できない。しかし、N,M <= 10^3 であるため、なんかできそうだなあと思った。考えると、
ハンコのマス (i,j) が黒ならば、台紙のマスは (i,j)-(i+H-N,j+W-M) まで塗られる
ため、
座標圧縮からの二次元累積和
で解けそうとなる。座圧において、始端と末端の処理で手こずり 3WA（悲しいね）。
-
解答
Submission #2626889 - codeFlyer （bitFlyer Programming Contest）
