Learning Algorithms

アルゴリズムの勉強メモ

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;
}