TopCoder SRM 801 : Div1 Medium EquivalentStrings

周りみんな早くて焦った。
https://community.topcoder.com/stat?c=problem_statement&pm=16824&rd=18530

問題

(いくつかの文字列をrotateしてられる)N個の文字列が与えられる。
各文字は0～9で構成される。
文字の差が2以上である隣接文字を、任意に入れ替えられるとする。
この時、この手順で互いに交換可能な文字列は等しいと定義する。

元のN個の文字列について、等しいものを同じグループとしてまとめたとき、何個のグループを構成できるか。

解法

この手順は可逆なので、同じ辞書順最小の文字列を作れる文字列同士は等しい。
そこで、文字列Sから上記手順で生成できる辞書順最小の文字列Tを構成し、uniqueなものを数え上げよう。

まず、文字列の各位置において、直前にある文字の差が1以内の文字の位置を覚えておこう。
Tの先頭から、0～9のどの文字cを末尾に追加するかを考えている。
辞書順最小の文字列を作りたいので、cを小さい方からどん欲に試す。
Sの中のcのうちまだTの中に入っていない最も手前の位置を求めよう。
「直前にある文字の差が1以内の文字の位置」がわかっているので、それらが全部Tに中に入っているなら、Sの対象の文字をTに加えよう。
そうでないなら次のcを試す。

これで文字列当たりO(c|S|)で処理できる(cは文字の種類)

class EquivalentStrings {
	public:
	string trans(string S) {
		vector<int> pep[2525];
		int did[2525]={};
		int C[10];
		int fin[10];
		int i,j;
		queue<int> cand[10];
		FOR(i,10) {
			C[i]=fin[i]=-1;
		}
		FOR(i,S.size()) {
			cand[S[i]-'0'].push(i);
			pep[i].push_back(C[S[i]-'0']);
			if(S[i]!='9') pep[i].push_back(C[S[i]-'0'+1]);
			if(S[i]!='0') pep[i].push_back(C[S[i]-'0'-1]);
			C[S[i]-'0']=i;
		}
		
		string T;
		
		FOR(i,S.size()) {
			int j;
			FOR(j,10) if(cand[j].size()) {
				int x=cand[j].front();
				int ok=1;
				FORR(p,pep[x]) if(p>=0 &&did[p]==0) ok=0;
				if(ok) {
					T.push_back('0'+j);
					did[x]=1;
					cand[j].pop();
					break;
				}
			}
		}
		
		return T;
	}
	
	int count(vector <string> seeds) {
		set<string> V;
		FORR(v,seeds) {
			int N=v.size(),j;
			FOR(j,N) {
				V.insert(trans(v));
				v=v.substr(1,N-1)+v.substr(0,1);
			}
		}
		
		return V.size();
	}
}

まとめ

もっと簡潔にやる方法もあったみたいだけども。