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; } };