TopCoder, Single Round Match 648, Division 2, Level 3 : ABC

問題文

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

問題概要

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

• は 文字からなり， である．
• 整数の順序対 であって， を満たすものの個数が丁度 個

　

はい

　問題設定は，Division 1, Level 1 に 'C' が増えただけです． の制約が小さくなっているので，（ほぼ）同じ解法で通すことができます．つまり，以下の記述はコピペと修正によって生成されました．

解法

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

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

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

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

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

コード

#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[ 31 ][ 31 ][ 31 ][ 31 * 31 ];

class ABC
{
public:
	string createString( int N, int K )
	{
		{ // initialize for local test
			fill( AALL( dp, int ), -1 );
		}

		dp[0][0][0][0] = 0;

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

						dp[ i + 1 ][ j + 1 ][k][l] = 0;
						dp[ i + 1 ][j][ k + 1 ][ l + j ] = 1;
						dp[ i + 1 ][j][k][ l + j + k ] = 2;
					}
				}
			}
		}

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

		string res;
		for ( int i = N; i; --i )
		{
			const int c =dp[i][a][b][K];
			res += 'A' + c;

			switch ( c )
			{
				case 0:
					--a;
					break;
				case 1:
					K -= a;
					--b;
					break;
				case 2:
					K -= a + b;
					break;
			}
		}
		reverse( ALL( res ) );

		return res;
	}
};