SRM 562 div1 easy PastingPaintingDivOne

問題

TopCoder Statistics - Problem Statement

クリップボードが与えられる。これは H*W 個のセルがあり, それぞれのセルは透明か RGB いずれかの色をしている。このクリップボードを, 左上が(0, 0), (1, 1), ..., (T-1, T-1) になるように (0, 0) が一番下になるように重ねていく。重ねられた際, 色のついてるセルはその色に塗り替えられる(透明なセルは塗り替えられない)。

この重ねられたクリップボードを上から見ると, R, G, B のセルは各自いくつあるか。

解法

T が大きいので正直にやるとできませんが, 各クリップボードの下に i 個だけクリップボードがあるとして, 他のクリップボードに重ねられる色がどれだけあるかを調べれば, T が大きい場合はほとんどのボードが min(H, W) 個のクリップボードを下に重ねられたものになります。

bool done[55][55];

class PastingPaintingDivOne {
public:
    vector<long long> countColors(vector <string> clipboard, int T) {
        int H = clipboard.size(), W = clipboard[0].size();
        vector<ll> ans(3);
        map<char, ll> mp[55];
        memset(done, false, sizeof(done));
        for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
            mp[0][clipboard[i][j]]++;
        }
        for (int i = 1; i < 55; i++) {
            mp[i]['R'] = mp[i-1]['R'];
            mp[i]['G'] = mp[i-1]['G'];
            mp[i]['B'] = mp[i-1]['B'];
            for (int h = i; h < H; h++) for (int w = i; w < W; w++) {
                if (clipboard[h][w] != '.' && clipboard[h-i][w-i] != '.' && !done[h][w]) {
                    done[h][w] = true;
                    mp[i][clipboard[h][w]]--;
                }
            }
        }
        for (int i = 0; i < min(55, T); i++) {
            ans[0] += mp[i]['R'];
            ans[1] += mp[i]['G'];
            ans[2] += mp[i]['B'];
        }
        if (T >= 55) {
            ans[0] += mp[54]['R'] * (ll)(T-55);
            ans[1] += mp[54]['G'] * (ll)(T-55);
            ans[2] += mp[54]['B'] * (ll)(T-55);
        }
        return ans;
    }
};