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 ""; } };