torus711 のアレ

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

TopCoder SRM 577, Division 2, Level 1 : EllysNewNickname

概要

与えられた文字列から、連続する母音を排除したときの最長の長さを求めよ。

解法

まず、子音を消すことに意味はありません。
得られる文字列の長さが短くなる上、隣り合わない母音が隣り合ってしまう場合があるためです。
子音を消さないとすると、考慮するべきなのは母音が連続する箇所のみとなります。

連続する母音について、一つを残して消去する必要があります。
消去される数は、連続する母音の長さ - 1 です。
これは、母音が連続する箇所の数と言い換えることができます。
母音が連続する箇所の数は、有効な i, i + 1 について、s[i] と s[ i + 1 ] の両方が母音であるような i の数です。
元の文字列の長さからこの値を引くと最適な結果を得られます。

コード

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

const string vowels = "aeiouy";

class EllysNewNickname
{
public:
	int getLength( string nickname )
	{
		int res = nickname.size();;
		REP( i, 0, nickname.size() - 1 )
		{
			res -= vowels.find( nickname[i] ) != string::npos && vowels.find( nickname[ i + 1 ] ) != string::npos;
		}
		return res;
	}
}