CSAcademy Round #22 : D. Distinct Rotations

ECRと行ったり来たりしてたので時間がかかった。
https://csacademy.com/contest/round-22/#task/distinct_rotations

問題

0,1で構成された文字列Sが与えられる。
ただし一部はワイルドカードとなっている。
このSを繰り返しrotationさせたとき、登場する相異なる文字列の種類が最小となるようにしたい。
そのようにワイルドカードに0,1を割り当てよ。
また、種類数が同じになるものが複数あるなら、辞書順最小のものを求めよ。

解法

種類が最小ということは、周期が最大となるものを探せばよい。

S	の約数dを大きい順に試し、Sが周期dの文字列となるか判定すればよい。

すなわち、S[i]==S[(i+d)%|S|]を満たすように0,1を割り当てよう。
S[i]=S[i+d]=...='?'とすべてがワイルドカードの場合、辞書順最小にするために0を割り当てればよい。

int N;
string S;
string T;
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	for(i=1;i*i<=N;i++) {
		if(N%i==0) {
			V.push_back(i);
			if(i*i!=N) V.push_back(N/i);
		}
	}
	sort(ALL(V));
	FORR(r,V) {
		
		
		T=S.substr(0,r);
		for(i=r,j=0;i<N;i++,j++) {
			if(j==r) j=0;
			
			if(T[j]=='?') T[j]=S[i];
			else if(S[i]=='?') T[j]=T[j];
			else if(S[i]!=T[j]) break;
		}
		if(i==N) {
			FORR(r,T) if(r=='?') r='0';
			FOR(j,N/r) cout<<T;
			cout<<endl;
			return;
		}
	}
	
}

まとめ

最初逆に周期最長のものを作れと勘違いしてしまい手間取った。