torus711 のアレ

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

TopCoder, Single Round Match 649, Division 2, Level 1 : DecipherabilityEasy

問題概要

 2 つの文字列 s, t が与えられる.s から 1 文字を削除することで,t を作ることができるか?
 |s| \leq 50

解法

 |s| = L と書きます.
 文字列長が短いので全探索で解くことを考えます.s からある 1 文字を削除した新しい文字列を作る操作は,O( L ) でできます.消す文字の候補の数も同じく O( L ) 箇所なので,生成可能な文字列の全てを O( L^2 ) 時間で列挙できます.
 生成された各文字列と t との比較は O( L ) 時間でできるので,結局,O( L^2 ) 時間で t と一致するものがあるかを調べられます.

コード

#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 SZ( v ) ( (int)( v ).size() )

class DecipherabilityEasy
{
public:
	string check( string s, string t )
	{
		const int L = SZ( s );
		REP( i, L )
		{
			string tmp = s;
			tmp.erase( i, 1 );
			if ( tmp == t )
			{
				return "Possible";
			}
		}
		return "Impossible";
	}
};