torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 618, Division 2, Level 2 : LongWordsDiv2

問題概要

 英大文字からなる文字列 word が与えられる。word が以下の条件を共に満たすかどうかを判定せよ。

  • 同じ文字が連続しない
  • ある二つの文字 x, y (同一でもよい)があって、xyxy となる部分列が存在しない

解法

 word の長さを L と書きます。
 それぞれの条件は互いに独立なので、それぞれ別に判定することを考えます。
 一つ目の条件は、各 i ( 0 ≦ i < L - 1 ) について、word[ i ] と word[ i + 1 ] が異なることを確かめることで判定できます。これは単純なループにより O( L ) で完了します。
 二つ目の条件は、長さ 4 の部分列を全て試して、xyxy なるものが存在するかを確かめることで判定できます。すなわち、各 i, j, k, l ( 0 ≦ i < j < k < l < L ) について、word[ i ] == word[ k ] && word[ j ] == word[ l ] を満たすものが存在すれば、二つ目の条件を満たさないと分かります。この処理は O( L^4 ) できつめですが、定数が軽いので案外余裕で通ります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class LongWordsDiv2
{
public:
	string find(string word)
	{
		return check1( word ) && check2( word ) ? "Likes" : "Dislikes";
	}

	bool check1( const string &S )
	{
		REP( i, 0, S.size() - 1 )
		{
			if ( S[i] == S[ i + 1 ] )
			{
				return false;
			}
		}
		return true;
	}

	bool check2( const string &S )
	{
		const int L = S.size();

		REP( i, 0, L )
		{
			REP( j, i + 1, L )
			{
				REP( k, j + 1, L )
				{
					REP( l, k + 1, L )
					{
						if ( S[i] == S[k] && S[j] == S[l] )
						{
							return false;
						}
					}
				}
			}
		}

		return true;
	}
};