TopCoder SRM 835 : Div1 Medium MostPeriodic

こっちは割とすんなり解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=17776

問題

この問題において、文字列Sの周期がLであるとは、i+L＜|S|の場合、S[i]=S[i+L]であることを意味する。
|S|の長さがLの倍数でなくてもこの定義は成り立つことに留意せよ。

文字列Bが与えられる。
Bを並べ替え、最小の周期となるものを答えよ。

解法

Bが同じ文字列TがR回続き、最後にTのprefixが後ろにつくようなケースを考える。
Rを総当たりしながら、Tの候補を探そう。
各文字の登場回数をCとしたとき、X*R+Y=Cと表現できる、X≧Yかつ最小のXを求めよう。
この時、Tにこの文字はX回含まれ、Bの最後につくTのprefix中にY回含まれるようにすればよい。

class MostPeriodic {
	public:
	string construct(string bank) {
		int N=bank.size();
		int C[26]={};
		FORR(c,bank) C[c-'A']++;
		int step,i,rep;
		for(rep=N;rep>=1;rep--) {
			int X[26],Y[26];
			int num=0;
			int ok=1;
			FOR(i,26) {
				X[i]=0;
				Y[i]=C[i];
				while(1) {
					if(X[i]>=Y[i]) break;
					if(Y[i]>=rep) {
						X[i]++;
						Y[i]-=rep;
					}
					else {
						break;
					}
				}
				if(X[i]<Y[i]) break;
			}
			if(i!=26) continue;
			string S;
			int j,x;
			FOR(x,rep) {
				FOR(i,26) {
					FOR(j,Y[i]) S+='A'+i;
				}
				FOR(i,26) {
					FOR(j,X[i]-Y[i]) S+='A'+i;
				}
			}
			FOR(i,26) {
				FOR(j,Y[i]) S+='A'+i;
			}
			return S;
			
		}
		
	}
}

まとめ

Easyは誤ジャッジ除いても間違ってたので、せっかくMedium早く解けたのにあんまり意味なかったな。