SRM592 Div1 Easy - LittleElephantAndBalls

問題

ボールをn個持っており、ボールiの色は左から順にs[i]である(s[i]は'R' か 'G' か 'B')
これを左から順に空のテーブルに一列に置いていく
ボールiを置くとき、
ボールの列の端に置く場合) 元のボールの列に含まれるボールの色の種類数をスコアに加える
ボールの列の隙間に置く場合) その隙間の左右それぞれの列に含まれるボールの色の種類数の和をスコアに加える
最終的に得られるスコアの最大値を求めよ

1 <= n <= 50

解法

ちょっと考えると、毎回
テーブルのボールの列の長さが偶数のとき) 列の真ん中
そうでないとき) 列の左半分と右半分で今加えようとしてるボールの色が含まれない方があればそっち側の一番真ん中に近い隙間、そうでなければどっちでもいい
にボールを置き続けるのが最善であることがわかる
今列にある各色のボールを最大2個まで数えておいて、それらの和を答えに足していけばいい

class LittleElephantAndBalls {
public:
	int getNumber(string s) {
		int res = 0, a[3] = {};
		each(i,s) {
			res += accumulate(a,a+3,0);
			if (i=='R') a[0] = min(2, a[0]+1);
			else if (i=='G') a[1] = min(2, a[1]+1);
			else a[2] = min(2, a[2]+1);
		}
		return res;
	}
};