SRM648div1easy:AB

ここからしばらくは解き直しphaseなんだけど意外によくわからなかったりするので復習する意義はありそう。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13642&rd=16312

解法:題意のペアの数が最大になるのは明らかに,n=N/2としてN-n個Aを並べた後n個Bを並べたもの。この時ペアの数はn*(N-n)となるが、Kがこれより大きい時は解はない。
解が存在するときは、AAABBB->AABABB->AABBAB->AABBBAというようにAを右にずらして行くとペアの数が1ずつ減っていくことに注意して答えを求める。
以下ソースコード

class AB {
public:
    string createString(int N, int K) {
        int n = N/2;
        if (n*(N-n) < K) return "";
        string ret;
        for (int i = 0; i < N-n; i++) ret += "A";
        for (int i = N-n; i < N; i++) ret += "B";
        int cur = n*(N-n);
        int point = 0;
        while (1) {
            cout << cur << endl;
            if (cur == K) break;
            if (cur >= K+n) {
                swap(ret[N-n-point-1], ret[N-point-1]);
                cur -= n;
                point++;
            } else {
                int lastA = N-n-point-1;
                while (cur > K) {
                    swap(ret[lastA], ret[lastA+1]);
                    cur--;
                    lastA++;
                    cout << ret << endl;
                }
            }
        }
        return ret;
    }
};