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とはいえずいぶん簡単だな。