AGC_016B: Colorful Hats

http://agc016.contest.atcoder.jp/tasks/agc016_b
最初1CaseだけWAだったからこれはいけると思ったけどそうでもなかった。

A[i]の最大値と最小値(それぞれrv,lvとする)の差が1か0で場合分けする
1.　0のとき
rv = N - 1なら全色違うものを置けばOK
rv * 2 <= Nなら同じ色のペアを作っていって、N - rv * 2個分は使った色を適当にアサインすればよい。

2. 1のとき
lvの個数をcmin,rvの個数をcmaxと置く。
観察するとA[i] = lv, A[j] = lv, i != jを満たす任意のi、jについて違う色をアサインしなくてはならなくて、
A[i] = rvを満たす任意のiに関してはA[j] = rv, i != jを満たすjが存在する必要がある。
cmin >= rvだと、A[i] = lvを満たすiの集合にrv以上種類の色をアサインしてしまう。よって不可。
また2 * (rv - cnt) > cmaxだと、対応するjが存在しないiが現れてしまう。よって不可。
なのでcmin + 1 <= rv && 2 * (rv - cnt) <= cmaxが必要条件。十分性は証明簡単。

int N;
int A[MAX_N];

void solve() {
	cin >> N;
	int lv = inf, rv = -1;
	rep(i, 0, N) {
		cin >> A[i];
		MIN(lv, A[i]);
		MAX(rv, A[i]);
	}
	if(rv - lv > 1) {
		cout << "No\n";
	}
	else {
		if(rv - lv == 0) {
			if(rv == N - 1) cout << "Yes\n";
			else if(rv * 2 <= N) cout << "Yes\n";
			else cout << "No\n";
		}
		else {
			int cnt = 0;
			rep(i, 0, N) {
				if(A[i] == lv) cnt++;
			}
			if(cnt + 1 <= rv && 2 * (rv - cnt) <= N - cnt) cout << "Yes\n";
			else cout << "No\n";
		}
	}
}

2の場合分けをミスった。