TopCoder SRM 670, Division 1, Level 1 : Bracket107

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=14059&rd=16550

問題概要

　'(' と ')' からなる，括弧がバランスした文字列 $S$ が与えられる．4 つの性質，

• 長さが $S$ と等しい
• 括弧がバランスしている
• $S$ と等しくない
• $S$ との最長共通部分列 (LCS) の長さが最長

を満たす文字列の総数を求めよ．

• $4 \leq |S| \leq 50$

解法

　括弧がバランスした文字列の総数は（多分）大きくなるので，まずは $S$ との LCS の長さの最適値について考えます．")(" という部分か，"()" という部分（どちらかは必ず含まれる）を swap すると 長さ $|S| - 1$ の LCS をもつ文字列を得られるので，LCS の長さの最適値は $|S| - 1$ となります．これは言い換えると，$|S| - 1$ 文字は $S$ 中と同じ順序で表れるということです．つまり，条件を満たす文字列とは，$S$ から 1 文字を選んで別の場所に挿入した文字列となります（開き括弧・閉じ括弧の総数は変えられないので，選んだ文字を入れるしかない）．これに加えて，括弧がバランスしていれば，数え上げるべき文字列となります．
　この解法は，文字の選び方・挿入の仕方がそれぞれ $O( |S| )$ 通りで，文字の挿入・ validness のチェックに $O( |S| )$ 時間かかるので，全体で $O( |S|^3 )$ 時間となります．

コード

using VI = vector< int >;
using VVI = vector< vector< int > >;

#define REP2( i, n ) REP3( i, 0, n )
#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 FOR( e, c ) for ( auto &e : c )

#define SZ( v ) ( (int)( v ).size() )

class Bracket107
{
public:
	int yetanother( string S )
	{
		const int L = SZ( S );

		set< string > res;
		REP( i, L )
		{
			const char c = S[i];

			REP( j, L )
			{
				string T( S );
				T.erase( i, 1 );
				T.insert( j, 1, c );

				if ( valid( T ) && S != T )
				{
					res.insert( T );
				}
			}
		}
		return SZ( res );
	}

	bool valid( const string &S )
	{
		int depth = 0;
		FOR( c, S )
		{
			depth += c == '(' ? 1 : -1;
			if ( depth < 0 )
			{
				return false;
			}
		}
		return depth == 0;
	}
};