AtCoder ABC #182 : E - Akari

Dの方が難しくない？
https://atcoder.jp/contests/abc182/tasks/abc182_e

問題

H*Wのグリッドがある。
一部マスに電球、一部マスは障害物がある。
電球から上下左右のマスは、障害物に途中遮られない範囲で照らされる。
照らされているマスの総数を求めよ。

解法

累積和に近い感じで解く。
例えば左から照らされるマスを列挙する場合、各行を左から見て行って、最寄の障害物より最寄の電球が近いなら照らされているとみなす。
同様の処理を上下左右に行うと、全体でO(HW)で処理できる。

int H,W;
int N,M;
int A[1555][1555];
int B[1555][1555];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		A[x-1][y-1]=1;
	}
	FOR(i,M) {
		cin>>x>>y;
		A[x-1][y-1]=2;
	}
	FOR(y,H) {
		int ok=0;
		FOR(x,W) {
			if(A[y][x]==1) ok=1;
			if(A[y][x]==2) ok=0;
			B[y][x]|=ok;
		}
		ok=0;
		for(x=W-1;x>=0;x--) {
			if(A[y][x]==1) ok=1;
			if(A[y][x]==2) ok=0;
			B[y][x]|=ok;
		}
	}
	FOR(x,W) {
		int ok=0;
		FOR(y,H) {
			if(A[y][x]==1) ok=1;
			if(A[y][x]==2) ok=0;
			B[y][x]|=ok;
		}
		ok=0;
		for(y=H-1;y>=0;y--) {
			if(A[y][x]==1) ok=1;
			if(A[y][x]==2) ok=0;
			B[y][x]|=ok;
		}
	}
	int ret=0;
	FOR(y,H) FOR(x,W) ret+=B[y][x];
	cout<<ret<<endl;
	
}

まとめ

Dの方が迷ったなぁ。