AGC 016 B - Colorful Hats (700)

• 問題

問題概要

N匹の猫がいて,それぞれが色のついた帽子をかぶっている.
N匹の猫に,自分以外の猫の帽子の色は何種類あるかという質問をした時の答えa[i] (1<=i<=N) が与えられる.
条件を満たすような帽子のかぶり方は存在するか.
1 <= a[i] <= N-1, 1 <= N <= 10⁵

解法

全ての猫がA種類の帽子をかぶっているとする.
自分以外で自分と同じ色の帽子をかぶっている猫がいるとき,その猫をaloneであるとする.
猫iがaloneである時, a[i] = A-1
猫iがaloneでない時, a[i] = A　となる.

よってmin = min(a[i]) , max = max(a[i])とすると, max - min >= 2ならば満たすかぶり方は存在しない.
(1) min = max
(2) max = min+1 = A
それぞれの場合について考える.

(1) 全ての猫がalone, または全ての猫がnot aloneである.
前者の時は, A = a[i]+1 = N でなければならない.
後者の時の, Aの範囲について考える.
最小は全て同じ色にすれば良いから,1色である.
最大は,猫は少なくとも2匹で組を作らなければならない(同じ色の猫がいなければならない)と考えると,
floor(N/2)となる.
よって後者の時は A <= floor(N/2) を満たしていれば良い.

(2) min = A-1, max = Aと考えて良い.
ということはminを答えた猫はaloneであり, maxと答えた猫はnot aloneである.
minと答えた猫の数をx, maxと答えた猫の数をyとすると,
aloneである猫の色の数はx.
not aloneな猫の色の数は,(1)と同様に考察すると1〜floor(y/2)のいずれかである.
よって, x+1 <= A <= x+floor(y/2) を満たしていれば良い.

メモ

超考察ゲーだった.
こういう種類の問題は数をこなすしかないのか...

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;
int a[MAX_N];

int main(){
  int N; cin >> N;
  int _max = -INF, _min = INF;
  rep(i,N){
    scanf("%d",a+i);
    _max = max(_max,a[i]);
    _min = min(_min,a[i]);
  }
  bool ans = false;
  if(_min==_max){
    if(_min==N-1 || _min<=N/2) ans = true;
  }else if(_max==_min+1){
    int cnt_min = 0;
    rep(i,N) if(a[i]==_min) cnt_min++;
    if(_max >= cnt_min+1 && _max <=(cnt_min)+(N-cnt_min)/2) ans = true;
  }
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}