MemSQL start[c]up Round 2 : A. Banana

Round2は不参加なので練習のみ。
http://codeforces.com/contest/335/problem/A

問題

アルファベットで構成される文字列Sと、自然数Nが与えられる。

ここで、あるN文字の文字列Tを準備し、Tをいくつか集めて、Sを再現できるだけのアルファベットを集めたい。
Sの再現に必要なTの数を最小にするようなTと、集める数を答えよ。

解法

Sが1000文字なので、Tを集める数も1000以下。
よって、集める数を1～1000で順にループさせ、T内に必要な各アルファベットの数を数えて総和がN以下になるようにすればよい。

string S;
int N,oc[26];

void solve() {
	int f,r,i,j,k,l,x,y;
	
	cin>>S>>N;
	FOR(i,S.size()) oc[S[i]-'a']++;
	
	for(i=1;i<=1000;i++) {
		j=0;
		FOR(k,26) j+= (oc[k]+(i-1))/i;
		if(j<=N) {
			_P("%d\n",i);
			string S;
			FOR(k,26) FOR(j,(oc[k]+(i-1))/i) S+=(char)(k+'a');
			while(S.size()<N) S+="a";
			cout << S << endl;
			return;
		}
	}
	_P("-1\n");
}

まとめ

Round2とはいえずいぶん簡単だな。