SRM-429 250pt: SubrectanglesOfTable

TopCoder

keyword

C++

問題概要

W*H(W,H<100)のマスにアルファベットが埋められている。全ての部分長方形に関して出現する文字列をカウントしたとき、各文字の出現頻度を求める問題。

解法

2次元累積和で各長方形に含まれる文字を列挙しようとするとO(26*(W*H)^2)で解けない。各マスについてそれを含む長方形がいくつあるか数え上げれば良い。

感想

累積和の発想から抜けだすのに時間がかかった。

vector<long long> getQuantity(vector <string> table) {
    map<char, int64> ans;
    for(char c='A'; c<='Z'; c++) ans[c] = 0;
    int i, j, W=SZ(table[0]), H=SZ(table);
    REP(i,H) table[i] += table[i];
    REP(i,H) table.push_back(table[i]);
    H <<= 1; W <<= 1;
    REP(i,H)REP(j,W){
        ans[table[i][j]] += (j+1)*(W-j)*(i+1)*(H-i);
    }
    vector<int64> ret;
    EACH(ans,it) ret.push_back(it->second);
    return ret;
}