kmjp's blog

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

Codeforces #269 Div2 D. MUH and Cube Walls

Codeforces

あまり良い手段ではないが何とか解けた。
http://codeforces.com/contest/471/problem/D

問題

幅1、高さa[i]の建物がN個順に並んでいる。

ここで、幅1、高さb[i]の建物がW個連続にならんでいる場合、その建物群は象に見える。
また、象に見える建物群を平行移動したら一致する建物群も象に見える。

元のN個の建物の中に、象は何個見えるか。

解法

W==1の時、答えはNとなる。

それ以外の場合、a[i]の差分を取って(N-1)要素の配列p[i]を作る。
また、b[i]の差分を取って(W-1)要素の配列q[i]を作る。

差分を取ることに気づけばあとは簡単で、p[i]中にq[i]が何個含まれるか調べればよい。
これは文字列検索と同じなので、ローリングハッシュ・KMP法・Z Algorithmあたりでいずれも通る。
自分は本番ローリングハッシュを使ったけど、Z Algorithmの方が簡単だね。

以下はローリングハッシュ。

int N,W;
ll A[300000],B[300000];
ll D[300000],E[300000];

ll mo1=999999937,mo2=1000000009;
ll d1,d2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W;
	FOR(i,N) cin>>A[i];
	FOR(i,W) cin>>B[i];
	N--;W--;
	FOR(i,N) D[i]=A[i+1]-A[i];
	FOR(i,W) E[i]=B[i+1]-B[i];
	ll ha1=0,ha2=0;
	d1=d2=1;
	ll m1=10009,m2=10007;
	ll a1=1000000000+10007,a2=1000000000+3333331;
	
	if(N<W) return _P("0\n");
	if(W==0) return _P("%d\n",N+1);
	
	FOR(i,W) {
		ha1=(ha1*m1+E[i]+a1)%mo1;
		ha2=(ha2*m2+E[i]+a2)%mo2;
		d1=d1*m1%mo1;
		d2=d2*m2%mo2;
	}
	
	
	ll c1=0,c2=0;
	int ret=0,t=0;
	FOR(i,N) {
		c1=(c1*m1+D[i]+a1)%mo1;
		c2=(c2*m2+D[i]+a2)%mo2;
		t++;
		if(t>=W+1) {
			c1-=d1*(D[i-W]+a1)%mo1;
			c2-=d2*(D[i-W]+a2)%mo2;
			if(c1<0) c1+=mo1;
			if(c2<0) c2+=mo2;
		}
		if(t>=W && c1==ha1 &&c2==ha2) {
			ret++;
			/*i++;
			t=0;
			c1=c2=0;*/
		}
	}
	cout << ret << endl;
}

以下はKMP法。

int N,W;
ll A[300000],B[300000];

int KMPT[4*100000];
ll res;

int KMP(vector<int>& tar,vector<int>& pat, int cur=0) {
	int c,p=0,l,pl;
	FOR(c,tar.size()) {
		while(cur>-1 && pat[cur]!=tar[c]) cur=KMPT[cur];
		if(++cur >= pat.size()) res++, cur=KMPT[cur];
	}
	return cur;
}

void prepKMP(vector<int>& str) {
	int i,n;
	
	n=KMPT[0]=-1;
	FOR(i,str.size()) {
		while(n>-1 && str[i]!=str[n]) n=KMPT[n];
		KMPT[i+1]=++n;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W;
	FOR(i,N) cin>>A[i];
	FOR(i,W) cin>>B[i];
	
	if(W==1) return _P("%d\n",N);
	vector<int> D,E;
	FOR(i,N-1) D.push_back(A[i+1]-A[i]);
	FOR(i,W-1) E.push_back(B[i+1]-B[i]);
	prepKMP(E);
	KMP(D,E);
	cout << res << endl;
	
}

Z Algorithmでも行ける。

int N,W;
ll A[300000],B[300000];

vector<int> Zalgo(vector<int> s) {
	int l=-1,r=-1,i;
	vector<int> v;
	v.push_back(s.size());
	for(i=1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W;
	FOR(i,N) cin>>A[i];
	FOR(i,W) cin>>B[i];
	
	if(W==1) return _P("%d\n",N);
	vector<int> V;
	FOR(i,W-1) V.push_back(B[i+1]-B[i]);
	V.push_back(1<<30);
	FOR(i,N-1) V.push_back(A[i+1]-A[i]);
	
	V=Zalgo(V);
	int res=0;
	for(i=W;i<V.size();i++) if(V[i]>=W-1) res++;
	cout << res << endl;
	
}

まとめ

Writeは差分を取ることに気づく人があまりいないと思ってこの問題をDに置いたようだが、想像以上に気づいた人は多かったようだ。
自分もわりとあっさり気づいたしね。