AOJ_2102 ラミー

雪がかなり降っている。寒いいいい
実装がかなり難しかった。実装力ないのをどうにかしたい。
問題
略
解法
色ごとにカードをわけ、3枚ずつ選ぶ選び方をすべて試すというやり方をした。
カード1セットあたり最悪でも3*9C3*6C3=5040の計算しかしないので間に合う。(枝刈りするともっとはやくなる)
あと、各色のカードの枚数が3の倍数でないのはすぐやめる。

実装

#include <cstdio>
#include <algorithm>
using namespace std;

int card[3][9];
int rgbn[3];

bool used[9];
bool c3(int c[3]){
	sort(c, c + 3);
	if(c[0] == c[1] && c[1] == c[2]) return true;
	if(c[0] + 1 == c[1] && c[1] + 1 == c[2]) return true;
	return false;
}
bool c9(const int col, int n, const int card3[3]){
	if(rgbn[col] % 3 != 0) return false;
	int next_card[3];
	for(int i = 0; i < 3; i++) next_card[i] = card3[i];

	if(n % 3 == 0){
		if(!c3(next_card))
			return false;
		else
			if(n == 9) return true;
	}

	bool f = false;
	for(int i = 0; i < 9; i++){
		if(used[i]) continue;
		used[i] = true;
		next_card[n % 3] = card[col][i];
		f = f || c9(col, n + 1, next_card);
		used[i] = false;
	}
	return f;
}
int solve(){
	const int C[] = {0, 0, 0};
	fill(used, used + 9, false);
	for(int i = 0; i < 3; i++){
		if(!c9(i, 0, C))
			return false;
	}
	return true;
}
int main(){
	int n;
	scanf("%d", &n);
	for(int k = 0; k < n; k++){
		int num[9];
		int col[9];
		char c;
		fill(rgbn, rgbn + 3, 0);
		for(int i = 0; i < 3; i++)
			fill(&card[i][0], &card[i][0] + 9, 0);
		for(int i = 0; i < 9; i++)
			scanf("%d", &num[i]);
		for(int i = 0; i < 9; i++){
			scanf("%c", &c);
			scanf("%c", &c);
			if(c == 'R')		col[i] = 0;
			else if(c == 'G')	col[i] = 1;
			else if(c == 'B')	col[i] = 2;
		}
		for(int i = 0; i < 9; i++){
			card[col[i]][rgbn[col[i]]] = num[i];
			rgbn[col[i]]++;
		}
		if(solve()) printf("1\n");
		else printf("0\n");
	}
	return 0;
}