人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

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

問題

atcoder.jp

解法

紙の (N + 1) 行目~ (H - N) 行目,(M + 1) 列目~ (W - M) 列目 はそれぞれ同じ模様になるので,この2つの区間を座標圧縮することが出来る.また,ハンコの1つ1つの黒マスが紙を黒くする領域は長方形になるので,これらを組み合わせて (2 * N + 1) * (2 * M + 1) の大きさで紙を持っておき,黒くする領域を累積和で記録しておく.O(NM).

解答

atcoder.jp

一発 AC だったのでよかったが,少し実装に時間をかけすぎた.

f:id:babcs2035:20181227164752p:plain