座標圧縮まで思いつけばすぐ。
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座標に対応する2次元配列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)なので、部分点2はここまでで取れる。
満点解法
基本的には部分点解法2と同じ。
既存の配信が全く行われない格子群や、格子内全領域をカバー済みの格子については、クエリ処理の際事前にスキップできるよう前処理しておくと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な時点でそれはないと思ったが…。
座圧まで思いつけばあとは自力で解けたのに。