TopCoder SRM 648 Div1 Easy AB

シンプルな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13642

問題

'A'と'B'で構成されたN文字の文字列Sを考える。
(i,j)となる数値のペアのうち、0≦i＜j＜NかつS[i]＜S[j]となるものがK個となるSを答えよ。

解法

'A'がa個、'B'が(N-a)個あれば、0～(a*(N-a))個の範囲で任意のペアを作れる。

先にBを(N-a)個配置し、AをB何個の左に置くか考えていけばよい。
残りペア数がpなら、min(p,N-a)個のBの左にAを追加していく。
以下ではaを総当たりしているが、a=N/2の時が最大なのは明らか。

class AB {
	public:
	string createString(int N, int K) {
		int i,j,k;
		for(int na=0;na<=N;na++) {
			int nb=N-na;
			if(na*nb<K) continue;
			k=K;
			vector<int> V;
			FOR(i,na) {
				int x=min(nb,K);
				V.push_back(x);
				K-=x;
			}
			string S;
			for(int x=nb;x>=0;x--) {
				FOR(j,V.size()) if(V[j]==x) S+="A";
				if(x) S+="B";
			}
			return S;
			
		}
		return "";
	}
}

まとめ

シンプルな問題設定。
Div1 Easyとしては簡単な気もするけど、たまにはいいのかな。