Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring
Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring
D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Regular Contest 061 | AtCoder
解法
最も愚直な方法は、$\ H * W\ $の配列を用意し、そこにクエリに従って色をつけていき、最後に$\ 3 * 3\ $の範囲を動かして全探索する方法である。 当然これは時間計算量も空間計算量も厳しい。
あるグリッドが塗られたときに、各カウントがどのように変化するかを考える。すると、その塗られたグリッドを中心とする$\ 5 * 5\ $の範囲のみのカウントが変わることに気づく。よってそこのカウントの変化だけを見れば良い。
普通にグリッドを用意すると同様にMLEとなる。ある座標が塗られているかどうかだけ判定できればよいので、塗られた座標をset
に入れておくとよい。計算量は$\ O(n\log n)\ $の大きめの定数倍?
実装
#include "bits/stdc++.h" using namespace std; #define mp make_pair #define pii pair<int, int> int main() { long long h, w, n; cin >> h >> w >> n; set<pii> s; vector<long long> ans(10, 0); ans[0] = (h - 2) * (w - 2); for (int k = 0; k < n; k ++) { long long a, b; cin >> a >> b; a --, b --; for (long long i = max(0LL, a - 2); i < min(a + 1, h - 2); i ++) { for (long long j = max(0LL, b - 2); j < min(b + 1, w - 2); j ++) { int cnt = 0; for (long long y = i; y < i + 3; y ++) { for (long long x = j; x < j + 3; x ++) { if (s.count(mp(y, x))) cnt ++; } } ans[cnt] --; ans[cnt + 1] ++; } } s.insert(mp(a, b)); } for (int i = 0; i < 10; i ++) { cout << ans[i] << endl; } return 0; }