mayoko’s diary

プロコンとかいろいろ。

CODE THANKS FESTIVAL 2015 H - 穴あきケーキ

解法

まず前計算として, (y0, x0, y1, x1) で決まる長方形内にある数字の合計, および 長方形内にある各数字の数, を求めておきます。

そのあとはしゃくとり法です。問題文にあるように c と d を決めた時, a と b の組は前計算で求めたものを使えば (d-c >= 10 のとき) しゃくとりで簡単に求められます。

ただ, d-c < 10 のとき, b の値を一つ決めても a の値が複数通りある可能性があり, 処理が面倒だと思ったので, d-c < 10 の時は, a と b の組み合わせを全探索しています。

const int MAX = 355;
string board[MAX];
int numSum[MAX][MAX][10];
int boardSum[MAX][MAX];

int getNumSum(int num, int y0, int x0, int y1, int x1) {
    return numSum[y1][x1][num] - numSum[y1][x0-1][num] - numSum[y0-1][x1][num] + numSum[y0-1][x0-1][num];
}

int getSum(int y0, int x0, int y1, int x1) {
    return boardSum[y1][x1] - boardSum[y1][x0-1] - boardSum[y0-1][x1] + boardSum[y0-1][x0-1];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int R, C, K;
    cin >> R >> C >> K;
    for (int i = 0; i < R; i++) cin >> board[i];
    for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) {
        int num = board[i-1][j-1]-'0';
        for (int k = 1; k <= 9; k++) {
            numSum[i][j][k] = numSum[i-1][j][k] + numSum[i][j-1][k] - numSum[i-1][j-1][k] + (k==num);
        }
    }
    for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) {
        boardSum[i][j] = boardSum[i-1][j] + boardSum[i][j-1] - boardSum[i-1][j-1] + (board[i-1][j-1]-'0');
    }
    ll ans = 0;
    for (int x0 = 1; x0 <= C; x0++) for (int x1 = x0+2; x1 <= C; x1++) {
        if (x1-x0 < 10) {
            for (int y0 = 1; y0 <= R; y0++) for (int y1 = y0+2; y1 <= R; y1++) {
                int rest = getSum(y0, x0, y1, x1) - K;
                if (0 < rest && rest <= 9) ans += getNumSum(rest, y0+1, x0+1, y1-1, x1-1);
            }
        } else {
            int s = 1, t = 1;
            for (;;) {
                while (t <= R && getSum(s, x0, t, x1) <= K) t++;
                if (getSum(s, x0, t, x1) <= K) break;
                int rest = getSum(s, x0, t, x1)-K;
                if (rest <= 9 && t-s >= 2) ans += getNumSum(rest, s+1, x0+1, t-1, x1-1);
                s++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}