SRM 648 DIV1 Easy - AB (×)

March 16, 2015

問題

・文字の長さがNであり、’A’か’B’から成る文字列を作りたい。
・ただし、Aより後ろのどこかにBがあるペアをK個作りたい。
・そのような文字列を作れない場合は-1を、作れる場合はそのような文字列のうち一つを出力する。

解き方

・最大のペア数はN/2 * (N-N/2)であるので、これよりもKが大きければそのような文字列を
　作れない。

・作れる場合は実装するだけ。Aを出力するときに、それより右にあるべきBの数を保存してあげるように解いた。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class AB {

public: string createString(int N, int K) {

string ret="";
for(int a=0;a<=N/2;a++){
int b=N-a;
if(a*b<K)continue;

vector<int> v;
FORE(i,0,a){
int x=min(b,K);
v.push_back(x);
K-=x;
}

FORE(i,0,v.size()){
while(v[i]<b){
ret+='B';
b--;
}
ret+='A';
}
while(b){
ret+='B';
b--;
}

return ret;
}

return "";
}

};

実装