mayoko’s diary

プロコンとかいろいろ。

SRM648div2hard:ABC

なんとなく解法は覚えていたがstringとcharの変換周りで悩まされた。

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

解法:下のソースコードのコメントに書いてあるとおり、「dp[n][a][b][k]: n文字中a文字をA,b文字をB,で埋めている時、ペアの数がkになるような文字が存在する時、最後のcharを埋める ないときは'?'」というメモ配列を用意する。埋め方は簡単で、まずdp[1][1][0][0] = 'A'となることは明らか。また、次の文字を'B'にすると今までに'A'としていた分だけペアが増え、次の文字を'C'にすると今までに'C'としていた分だけペアが増える。
また、dpを埋めてからの復元方法も、同じような論法で逆向きにたどっていけばできる。char型だとstringの+演算子使えないーと思ってたけどsubstr使えば良かったのか・・・
以下ソースコード

const int MAXN = 32;
const int MAXK = 1000;
char dp[MAXN][MAXN][MAXN][MAXK]; // dp[n][a][b][k]: n文字中a文字をA,b文字をB,で埋めている時、ペアの数がkになるような文字が存在する時、最後のcharを埋める ないときは'?'

class ABC {
public:
    string createString(int N, int K) {
        memset(dp, '?', sizeof(dp));
        dp[1][1][0][0] = 'A';
        for (int n = 1; n < N; n++) {
            for (int a = 0; a <= n; a++) {
                for (int b = 0; b <= n-a; b++) {
                    for (int k = 0; k <= K; k++) {
                        if (dp[n][a][b][k] == '?') continue;
                        // aを埋める
                        dp[n+1][a+1][b][k] = 'A';
                        // bを埋める
                        dp[n+1][a][b+1][k+a] = 'B';
                        // cを埋める
                        dp[n+1][a][b][k+a+b] = 'C';
                    }
                }
            }
        }
        for (int a = 0; a <= N; a++) {
            for (int b = 0; b <= N-a; b++) {
                if (dp[N][a][b][K] != '?') {
                    string ans;
                    int k = K;
                    for (int i = 0; i < N; i++) {
                        printf("%d %d %d \n", a, b, k);
                        char c[1];
                        c[0] = dp[N-i][a][b][k];
                        string tmp = c;
                        ans += tmp;
                        if (c[0] == 'A') {
                            a--;
                        } else if (c[0] == 'B') {
                            k -= a;
                            b--;
                        } else {
                            k -= a+b;
                        }
                    }
                    reverse(ans.begin(), ans.end());
                    return ans;
                }
            }
        }
        return "";
    }
};