HackerRank HourRank 30 : C. Diverse Strings

これは実験ゲーかな…。
https://www.hackerrank.com/contests/hourrank-30/challenges/diverse-strings

問題

文字列が盛り合わせであるとは、各文字の登場回数が異なることをいう。
N,Kの2値が与えられる。
以下の条件を満たすN文字の文字列Sを構成可能か。可能なら辞書順最小のものを示せ。

• Sは異なるアルファベットK種類からなる。
• Sの任意のprefix/suffixは盛り合わせである。

解法

アルファベットK種類からなる最短のSを考えよう。
各文字の登場回数が異なるためには、cnt(x) := 文字列中のxの登場回数　としたとき、任意のprefix/suffixにおいて
cnt('a')＞cnt('b')＞cnt('c')＞…とならなければならない。
とするとSはaで始まりaで終わる文字列になる。

この文字列がN'文字とする。
N＜N'なら解無し、N＞N'ならSの頭に(N-N')個'a'を追加したものを答えればよい。

肝心のSだが、解は以下の通り。
まず頭に(a)*2+(ba)*2+(cba)*2+(dcba)*2+....をアルファベットの先頭(K-1)個分に対して置く。
その後、アルファベット先頭K個分に対し...+(dcba)+(cba)+(ba)+aを置く。

確かにこれなら、prefixでもsuffixでもあるアルファベットの登場回数が増えそうなとき、その手前でより小さなアルファベットが登場するので、cnt('a')＞cnt('b')＞cnt('c')＞…の関係が保たれる。

int Q;
int N;
int K;

string ret;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N>>K;
		
		string S;
		for(i=1;i<=K-1;i++) {
			for(j=i;j>=1;j--) S.push_back('a'+j-1);
			for(j=i;j>=1;j--) S.push_back('a'+j-1);
		}
		for(i=K;i>=1;i--) {
			for(j=i;j>=1;j--) S.push_back('a'+j-1);
		}
		if(S.size()>N) {
			cout<<"NONE"<<endl;
		}
		else {
			S=string(N-S.size(),'a') + S;
			cout<<S<<endl;
		}
		
	}
}

まとめ

実験なしで一発でわかった人いるのかな…。