AtCoder Regular Contest #014, C : 魂の還る場所

問題文

http://arc014.contest.atcoder.jp/tasks/arc014_3

解法

あるボールを消せる場合は常に消してしまった方が得になります。
筒内部におけるそれぞれの端のボールの色と、今入れようとしているボールの色によって場合分けされます。

• どちらかの端が入れようとしている色と一致する -> 一致する側に入れて消す
• 入れようとしているボールと、次のボールの色が一致する -> 好きな方に入れる（次のターンで消される）
• それ以外 -> その次のボールの色と異なる色の方の端に入れる

（実は奇偶性だけでいけます）

コード

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

const int INF = INT_MAX / 4;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;
	string str;
	cin >> str;

	string cylinder;
	REP( i, 0, n )
	{
		if ( cylinder.empty() )
		{
			cylinder += str[i];
		}
		else if ( str[i] == cylinder[0] )
		{
			cylinder.erase( 0, 1 );
		}
		else if ( str[i] == cylinder.back() )
		{
			cylinder.erase( cylinder.size() - 1, 1 );
		}
		else
		{
			if ( i + 1 < n )
			{
				if ( str[i] == str[ i + 1 ] || str[ i + 1 ] == cylinder[0] )
				{
					cylinder += str[i];
				}
				else 
				{
					cylinder = string( 1, str[i] ) + cylinder;
				}
			}
			else
			{
				cylinder += str[i];
			}
		}
	}

	cout << cylinder.size() << endl;

	return 0;
}