ARC014 C-魂の還る場所

【問題】
arc014.contest.atcoder.jp

【考察】
N がそれなりに小さいのですが、ギリギリ半分全列挙はできないくらいの大きさ (そもそも効率的にマージする方法もなさそうですが)。そこで O(N^4) くらいの DP かなと思ってあれこれ考えてみるものの、箱に入ってる全てのボールの情報をもたないことには、どうやっても DP は不可能そう。ここでサンプルをよく見てみると、どちらのケースも解が小さいことに気づく。さらに軽く考察してみて、色ごとのボールの数を数えて奇数個あるものの種類数を出力するようにしたら AC。
軽く証明を考えてみます。奇数個ある色のボールは、どうやっても全て消すことができないので、少なくともこの解よりも小さい解を構成することはできません。次に、実際にこの解が構成できることを示します。まず、最初に入れる 2 つのボールが異なる色であるとしても一般性を失いません (初めのいくつかのボールが同じ色なら、それらは全て自動的に消えていくため)。仮にその 2 つのボールが赤色と青色であるとします。すると、次に赤か青のボールを入れるまでの間、円筒に入るボールは全て緑色です。この緑色のボールが偶数個の場合は、適当に片側に寄せてボールを入れていくことで、その全てを消すことができます。奇数個の場合は、仮に次に入れる緑以外のボールが赤色の場合、最後の 1 つを青色のほうに寄せて入れます。こうするとその赤色のボールを 2 つ並べて消したあとには、青色と緑色のボールが 1 つずつ残ることになります。このような操作を繰り返していけば、最終的に奇数個ある色のボールが 1 つずつ残るので、目的の解が構成できることが分かります (ちょっと議論を省略した)。
ちなみに枝刈り全探索してもギリギリ通るらしい。

【コード】

int main() {
	ios::sync_with_stdio(false);
	int N; string S; cin>>N>>S;
	int res=0;
	int rc=0,bc=0,gc=0;
	REP(i,N) {
		if(S[i]=='R') rc++;
		if(S[i]=='G') bc++;
		if(S[i]=='B') gc++;
	}
	res+=(rc%2!=0)+(bc%2!=0)+(gc%2!=0);
	cout<<res<<endl;
}

【使ったアイデア】
サンプルでエスパーする (解の予想をつける)。緩い制約に惑わされない。

【得た知見】
サンプルでエスパーしたほうが早い問題が存在する。