TopCoder SRM 592, Division 1, Level 1 : LittleElephantAndBalls

概要

三種類のボールがあり、それぞれの色は 'R', 'G', 'B' で表される。
これらのボールを決まった順番で一列に並べる
ボールは列の好きな位置に挿入することができて、挿入する位置と列の状態によって毎回スコアを得る。
スコアは次のように計算される

• 既に置かれているボールが 0 個のとき : 0
• 列のどちらかの端に置くとき : 列中で異なる色の数
• それ以外の位置に挿入するとき : 挿入する場所で列を分割して、それぞれの中で異なるボールの色の数の和

得ることができる合計スコアの最大値を求めよ。

解法

まず、ボールが二つ以上あるときに列の端に挿入する操作は完全に無駄になります。
（どこか中間に入れたとき以下のスコアしか取れない）

新しいボールを挿入する場所を基準にして考えます。
このとき、挿入済みのボールは二つのグループに分けられます。
それぞれのグループに含まれる色の数を足しあわせていけば最適解が得られます。
新しく挿入するボールは、その色が無い方のグループがあればそっちに入れます。
まとめると、色毎に挿入済みの個数を数えておいて、min( 2, 個数 ) を足し合わせた値が、そのときに得られるスコアです。

コード

typedef vector<int> VI;

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

class LittleElephantAndBalls
{
public:
	int getNumber( string S )
	{
		const int N = S.size();
		map<char,int> color_id = { MP( 'R', 0 ), MP( 'G', 1 ), MP( 'B', 2 ) };

		int res = 0;
		VI counts( 3, 0 );
		REP( i, 0, N )
		{
			res += accumulate( ALL( counts ), 0 );

			const int p = color_id[ S[i] ];
			counts[p] = min( counts[p] + 1, 2 );
		}
		return res;
	}
};