yukicoder : No.60 魔法少女

割と典型問題。
http://yukicoder.me/problems/123

問題

N匹のモンスターが2次元グリッド上に配置されており、それぞれの座標と体力が与えられる。
このグリッドに対し、K回の攻撃を加える。
各攻撃は、グリッド状の矩形の範囲にいる敵にDのダメージを与えられる。

全攻撃終了時、残された敵の体力を求めよ。

解法

N,Kは大きいので、攻撃ごとにモンスターが範囲内か判定するO(NK)解では間に合わない。
また、各セルへの累積ダメージを愚直に計算するのもO(N+K*L^2)かかり間に合わない(Lは敵がいる座標の範囲である1000)。

そこで、セルへの累積ダメージを累積和を使って求めると良い。
2次元累積和を使うとO(N+K+L^2)だが、以下のコードでは手を抜いて各行ごとに1次元の累積和を使っておりO(N+K*L)である。

int N,K;
int X[100001],Y[100001],H[100001];
int AX[100001],AY[100001],W[100001],HH[100001],D[100001];

int DD[1505][1505];
int S[1505][1505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>X[i]>>Y[i]>>H[i];
	
	FOR(i,K) {
		cin>>AX[i]>>AY[i]>>W[i]>>HH[i]>>D[i];
		for(y=AY[i]+500;y<=AY[i]+500+HH[i];y++) DD[y][AX[i]+500]+=D[i],DD[y][AX[i]+500+W[i]+1]-=D[i];
	}
	
	FOR(y,1502) FOR(x,1502) S[y][x]=((x>0)?S[y][x-1]:0)+DD[y][x];
	
	int tot=0;
	FOR(i,N) tot+=max(0,H[i]-S[Y[i]+500][X[i]+500]);
	cout<<tot<<endl;
	
}

まとめ

ロゴはこの問題のためだけに作ったのかな…。