TopCoder, Single Round Match 648, Division 1, Level 1 : AB

問題文

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

問題概要

　二つの正整数 が与えられる．次の条件を満たす文字列 を 1 つ求めよ．存在しない場合は空文字列で示せ．

• は 文字からなり， を構成する各文字は 'A' または 'B' である
• 整数の順序対 であって， = 'A' かつ = 'B' を満たすものの個数が丁度 個

　

解法

　かしこい解法が思い付かなかったので動的計画法で通しました．
　空文字列から初めて，1 文字ずつ文字を追加していくことを考えます．同じ数の文字を追加した状態が複数あったとして，構築途中の文字列に含まれる 'A' の数と，条件を満たすインデックスのペアの数が等しいような状態から得られる結果は同じになります．従って，次のような動的計画法を考えることができます．

• dp[ 文字追加した文字数 ][ 'A' の数 ][ 条件を満たすインデックスのペアの数 ] := 作れるか否か

状態 dp[ i ][ j ][ k ] からの遷移は次に追加する文字を両方とも試すことになるので，

• 'A' を追加する -> dp[ i + 1 ][ j + 1 ][ k ] を更新
• 'B' を追加する -> dp[ i + 1 ][ j ][ k + j ] を更新

の 2 通りになります．インデックスのペアの総数が 個であることを踏まえると，状態数は となり， の制約に対して十分小さいのでこれで間に合います．
　更に，各パラメータに対して，文字列を作れる場合には直前に追加した文字を判別できるような値を入れておくことで，状態遷移を逆に辿って文字列を復元することができます．

コード

#define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define ALL( c ) ( c ).begin(), ( c ).end()
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )

int dp[ 64 ][ 64 ][ 4096 ];

class AB
{
public:
	string createString( int N, int K )
	{
		{
			fill( AALL( dp, int ), -1 );
		}
		dp[0][0][0] = 0;

		REP( i, N )
		{
			REP( j, N )
			{
				REP( k, K + 1 )
				{
					if ( dp[i][j][k] == -1 )
					{
						continue;
					}

					REP( l, 2 )
					{
						const int nk = l == 0 ? k : k + j;
						dp[ i + 1 ][ j + !l ][ nk ] = l;
					}
				}
			}
		}

		int a = -1;
		REP( j, N + 1 )
		{
			if ( dp[N][j][K] != -1 )
			{
				a = j;
			}
		}
		if ( a == -1 )
		{
			return "";
		}

		string s;
		for ( int i = N, k = K; 0 < i; --i )
		{
			if ( dp[i][a][k] == 0 )
			{
				s += 'A';
				--a;
			}
			else
			{
				s += 'B';
				k -= a;
			}
		}
		reverse( ALL( s ) );
		return s;
	}
};