TopCoder SRM 648 Div2 Hard ABC

Div1 Easyの良いアレンジ。
http://community.topcoder.com/stat?c=problem_statement&pm=13645

問題

基本的にDiv1 easyと同じ。
TopCoder SRM 648 Div1 Easy AB - kmjp's blog

ただしSを構成する文字はA,B,Cの３通りとなっている。

解法

dp[文字の位置][Aの数][Bの数][ここまでのペアの数]=このパターンが存在するなら、最後に追加した文字の数
として状態を持ち、DPをしていけば良い。
最後の文字までDPを行った後、ペア数がKになるパターンがあるならそこからバックトラックして文字列を組み立てる。

状態数がO(N^5)だが、文字の位置が手前のうちは(Aの数)(Bの数)(ペアの数)の上限が小さいので割と軽い。

char dp[40][40][40][950];

class ABC {
	public:
	string createString(int N, int K) {
		int i,a,b,x;
		ZERO(dp);
		dp[0][0][0][0]='A';
		
		FOR(i,N) {
			FOR(a,N+1) for(b=0;b<=N-a;b++) {
				FOR(x,948) if(dp[i][a][b][x]) {
					dp[i+1][a+1][b][x]='A';
					dp[i+1][a][b+1][x+a]='B';
					dp[i+1][a][b][x+a+b]='C';
				}
			}
		}
		
		FOR(a,N+1) for(b=0;b<=N-a;b++) if(dp[N][a][b][K]) {
			string s;
			while(N) {
				s+=dp[N][a][b][K];
				if(dp[N][a][b][K]=='A') a--;
				else if(dp[N][a][b][K]=='B') b--, K-=a;
				else K-=a+b;
				N--;
			}
			reverse(s.begin(),s.end());
			return s;
		}
		return "";
	}
}

まとめ

最初はDiv1 easyのように貪欲で解こうとしたけど面倒でDPにしてしまった。
貪欲でも行けるのかな？