B - Colorful Hats AtCoder Grand Contest 016

B - Colorful Hats

問題文

$N$ 匹の猫がいます。 猫には $1$ から $N$ まで番号が振られています。

各猫はある色の帽子を被っています。 猫 $i$ は「自分を除く $N-1$ 匹の猫が被っている帽子の色の種類数はちょうど $a_i$ である」と言っています。

すべての猫の発言と矛盾しないような帽子の色の組合せが存在するか判定してください。

制約

• $2\le N\le {10}^5$
• $1\le a_i\le N-1$

解法

全体でA種類の帽子がある場合、一つだけの帽子をかぶっている猫をaloneその他をanyとすると、aloneはA-1,anyはAになる。

よってそれを満たさない場合No

全ての数字が同じ場合、全てがaloneか全てがanyである。

aloneの場合は全員N-1になればよい。

anyの場合、グループには最小で二人必要のためA * 2 がN以下ならok

2種類の数字がある場合、少ない方はalone,その他はanyとなる。

大きい数からaloneの人数を引くとanyのグループの数がわかる。

*2して制限を超えないならよし。

また、anyのグループ数が0以下になったらだめ。

public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        A = sc.nextIntArray(N);
        int max = max(A);
        int min = min(A);
        int comi = 0;
        int coma = 0;
        //佐賀1
        if (max - min > 1)
        {
            System.out.println("No");
            return;
        }
        //全員同じ N-1
        if (max == min && max == N - 1)
        {
            System.out.println("Yes");
            return;
        }
        if (max == min)
        {
            if (max * 2 <= N)
            {
                System.out.println("Yes");
                return;
            }
            else
            {
                System.out.println("No");
                return;
            }
        }
        //2種類
        for (int i = 0; i < N; i++)
        {
            if (A[i] != max && A[i] != min)
            {
                System.out.println("No");
                return;
            }
            if (A[i] == min) comi++;
        }
        coma = N - comi;

        if (coma == 1)
        {

            System.out.println("No");
            return;
        }
        int lcou = max - comi;
        if (comi < max && lcou * 2 <= coma)
        {
            System.out.println("Yes");
            return;
        }
        System.out.println("No");

    }