## 2013年1月3日木曜日

### Codeforces Round #153 Table with Letters - 2

Problem Statement
You are given a rectangular of the size (n, m), at each cell of which an English lower-letter is located. Count the number of rectangulars in the original rectangular that satisfy the both of the following conditions:
1. The number of 'a' in the rectangle is less than k.
2. All the letters located at the four corners are the same.

Approach
First I tried a stupid bruteforce solution, which failed as I expected. Then an approach that uses binary search algorithm came to my mind, and I tried it. Failed again... It was very close, but I got a TLE. I thought through a proper approach, but it didn't hit me unfortunately. So I peeked someone's solution, and it seemed like he used a technique what you call "two-poiter" -- guess it's called "しゃくとり法" in Japanese --. Good thing that I found the solution, otherwise I would sleep on it :p

Source Code
`using namespace std;#define REP(i,n) for(int i=0; i<(int)(n); i++)#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  int n, m, k;string bd[400];int ac[400][400+1];int main() {    freopen("input.txt", "r", stdin);    freopen("output.txt", "w", stdout);    cin >> n >> m >> k;    REP (i, n)         cin >> bd[i];    REP (i, n) REP (j, m) ac[i][j+1] = ac[i][j] + (bd[i][j] == 'a');    long long ret = 0;    REP (q1, m) FOR (q2, q1+1, m) {        int atot = 0;        int cnt[26] = {0};        for (int p1 = 0, p2 = 0; p2 < n; p2++) {            atot += ac[p2][q2+1] - ac[p2][q1];            if (bd[p2][q1] != bd[p2][q2])                continue;            int c = bd[p2][q1]-'a';             ++cnt[c];                while(atot > k && p1 < p2) {                atot -= ac[p1][q2+1] - ac[p1][q1];                if (bd[p1][q1] == bd[p1][q2])                    --cnt[bd[p1][q1]-'a'];                ++p1;            }            if (atot <= k)                ret += max(0, cnt[c]-1);        }    }    cout << ret << endl;    return 0;}`