kmjp's blog

競技プログラミング参加記です

Google Code Jam 2013 Round 1C : C. The Great Wall

GCJ

さてC。最初Largeが１時間位かかりそうな回答になってしまった。
これだと本番では解けなかったね。
https://code.google.com/codejam/contest/2437488/dashboard#s=p2

問題

問題文が非常に長い。
部族の来襲に備え、東西方向に壁を築く。ただし壁の高さは0である。

N種類の部族がn[i]回攻めてくる。
攻めてくるのは、初回がD[i]日目で以降Delta_D[i]日ごとである。
また、攻めてくる強さは初回がS[i]で、以降毎回Delta_S[i]ずつ強さが変化する。
部族は、初回W[i]～E[i]の範囲の壁をせめてきて、以降毎回Delta_P[i]ずつ座標をずらして攻めてくる。

ここで、部族があるW～Eの範囲を強さSで攻めてきたとき、W～Sの壁の高さがS以上なら攻撃を防げる。
そうでない場合、攻撃が成功する。
部族が攻めてきた後、W～Eの壁のうち、高さがSに満たない場所をSにすることができる。

部族の攻撃が成功する回数を答える。

解法

敵が攻めてくる座標の範囲は-10^8～10^8と非常に広い。
しかし、部族の来襲は、N<=1000、n[i]<=1000で10^6しかない。
よって、最初に部族の攻めてくるW[i]およびS[i]の値を列挙し、座標圧縮しておくと座標を2*10^6程度に抑えることができる。

あとはSegmentTreeを用いて、

  • W[i]～E[i]の間に高さがS[i]以下の壁があるか判定
  • W[i]～E[i]の間に高さがS[i]以下の壁があれば、高さをS[i]にする

という処理を行う。

下記のコードでは、一旦分割されたSegmentTreeを再統合する処理を含まないため、３つのテストケースで１分前後かかる。
まぁGCJは8分あるので何とか間に合うが…。

const int MD=676061;
int N;
int D[1001],NN[1001],W[1001],E[1001],S[1001],DD[1001],DP[1001],DS[1001];
vector<int> C[MD];

const int BITL=22;
map<int,int> P2I;
int CS[1<<(BITL+1)];

int update(int cur,int L,int R,int v) {
	int bl=0;
	if(L==R) return v+1;
	
	while(cur>=1<<(bl+1)) bl++;
	int tl=(cur-(1<<bl))<<(BITL-bl-1);
	int tr=(cur-(1<<bl)+1)<<(BITL-bl-1);
	int tm=(tl+tr)/2;
	//_P("%x %x %x : %x %x %x %d %d\n",cur,L,R,tl,tr,tm,CS[cur],v);
	
	if(tl==L && tr==R && CS[cur]>=0) {
		return CS[cur]=max(CS[cur],v);
	}
	else {
		if(CS[cur]>=0) {
			if(CS[cur]>=v) return CS[cur];
			CS[(1<<(bl+1))+(tl>>(BITL-bl-2))]=CS[cur];
			CS[(1<<(bl+1))+(tm>>(BITL-bl-2))]=CS[cur];
		}
		CS[cur]=-1;
		if(L<tm) update((1<<(bl+1))+(tl>>(BITL-bl-2)),L,min(tm,R),v);
		if(R>=tm) update((1<<(bl+1))+(tm>>(BITL-bl-2)),max(L,tm),R,v);
	}
}

int query(int cur,int L,int R,int v) {
	int bl=0,r;
	if(L==R) return 0;
	if(CS[cur]>=0) return (v>CS[cur])?1:0;
	
	while(cur>=1<<(bl+1)) bl++;
	int tl=(cur-(1<<bl))<<(BITL-bl-1);
	int tr=(cur-(1<<bl)+1)<<(BITL-bl-1);
	int tm=(tl+tr)/2;
	//_P("%x %x %x : %x %x %x %d %d\n",cur,L,R,tl,tr,tm,CS[cur],v);
	
	return ((L<tm)&&query((1<<(bl+1))+(tl>>(BITL-bl-2)),L,min(tm,R),v)) || 
		((R>=tm) &&query((1<<(bl+1))+(tm>>(BITL-bl-2)),max(L,tm),R,v));
}


void solve(int _loop) {
	int i,j,x,y,ne=0;
	
	N=GETi();
	FOR(i,N) cin>>D[i]>>NN[i]>>W[i]>>E[i]>>S[i]>>DD[i]>>DP[i]>>DS[i];
	FOR(i,MD) C[i].clear();
	P2I.clear();
	FOR(i,N) FOR(j,NN[i]) C[D[i]+j*DD[i]].push_back(i);
	FOR(i,N) FOR(j,NN[i]) P2I[W[i]+j*DP[i]]=P2I[E[i]+j*DP[i]]=0;
	
	i=0;
	for(map<int,int>::iterator mit=P2I.begin();mit!=P2I.end();mit++) mit->second = i++;
	
	MINUS(CS);
	CS[1]=0;
	
	int res=0;
	FOR(i,MD) {
		//if(C[i].size()) _E("%d %d %d\n",_loop,i,C[i].size());
		FOR(x,C[i].size()) {
			//_E("%d %d %x %x %d\n",i,C[i][x],P2I[W[C[i][x]]],P2I[E[C[i][x]]],S[C[i][x]]);
			if(query(1,P2I[W[C[i][x]]],P2I[E[C[i][x]]],S[C[i][x]])) {
				res++;
				S[C[i][x]]=-S[C[i][x]];
			}
		}
		FOR(x,C[i].size()) {
			j=C[i][x];
			//_E("**%d %d %x %x %d\n",i,j,W[j],E[j],S[j]);
			//_P("%d %d\n",W[j],E[j]);
			if(S[j]<0) {
				S[j]=-S[j];
				update(1,P2I[W[j]],P2I[E[j]],S[j]);
			}
			
			D[j]+=DD[j];
			S[j]+=DS[j];
			W[j]+=DP[j];
			E[j]+=DP[j];
		}
	}

	_PE("Case #%d: %d\n",_loop,res);
}

まとめ

最初座標圧縮を思いつかず、-10^8～10^8の範囲を相手にしたおかげでえらい時間がかかってしまった。
10^6程度のオーダーが登場したら、座標圧縮を考えよう…。