SRM 507 250pt: CubeStickers

問題概要

色を示す文字列が複数与えられる。それらを使って隣り合う色が異なるようにサイコロの面を塗れるか判定する問題。

解法

場合分けして手で解ける。

感想

手で解くのは遅いし、抜けもよく起こるのであまり好ましくない。でもこの問題は結局綺麗な解法が思いつかなかった。

class CubeStickers {
public:
string isPossible(vector <string> sticker) {
	map<string, int> dict;
	for(int i=0; i<(int)sticker.size(); i++){
		dict[sticker[i]]++;
	}
	vector<int> xs;
	for(typeof(dict.begin()) itr = dict.begin(); itr != dict.end(); itr++){
		xs.push_back(itr->second);
	}
	return sub(xs)?"YES":"NO";
}

bool sub(vector<int> xs){
	if(xs.size() >= 5) return true;
	if(xs.size() < 3) return false;
	sort(xs.begin(), xs.end());
	if(xs.size()==3){
			return xs[0] >= 2;
	}
	if(xs.size()==4){
		return xs[2] >= 2;
	}
	return true;
}