dwangoプログラミングコンテスト予選 : E - 電波局

座標圧縮まで思いつけばすぐ。
http://dwango2015-prelims.contest.atcoder.jp/tasks/dwango2015_prelims_5

問題

1≦i≦j≦Nに対し(j,i)となるN*(N+1)/2個の格子点に電波による配信を行うことを考える。

M個の電波局がある。
各電波局は座標(A[i],B[i])に設置され、電波出力はC[i]である。
この電波局により、1≦k≦j≦C[i]となるk,jに対し(A[i]+j-1, B[i]+k-1)の位置に配信が可能となる。

ここで以下のQ個のクエリに答えよ。
各クエリでは、新規に設置する電波局の座標と電波出力が与えられる。
その新設電波局により、新たに配信可能となる格子点の数を答えよ。

解法

部分点解法1

N≦200なので、格子点の数は高々20200である。
よって単純に各格子点に対する配信の有無をシミュレートするだけでよい。

部分点解法2

Nが大きいので、全格子点の状態を管理することはできない。
M+Qは2000以下とそこまで大きくないので座標圧縮することを考える。

まず、配信条件がややこしいので少し書き換える。
元の条件は上にある電波塔が下に配信していたが、左下にある電波塔が右上に配信すると読み替える。
すなわち、(A[i]+C[i]-1,B[i])にある電波塔が0≦(k+j)≦C[i]なk,jに対し(A[i]+C[i]-1-k,B[i]+j)に配信すると考える。

そして既存電波塔・新規電波塔に対し、X座標を(A[i]+C[i]-1)、Y座標を(B[i])で座標圧縮する。
こうして座標圧縮した各X座標Y座標に対応する２次元配列dp[x][y]を準備し、「座標圧縮後の点(x,y)から右上方向にマンハッタン距離dp[x][y]の範囲に配信する」という値dp[x][y]を格納していく。

座標圧縮前の座標x,yから圧縮後の座標を求める関数をCx,Cy、逆関数をDx,Dyとする。
まず各既存電波塔に対しては、dp[Cx(A[i]+C[i]-1)][Cy(B[i])] = max(dp[Cx(A[i]+C[i]-1)][Cy(B[i])], C[i])で各dp[x][y]における配信範囲を設定する。

次に以下のDPで隣接する座標の配信範囲が自分の範囲をカバーするか判定する。

• dp[x+1][y] = max(dp[x+1][y], dp[x][y] - (Dx(x+1)-Dx(x))
• dp[x][y+1] = max(dp[x][y+1], dp[x][y] - (Dy(y+1)-Dy(y))

あとは各クエリに対し、座標圧縮後の各格子に対して、既存の配信先と新規配信先の格子点数の差を取ればよい。
全体でO((N+Q)^3)なので、部分点２はここまでで取れる。

満点解法

基本的には部分点解法２と同じ。
既存の配信が全く行われない格子群や、格子内全領域をカバー済みの格子については、クエリ処理の際事前にスキップできるよう前処理しておくとO((N+Q)^2)に抑えられる。
以下のコードだとempやfilはそのような情報を格納している。

int N,M,Q,NX,NY;
int A[1500],B[1500],C[1500];
int QA[1500],QB[1500],QC[1500];
int pat[3000][3000];
int emp[3000][3000],fil[3000][3000];
map<int,int> MX,MY;
vector<int> XX,YY;

ll area(ll dx,ll dy,ll d) {
	if(d<=0) return 0;
	ll ret=d*(d+1)/2;
	if(dx<d) ret -= (d-dx)*(d-dx+1)/2;
	if(dy<d) ret -= (d-dy)*(d-dy+1)/2;
	if(dx+dy<d) ret += (d-(dx+dy))*(d-(dx+dy)+1)/2;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	MX[N]=MY[N]=MX[0]=MY[0]=0;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		MX[N-(A[i]+C[i]-1)]=MY[B[i]-1]=0;
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>QA[i]>>QB[i]>>QC[i];
		MX[N-(QA[i]+QC[i]-1)]=MY[QB[i]-1]=0;
	}
	ITR(it,MX) it->second=XX.size(), XX.push_back(it->first);
	ITR(it,MY) it->second=YY.size(), YY.push_back(it->first);
	NX=XX.size();
	NY=YY.size();
	FOR(i,M) {
		A[i]=MX[N-(A[i]+C[i]-1)];
		B[i]=MY[B[i]-1];
		pat[A[i]][B[i]]=max(pat[A[i]][B[i]],C[i]);
	}
	
	FOR(x,NX) FOR(y,NY) {
		if(x+1<NX) pat[x+1][y]=max(pat[x+1][y],pat[x][y]-(XX[x+1]-XX[x]));
		if(y+1<NY) pat[x][y+1]=max(pat[x][y+1],pat[x][y]-(YY[y+1]-YY[y]));
	}
	FOR(x,NX) {
		for(y=NY-1;y>=0;y--) {
			if(pat[x][y]==0) emp[x][y]=emp[x][y+1]+1;
			if(y!=NY-1 && pat[x][y]-(YY[y+1]-YY[y])==pat[x][y+1]) fil[x][y]=fil[x][y+1]+1;
		}
	}
	
	FOR(i,Q) {
		QA[i]=MX[N-(QA[i]+QC[i]-1)];
		QB[i]=MY[QB[i]-1];
		ll ret=1LL*QC[i]*(QC[i]+1)/2;
		for(x=QA[i];x<NX-1;x++) for(y=QB[i];y<NY-1;y++) {
			j=QC[i]-(XX[x]-XX[QA[i]])-(YY[y]-YY[QB[i]]);
			if(j<=0) break;
			if(emp[x][y]) {
				y+=emp[x][y]-1;
			}
			else if(fil[x][y]) {
				ret -= area(XX[x+1]-XX[x],YY[y+fil[x][y]]-YY[y],min(j,pat[x][y]));
				y+=fil[x][y]-1;
			}
			else {
				ret -= area(XX[x+1]-XX[x],YY[y+1]-YY[y],min(j,pat[x][y]));
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

包除原理を考えたのが失敗。
Nが1000な時点でそれはないと思ったが…。
座圧まで思いつけばあとは自力で解けたのに。