codeFlyer 予選 : D - ハンコ

これはまぁすんなり。
https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_d

問題

H*Wのグリッドがある。
初期状態では全マス白い。
ここでN*Mの大きさの判子を用意する。判子の形状は入力で与えられており、この判子を押すと一部のマスが黒くなる。

判子をグリッドに沿って押しうるすべての位置で押したとき、黒く塗られるマスはいくつか。

解法

H,WはN,Mよりずっと大きい場合を考えよう。
上下の両端N行を除く(H-2N)行については、判子のすべての行が押される。
同様に左右の両端M列を除く(W-2M)列については、判子のすべての列が押される。
よってこれらの行や列はどうせ同じ塗られ方をするので座標圧縮の要領で塗りつぶすことを省略してしまおう。

という考察を済ませると実装は用意である。
max(H,2N+1)*max(W,2M+1)のグリッドを用意してまずは愚直に題意どおり塗る。
この際、１マス１マス律儀に塗るとO(N^2*M^2)でTLEするので、累積和を使って塗ろう。
後は黒ますの数え上げだが、行が(2N+1)行ある場合は中心は(H-2N)行が圧縮されたものであり、列も同様に圧縮されたものとみなして数えればよい。

int H,W;
int A,B;
string S[1010];

int F[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	cin>>A>>B;
	int c=0;
	FOR(y,A) {
		cin>>S[y];
		FOR(x,B) if(S[y][x]=='#') c=1;
	}
	
	int th=min(2*A+1,H);
	int tw=min(2*B+1,W);
	int mh=th-A;
	int mw=tw-B;
	FOR(y,A) FOR(x,B) if(S[y][x]=='#') {
		F[y+1][x+1]+=1;
		F[y+mh+2][x+1]+=-1;
		F[y+1][x+mw+2]+=-1;
		F[y+mh+2][x+mw+2]+=1;
	}
	ll ret=0;
	for(y=1;y<=th;y++) {
		for(x=1;x<=tw;x++) {
			F[y][x]+=F[y-1][x]+F[y][x-1]-F[y-1][x-1];
			if(F[y][x]) {
				ll mul=1;
				if(th==2*A+1 && y==A+1) mul*=(H-2*A);
				if(tw==2*B+1 && x==B+1) mul*=(W-2*B);
				ret+=mul;
			}
		}
	}
	
	cout<<ret<<endl;
	
}

まとめ

この記事、空港の搭乗待ちの間に書いてたりします。