Codeforces Beta Round #95 (Div. 2) F : Present to Mom

問題概要

01の値が入ったボード(H,W<500)が与えられる。長方形を選んで、その端以外の部分に1がK個以上あるようにしたい。長方形の選び方がいくつあるか求める問題。

解法

何はともあれ累積和を計算しておく。上端、下端、左端について全探索する。右端についても全探索したらさすがにTLEするので、右端については単調性を利用して二分探索すれば間に合う。上端と下端を全探索して左端と右端については尺取り法で求めることもできる。これだと計算量O(H^2 * W)。

本番で通ったコード

計算量O(H^2*W*log W)。

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long int64;

const int MAX_N = 500;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1};

int N, M, K;
char buf[MAX_N][MAX_N+1];

bool is_star[MAX_N][MAX_N];
int accum[MAX_N+1][MAX_N+1];
int accum2[MAX_N+1];

//[x1, x2) * [y1, y2)
int sum(int x1, int y1, int x2, int y2){
	return accum[y2][x2] - accum[y2][x1] - accum[y1][x2] + accum[y1][x1];
}

//[x1, x2)
int sum2(int x1, int x2){
	return accum2[x2] - accum2[x1];
}

void pre(){
	for(int i=1; i<N-1; i++){
		for(int j=1; j<M-1; j++)if(buf[i][j] == '1'){
			bool ok = true;
			for(int k=0; k<4; k++){
				int ny = i + dy[k], nx = j + dx[k];
				ok &= buf[ny][nx] == '1';
			}
			if(ok){
				is_star[i][j] = true;
			}
		}
	}


	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			accum[i+1][j+1] = accum[i][j+1] + accum[i+1][j] - accum[i][j] + (is_star[i][j] ? 1 : 0);
		}
	}

}

int64 solve(){
	pre();
	int64 ans = 0;

	for(int y1=0; y1<N; y1++){
		for(int y2=y1+2; y2<N; y2++){
			for(int x=0; x<M; x++){
				accum2[x+1] = accum2[x] + sum(x, y1+1, x+1, y2);
			}

			for(int x1=0; x1<M-2; x1++){

				/*
				for(int x2=x1+2; x2<M; x2++){
					if(accum2[x2] - accum2[x1+1] >= K){
						ans++;
					}
				}
				*/

				int diff = (accum2+M) - lower_bound(accum2+x1+2, accum2+M, K + accum2[x1+1]);
				ans += diff;
			}
		}
	}



	return ans;
}

int main(){
	scanf("%d%d%d ", &N, &M, &K);
	for(int i=0; i<N; i++){
		scanf("%[^\n]%*c", buf[i]);
	}
	cout << solve() << endl;
	return 0;
}