torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 670, Division 1, Level 1 : Bracket107

問題概要

 '(' と ')' からなる,括弧がバランスした文字列 $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;
	}
};