kmjp's blog

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

Codeforces #425 Div2 E. Vasya and Shifts

本番方針は思いついたものの時間切れ。
http://codeforces.com/contest/832/problem/E

問題


a~eの5種類の文字からなる文字列を使った文字列の変化を考える。
M文字の文字列Aに、同じくM文字の文字列Bを適用して変化されることを考える。
B[i]が0-originでj番目の文字列の場合、A[i]はj個進む。なおeの次はaに戻るよう循環する。

さて、ここでN個の変化用文字列が与えられる。
初期状態が'a'M個からなる文字列を、各変化用文字列を0~4回まで適用して変化させていくことを考える。

ここでQ個のクエリが与えられる。
各クエリは同じくM文字の文字列からなる。
初期状態の文字列をクエリ中の文字列にするために適用する変化用文字列の組み合わせが何通りかを求めよ。

解法

まず単一のクエリについて考える。
各添え字に対する制限を考えると、連立1次方程式を成すことができる。

元のN個の変化用文字列から、M行N列の行列Aを作ろう。
A_ij = j個目の変化用文字列のi文字目が何番目のアルファベットか
クエリの文字列を同様にM行の縦ベクトルVとみなすと、これはAx-V=0を満たすxの組み合わせ数を求める問題となる。

rank(A)とrank(A|V)が一致するなら、そのようなxが存在する。またxは5^(N-rank(A))通りとなる。
rank(A)とrank(A|V)が一致しないなら、xは存在しない。
よってrank(A)およびrank(A|V)を掃出し法で求めれば回答できる。

なお、Q個のクエリそれぞれについてrank(A|V)を求めようとするとO(N*M*min(N,M)*Q)程度かかり間に合わない。
そこで全クエリ分まとめて処理しよう。
各クエリに対応する縦ベクトルをV[i]としたとき、(A|V[0]|V[1]|...|V[Q-1])という拡大係数行列を作り、先頭N列まで掃出そう。
各V[i]に対応する列に非0成分が残っているなら、rank(A|V[i])!=rank(A)ということがわかる。

これなら掃出し法を1回行えばよく、O(M(N+Q)^2)程度で済む。

int N,M,Q;
string S[505],T;
int mo=5;
int mat[500][800];

int rev(int a) {
	int revt[]={0,1,3,2,4};
	return revt[a];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) {
		cin>>S[y];
		FOR(x,M) mat[x][y]=S[y][x]-'a';
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>T;
		FOR(x,M) mat[x][N+i]=T[x]-'a';
	}
	
	ll pat=1;
	int step=0,ret=0;
	FOR(step,N) {
		for(y=ret;y<M;y++) if(mat[y][step]) break;
		if(y==M) {
			pat=pat*5%1000000007;
			continue;
		}
		for(x=step;x<N+Q;x++) swap(mat[ret][x],mat[y][x]);
		int re=rev(mat[ret][step]);
		for(x=step;x<N+Q;x++) mat[ret][x]=mat[ret][x]*re%mo;
		
		FOR(y,M) if(y!=ret && mat[y][step]) {
			re=mat[y][step];
			for(x=step;x<N+Q;x++) mat[y][x]=((mat[y][x]-re*mat[ret][x])%mo+mo)%mo;
		}
		ret++;
	}
	
	
	FOR(i,Q) {
		for(x=ret;x<M;x++) if(mat[x][N+i]) break;
		if(x==M) cout<<pat<<endl;
		else cout<<0<<endl;
	}
	
	
}

まとめ

本番だとTLE無視してO(N*M*min(N,M)*Q)で撃沈してたな。
まとめて掃き出すテクは今後も使えそう。