SRM511 Div1 Easy - Zoo

TopCoder SRM
問題

各動物が「自分と同じ動物で、かつ自分より背の高い奴の数」はa[i]であると言っている
各動物はウサギかネコで、全ての動物の身長は異なる
全ての情報と矛盾しないようなウサギ・ネコの当てはめ方は何通りあるか

解法

答えが0通りのケースは以下の2つ

1) ex1{5,8} とか ex4{1,0,1} みたいに数が飛んでる(動物の数が足りない)パターン
前者は動物が9匹以上いないとあり得ない
後者は一番背が高いやつが1匹しかいないのに2番目に背が高いやつが2匹いるのはあり得ない

2) ex2{0,0,0,0,0} みたいに同じ値が3個以上ある(動物の種類数が足りない)パターン
動物の種類はウサギかネコしかないのに同種の中で一番背が高いやつが3匹以上いるのはあり得ない

これら以外の場合は答えは2^(k+m)
k: aに2回出てくる数字の個数
(aが同じ値である動物のペアはウサギ-ネコかネコ-ウサギの2通りどっちでもいい)
m: aに1回しか出てこない数字があれば1
(1回しか出てこない数字の動物は全てネコかウサギのどちらかに統一しないといけない)

実装

b[i]: 配列aに数字iが登場する回数
という配列を作り、これが全要素2以下である かつ 広義単調減少になっている かどうかチェックすれば、↑で書いた答えが0になるようなケースを両方弾ける

class Zoo {
	public:
	ll theCount(vector<int> a) {
		int b[44] = {};
		each(i,a) b[i]++;
		rep(i,41) if (2<b[i] || b[i]<b[i+1]) return 0;
		return 1ll<<(count(b,b+44,2) + (1<=count(b,b+44,1)));
	}
};