Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-26SRM360, SRM361 (Practice)

SRM 361 WhiteHats

|  SRM 361 WhiteHats - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 361 WhiteHats - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8010

  • 方針検討しながら行き当たりばったりで書いた
    • まず、各人が報告した数は2種類か1種類のはず
    • 1種類の時
      • 被ってる帽子は全て同じ色
      • 数が0なら全員黒、数が(人数-1)のときは全員白
    • 2種類の時
      • (報告した数の最大) - (最小) = 1 で、最大が白い帽子を被ってる人の数
      • さらに、大きな数を報告した人は全員黒、小さい数を報告した人は全員白
      • 以上を数えて検証する
import java.util.HashSet;
import java.util.Set;

public class WhiteHats {
	public int whiteNumber(int[] count) {
		int people = count.length;
		int many = -1;
		int less = 50;
		Set<Integer> a = new HashSet<Integer>();
		for (int i = 0 ; i < people ; i++) {
			many = Math.max(many, count[i]);
			less = Math.min(less, count[i]);
			a.add(count[i]);
		}
		if (a.size() >= 3) {
			return -1;
		} else if (a.size() == 1) {
			if (many == 0) {
				return 0;
			} else if (many == people - 1) {
				return people;
			} else {
				return -1;
			}
		}
		
		int black = 0;
		int white = 0;
		for (int i = 0 ; i < people ; i++) {
			if (count[i] == many) {
				black++;
			} else {
				white++;
			}
		}
		if (white == many && white - 1 == less) {
			return white;
		}
		return -1;
	}
}