codeFlyer 2018 予選 D - ハンコ

• 問題

問題概要

NM のハンコをハンコがマスに収まるような範囲の全ての場所でHW のマスに押す.
ハンコで黒く塗られるのは何箇所か求めよ.
1 <= N,M <= 10³ ,1 <= H,W <= 10⁹

解法

まず for(ハンコを押した回数) for(ハンコの全てのマス)のループの順序を入れ替えて,
ハンコの各マスがH-N+1 * W-M+1 のマスを黒く塗ると考えよう.
こうすることで塗る領域が長方形になるので,二次元累積和を取ればO(HW+NM)では解けるようになった.
しかしこれでは間に合わない,
だが,HとWが増えても塗る長方形の領域が大きくなるだけなので二次元累積和を取るときにアクセスするマスだけを考えれば良いことがわかる.
つまり考えなければならないマスは, xであれば 0とH-N, 1とH-N+1, .., N-1とH-1 .. となる
yも同様に考えて,これらのうち重複を除き,考えなければならない座標をx_dec, y_decとする.
このindexとelementを逆にしてmapを取れば圧縮後の座標 x_enc, y_enc が求められる.
圧縮後の座標を二次元累積和で塗り,圧縮前の塗られている場所の面積を求めれば答えとなる.
( i が塗られていれば [ x_dec[i], x_dec[i+1] ) が塗られていると考える)

メモ

本番は色々なケースで試してみる
-> H,Wが大きいケースでは外縁の領域だけ考えれば良さそう
-> 外側の領域を頑張って取ってくるコードを書く
という感じで爆死だった
言われてみるといかにも累積和だし座標圧縮っぽい
面積が復元できるというところで経験値が足りなかった..

コード