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