SRM 361 250pt : WhiteHats

問題概要

黒か白の帽子を被ったものがN(<50)人いる。自分の帽子の色は分からない。各人に対して、白の帽子を被った人が何人見えるかが与えられる。それがvalidであるとき、白の帽子を被っている人が何人いるか求める問題。

解法1

出てくる数字が何種類あるか場合分けして、正当性をチェックして合っているかどうかを判定する。

解法2

場合分けとかミスの可能性が増えるだけなので、多少計算量が悪くなっても時間内に動くなら一緒だよ、という方針の元で答えに関して全探索する。
解法1

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

struct WhiteHats {

	int whiteNumber(vector <int> count) {
		set<int> ns;
		int N = count.size();
		for(int i=0; i<N; i++){
			ns.insert(count[i]);
		}
		if((int)ns.size() == 1){
			int x = count[0];
			if(x == N-1){
				return N;
			}
			else if(x == 0){
				return 0;
			}
			return -1;
		}

		else if((int)ns.size() == 2){
			int black = *min_element(count.begin(), count.end()),
					white = *max_element(count.begin(), count.end());
			if(black == white - 1 && std::count(count.begin(), count.end(), black) == white){
				return white;
			}
		}
		return -1;
	}

};

解法2

#include <vector>
using namespace std;

struct WhiteHats {

	int whiteNumber(vector <int> count) {
		for(int r=0, N=count.size(); r<=N; r++){
			int black_cnt = 0, white_cnt = 0;
			for(int i=0; i<N; i++){
				if(count[i] == r){
					black_cnt++;
				}
				else if(count[i] == r-1){
					white_cnt++;
				}
			}
			if(white_cnt == r && black_cnt == N - r){
				return r;
			}
		}
		return -1;
	}

};