torus711 のアレ

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

TopCoder Single Round Match 564, Division 2, Level 1 : FauxPalindromes

概要

ある文字列について、左から読んだものと右から読んだものが一致するとき、文字列は PALINDROME(回文)であると言う。
また、ある文字列について、連続する同一文字を取り除いたものが回文であるとき、これを FAUX PALINDROME と言う。
(任意の回文は FAUX PALINDROME である)

文字列 word が与えられるので、以下の条件に従って結果を返却せよ。

  • word が回文 : "PALINDROME"
  • word は回文ではないが、FAUX PALINDROME :"FAUX"
  • word が上の二つの条件を満たさない : "NOT EVEN FAUX"

解法

やるだけ……。
回文の判定時のインデキシングが面倒だったのでコピーして反転したものと等値比較しています。
連続する文字を取り除く部分はベタ書きしましたが unique して erase した方が速くて確実だったと反省。

コード

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

class FauxPalindromes
{
public:
	string classifyIt( string word )
	{
		if ( ispal( word ) )
		{
			return "PALINDROME";
		}
		else if ( isfaux( word ) )
		{
			return "FAUX";
		}
		else
		{
			return "NOT EVEN FAUX";
		}
	}

	bool ispal( string str )
	{
		string rev( str );
		reverse( ALL( rev ) );

		return str == rev;
	}

	bool isfaux( string src )
	{
		char last = ' ';
		string str;

		REP( i, 0, src.size() )
		{
			if ( src[i] == last )
			{
				continue;
			}

			str += src[i];
			last = src[i];
		}

		return ispal( str );
	}
};