TopCoder SRM 593, Division 2, Level 2 : WolfDelaymaster

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12778&rd=15705

概要

次のような文字列を valid であるとする。

1. ある正整数 k があって、k 個の 'w' の連続 + k 個の 'o' の連続 + k 個の 'l' の連続 + k 個の 'f' の連続 である文字列
2. valid な文字列を連結したもの

'w', 'o', 'l', 'f' からなる文字列 str が与えられる。
str が valid かどうか求めよ。

解法

やりようはいくつかありますが、典型的な区間 DP で解いてみました。
　dp[ l ][ r ] := 区間 [ l, r ) が valid かどうか
として DP できます。
dp[ l ][ r ] の計算は次のようになります。

1. [ l, r ) に対応する str の部分文字列がルール 1 により規定される単語のどれかであれば valid
2. そうでないとき、[ l, r ) の分割を全て試し、両側とも valid になるものがあれば valid
3. それ以外のときは invalid

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

class WolfDelaymaster
{
public:
	int N;
	string str;

	VS words;
	VVI dp;

	string check( string str )
	{
		// initialize of localtest
		{
			words.clear();
			dp.clear();
		}

		this -> N = str.size();
		this -> str = str;
		dp.resize( N + 1, VI( N + 1, -1 ) );
		
		for ( int i = 1; i * 4 <= N; i++ )
		{
			string s;
			REP( j, 0, 4 )
			{
				s += string( i, string( "wolf" )[j] );
			}
			words.PB( s );
		}
		sort( ALL( words ) );

		return rec( 0, N ) ? "VALID" : "INVALID";
	}

	bool rec( const int l, const int r )
	{
		if ( dp[l][r] != -1 )
		{
			return dp[l][r];
		}

		if ( binary_search( ALL( words ), str.substr( l, r - l ) ) )
		{
			return dp[l][r] = 1;
		}

		REP( i, l + 1, r )
		{
			if ( rec( l, i ) && rec( i, r ) )
			{
				return dp[l][r] = 1;
			}
		}
		return dp[l][r] = 0;
	}
}