CODE FESTIVAL 2017 Qual B : F - Largest Smallest Cyclic Shift

すいません手抜き解説です。
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_f

問題

a,b,cがX,Y,Z個含まれる文字列Sを考える。
f(S)をSを巡回させたときの辞書順最小な文字列とする。
f(S)の最大値を求めよ。

解法

{"a","a",...,"b","b",..,"c","c",...}という文字列の配列を作り、ソートして先頭と末尾をくっつける、を要素が1個になるまで繰り返すと通る。
…実際通ってしまうのだが、AtCoderでは厳密に証明できていないということでこの解は想定解としていないようだ。
自分もなんとなく通りそうな気がしてSubmitしたら通ってしまったのだが、確証は持てていない。

というわけで、想定解はEditorialを見てもらった方が良いかと。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int A,B,C;
	cin>>A>>B>>C;
	vector<string> V;
	while(A--) V.push_back("a");
	while(B--) V.push_back("b");
	while(C--) V.push_back("c");
	
	while(V.size()>1) {
		sort(ALL(V));
		V[0]+=V.back();
		V.pop_back();
	}
	
	cout<<V[0]<<endl;
}

まとめ

証明簡単そうで難しいんだな…。