問題
・文字の長さが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 "";
}
};
#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 "";
}
};