AtCoder ABC #260 : G - Scalene Triangle Area

直前にyukicoderで似た問題を見ていたのですんなり解けた。
https://atcoder.jp/contests/abc260/tasks/abc260_g

問題

N*Nのグリッドがある。また、正整数Mが与えられる。
セル(s,t)にコマがある場合、以下の条件を満たすセル(u,v)はそのコマに守られる。

• uはs以上、vはt以上
• (u-s)+(v-t)/2はM未満

各セルは何個のコマに守られるかを答えよ。

解法

f(u,v)をセル(u,v)を守るコマの数とする。
f(u,v)→f(u+1,v-2)の差分は、(u+1,v-2*M-1)～(u+1,v-2)の範囲のコマの分増え、(u-M+1,v-1)～(u-M+1,v)の範囲のコマの分減る。
これは、縦方向及び横方向の累積和を事前にO(N^2)かけて計算しておけば、差分はO(1)で求めることができる。
あとは、f(0,x)から初めてf(y,x-2y)を順に埋めて行けばよい。

int N,M;
string S[2020];
int LR[4020][6040];
int UD[4020][6040];
int sum[4020][6040];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) {
		cin>>S[y];
		FOR(x,6020) {
			if(x<N) {
				LR[y+1][x+1]=S[y][x]=='O';
				UD[y+1][x+1]=S[y][x]=='O';
			}
			LR[y+1][x+1]+=LR[y+1][x];
			UD[y+1][x+1]+=UD[y][x+1];
		}
	}
	FOR(x,6010) {
		int ret=0;
		int cx=x;
		FOR(y,N) {
			if(cx<0) break;
			ret+=LR[y+1][cx+1]-LR[y+1][max(cx-2*M+1,0)];
			sum[y][cx]=ret;
			ret-=UD[y+1][cx+1]-UD[max(y+1-M,0)][cx+1];
			ret-=UD[y+1][cx]-UD[max(y+1-M,0)][cx];
			cx-=2;
		}
	}
	
	
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>y>>x;
		cout<<sum[y-1][x-1]<<endl;
	}
}

まとめ

微妙に上限をミスしてしまし、本番無駄なWAを増やしてしまった。