Problem:


Score : 700 points

Problem Statement

There are N cats.
We number them from 1 through N.

Each of the cats wears a hat.
Cat i says: "there are exactly a_i different colors among the N - 1 hats worn by the cats except me."

Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.

Constraints

2 ≤ N ≤ 10^5

1 ≤ a_i ≤ N-1

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.

Sample Input 1

3
1 2 2

Sample Output 1

Yes

For example, if cat 1, 2 and 3 wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.

Sample Input 2

3
1 1 2

Sample Output 2

No

From the remark of cat 1, we can see that cat 2 and 3 wear hats of the same color.
Also, from the remark of cat 2, we can see that cat 1 and 3 wear hats of the same color.
Therefore, cat 1 and 2 wear hats of the same color, which contradicts the remark of cat 3.

Sample Input 3

5
4 3 4 3 4

Sample Output 3

No

Sample Input 4

3
2 2 2

Sample Output 4

Yes

Sample Input 5

4
2 2 2 2

Sample Output 5

Yes

Sample Input 6

5
3 3 3 3 3

Sample Output 6

No



Sample input:
3
1 2 2


Sample output:
Yes

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

a = max(A)
b = min(A)

# import sys
# if a - b > 1:
#     print("No")
#     sys.exit()

ok = 0

if a - b == 1:
    C = [0, 0]
    for i in range(n):
        C[A[i] - b] += 1
    if a - C[0] > 0 and C[1] // 2 >= a - C[0]:
        ok = 1
elif a == b:
    if n == a + 1:
        ok = 1   
    if n // 2 >= a:
        ok = 1

if ok == 1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

li = [{1: N}]
for i in range(1, N-1):
    li.append({i: i, i+1: min(N-i+max(N-i-2, 0), N)})
li.append({N-1: N})

C = Counter(A)
for d in li:
    cnt = 0
    for k, v in d.items():
        if C[k] <= v:
            cnt += C[k]
        else:
            break
    else:
        if cnt == N:
            Yes()
            exit()
No()

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

def solve():
    A.sort()

    if A[-1] - A[0] >= 2:
        return False

    if A[-1] - A[0] == 0:
        return (A[0] == N - 1) or (2 * A[-1] <= N)

    M = A.count(A[0])
    return (M < A[-1]) and (2 * (A[-1] - M) <= N - M)

if solve():
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))

ma = max(a)
mi = min(a)
if ma-mi >= 2:
    print('No')
elif ma == mi:
    if a[0] <= N//2 or a[0] == N-1:
        print('Yes')
    else:
        print('No')
else:
    maxnum = a.count(ma)
    minnum = a.count(mi)
    #if max(a) == minnum:
    #    print('No')
    if minnum + 1 <= ma <= minnum + maxnum//2:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = list(Counter(a).items())
c.sort()
if len(c) > 2:
    print("No")
    exit()
if len(c) == 1:
    if c[0][0] <= n//2 or c[0][0] == n-1:
        print("Yes")
    else:
        print("No")
    exit()
if c[1][0]-c[0][0] != 1:
    print("No")
    exit()
if c[0][1] > c[0][0] or (c[1][0]-c[0][1])*2>c[1][1]:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
a.sort()
k = a.count(a[0])
if a[-1] - a[0] > 1:
    print('No')
elif a[-1] == a[0]:
    if N == a[0] + 1:
        print('Yes')
    elif N//2 >= a[0]:
        print('Yes')
    else:
        print('No')
elif a[-1] < k + 1:
    print('No')
elif a[-1] > (N-k)//2 + k:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
min_a = min(a)
if min_a == max_a:
  if min_a == n-1 or min_a <= n // 2:
    print("Yes")
  else:
    print("No")
elif min_a + 1 == max_a:
  x = a.count(min_a)
  y = a.count(max_a)
  if x < max_a and (max_a - x) * 2 <= y:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    M,m = max(a),min(a)
    if M-m > 1:
        print("No")
        return
    if M == m:
        if m == n-1:
            print("Yes")
        elif 2*m <= n:
            print("Yes")
        else:
            print("No")
        return
    b = a.count(m)
    a = a.count(M)
    k = M-b
    if b+1 <= M and 2*k <= a:
        print("Yes")
    else:
        print("No")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def examA():
    Alpha = [chr(i) for i in range(97, 97+26)]
    S = SI(); N = len(S)
    ans = -1
    for i in range(N):
        for s in Alpha:
            cur = [s for s in S]
            for l in range(i):
                for k in range(N-1):
                    if cur[k+1]==s:
                        cur[k]=s
 #           print(cur)
            if len(Counter(cur[:N-i]))==1:
                ans = i
                break
        if ans>=0:
            break
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] +=1
    l = min(d); r = max(d)
    ans = "Yes"
    if l>=N:
        ans = "No"
    if r-l>1:
        ans = "No"
    if d[l]>l:
        ans = "No"
    if (r-d[l])*2+d[l]>N:
        ans = "No"
    if r==l and (N-l==1 or N//2>=l):
        ans = "Yes"
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Accepted

Solution code:
N = int(input())
hat = list(map(int, input().split()))
hat.sort()
min, max = hat[0], hat[N - 1]
count_min = 0
count_max = N
if max - min > 1:
    print("No")
elif max == min:
    if max <= N // 2 or max == N-1:
        print("Yes")
    else:
        print("No")
else:
    for i in range(N):
        if hat[i] < max:
            count_min += 1
            count_max -= 1
        else:
            break
    # 種類はcount_min+1 <= max <= count_min + count_max // 2
    if count_min < max <= count_min + count_max // 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

# それぞれの猫の発言からありえる色の種類を計算
b = [0 for i in range(n+1)]
for i in range(n):
    b[a[i]]+=1
    b[a[i]+1]+=1

for i in range(1,n+1):
    # n匹の猫がありえると言った、b[i]==nとなるi色だけ可能性がある
    if b[i]==n:
        # a[j]==i-1であれば、自分は固有の色
        unique = 0
        for j in range(n):
            if a[j]==i-1:
                unique+=1
        # 固有じゃない猫の数
        common = n-unique
        # 固有じゃないのが1匹はありえない
        if common==1:
            break
        # 全部固有の時
        elif common==0:
            if unique==i:
                print('Yes')
                exit()
        # 固有じゃないのが2匹以上いる時
        elif unique+1<=i<=common//2+unique:
            print('Yes')
            exit()
print('No')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
K, L = min(a), max(a)
s = a.count(K)

if L-K>1:
    print("No")
    quit()
if L==K:
    print("Yes" if K==n-1 or K<=n//2 else "No")
else:
    t = n-s
    print("Yes" if L-s>0 and L-s<=t//2 else "No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    m=min(A); M=max(A)

    # 種類数が x だとして
    # 自分の色が他にいない -> x-1
    # 自分の色が他にいる -> x
    # よって M-m は1以下
    if(M-m>1):
        print("No")
        return

    # もし全員が同じ数字を言っている場合
    if(m==M):
        if(m==n-1): # 全てが1色ずつならOK
            print("Yes")
            return
        elif(m<=n//2): # 全てが2色以上ずつ用意できるならOK
            print("Yes")
            return
        else:
            print("No")
            return

    # もしズレがある場合
    s=A.count(m) # 自分だけの色を持つ数
    t=A.count(M) # 複数で色を共有する数
    # 色の種類は最小でs+1、最大でs+t//2
    if(s+1<=M<=s+t//2):
        print("Yes")
    else:
        print("No")

resolve()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
a = [int(i) for i in input().split()]

def solve() :
    c = Counter(a)
    if len(c.keys()) > 2 :
        return 'No'
    
    if len(c.keys()) == 2 :
        if max(c.keys()) - min(c.keys()) != 1 :
            return 'No'
            
        mk, Mk = min(c.keys()), max(c.keys())
        mv, Mv = c[mk], c[Mk]
        n = N - mv
        m = Mk - mv
        if 0 < m * 2 <= n :
            return 'Yes'
        else :
            return 'No'
    else :
        n = N
        m = list(c.keys())[0]
        if m * 2 <= n or m == n - 1 :
            return 'Yes'
        else :
            return 'No' 

print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
mx = max(a)
mn = min(a)
c = mx + 0
b = 0
s = 0
if mx == mn and (mx != N - 1):
  mn -= 1
if mx >= N:
  print("No")
  exit(0)
for i in range(N):
  if abs(a[i] - mx) > 1:
    print("No")
    exit(0)
  if a[i] == mn:
    c = a[i] + 1
    s += 1
  else:
    b += 1
if s >= c and (b != 0 and s != 0):
  print("No")
  exit(0)
elif s > c:
  print("No")
  exit(0)
if b == 1:
  print("No")
  exit(0)
if b // 2 < c - s:
  print("No")
else: print("Yes")

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
M = max(a)
mcnt = a.count(M - 1)
Mcnt = a.count(M)
if Mcnt + mcnt == n:
	if mcnt == 0:
		if 2 * M <= n or M == n - 1:
			print("Yes")
			exit()
	else:
		if 0 < 2 * (M - mcnt) <= n - mcnt:
			print("Yes")
			exit()
print("No")

Submission status: Accepted

Solution code:
# 解説
def solve():
    n = int(input())
    a = tuple(map(int, input().split()))

    # n匹全体でA色とする
    # aloneな猫: a_i = A-1
    # 同色がいる猫: a_i = A

    M = max(a)
    m = min(a)

    delta = M - m
    # 最大値と最小値の差

    if delta > 1:
        return False
        # 各猫視点の色数の差は2以上にはならない
    elif delta == 1:
        # alone,同色ありが混在
        # aloneな猫: a_i = A-1
        # 同色がいる猫: a_i = A

        x = a.count(m)
        # alone猫数,この猫だけでx色ある

        y = n - x
        # 同色いる猫数
        # 最低1色、最大でy//2色（2匹ずつに分けて、端数はどこかのグループに入れる）

        if x >= M:
            return False
            # x + y//2 = A
            # x = A - y//2 < A

        if (y - (M - x) * 2) not in {0, 1}:
            return False
            # x + y//2 = A
            # y//2 = A - x
            # y = (A - x) * 2 or (A - x) * 2 + 1

        return True

    else:
        # if delta == 0
        if all(a_ == n - 1 for a_ in a):
            return True
            # 全員alone=A-1=n-1

        if all(a_ * 2 <= n for a_ in a):
            return True
            # 全員同色がいる=A
            # ooxxzz -> A=3: 色の総数は各グループが2匹以上なので、A*2<=n
            # oooxxx -> A=2

        return False

    return True


print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n=int(input())
    a=ct(list(map(int,input().split())))
    if len(a.keys()) not in [1,2]:
        print("No")
        return 0
    if len(a.keys())==1:
        a=list(a.items())
        if a==[(n-1,n)]:
            print("Yes")
            return 0
        if 2*a[0][0]<=a[0][1]:
            print("Yes")
        else:
            print("No")
        return 0
    i=min(a.keys())
    iv=a[i]
    j=max(a.keys())
    jv=a[j]
    if j-i!=1:
        print("No")
        return 0
    if iv>i:
        print("No")
        return 0
    k=2*(i-iv+1)
    if jv>=k:
        print("Yes")
    else:
        print("No")
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    A.sort()
    d = A[-1] - A[0]
    if d >= 2:
        return 'No'
    elif d == 0:
        if A[0]*2 <= N or A[0] == N-1:
            return 'Yes'
        else:
            return 'No'
    else:
        K = max(A)
        C = Counter(A)
        y = C[K]
        x = C[K-1]
        if x < K and 2*(K-x) <= y:
            return 'Yes'
        else:
            return 'No'

def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n=inp()
    a=inpl()
    a.sort()
    if a[n-1]-a[0]>1 or a[n-1]>=n or a[0]<1:
        print("No")
        return
    cnt=1
    for i in range(n-1):
        if a[i+1]==a[i]:
            cnt+=1
        else:
            break
    if cnt==n:
        if a[0]==n-1 or n//a[n-1]>=2:
            print("Yes")
            return
        else:
            print("No")
            return
    if cnt>a[0]:
        print("No")
        return
    if (a[n-1]-(n%a[n-1]))>cnt:        
        print("No")
        return
    print("Yes")    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	D = defaultdict(int)
	a = getlist()
	for i in a:
		D[i] += 1
	if len(D) >= 3:
		print("No")
	elif len(D) == 1:
		if a[i] * 2 <= N:
			print("Yes")
		elif a[i] + 1 == N:
			print("Yes")
		else:
			print("No")
	else:
		L = []
		for i in D:
			L.append([i, D[i]])
		L = sorted(L)
		if L[0][0] + 1 != L[1][0]:
			print("No")
		else:
			x = L[0][1]
			y = L[1][1]
			A = L[0][0]
			if y < (A - x + 1) * 2 or A - x + 1 <= 0:
				print("No")
			else:
				print("Yes")


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
a.sort()
if a[0] == a[-1]:
    if a[0] == N-1 or a[0] <= N//2:
        print("Yes")
    else:
        print("No")
    exit()

if a[0] < a[-1]-1:
    print("No")
    exit()

o = 0
t = 0
for i in range(N):
    if a[i] != a[0]:
        o = i
        t = N-i
        break

if t//2 + o >= a[-1] > o:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.buffer.readline

N = int(input())
a = list(map(int, input().split()))

c = Counter(a)
if len(c.most_common()) > 2:
    print('No')
elif len(c.most_common()) == 1:
    if c.most_common()[0][0] == N-1:
        print('Yes')
    else:
        if c.most_common()[0][0] * 2 <= N:
            print('Yes')
        else:
            print('No')
else:
    x, nx = c.most_common()[0]
    y, ny = c.most_common()[1]
    if x > y:
        x, y = y, x
        nx, ny = ny, nx
    if y - x != 1:
        print('No')
    else:
        if 1 <= y - nx <= ny//2:
            print('Yes')
        else:
            print('No')

Submission status: Accepted

Solution code:
n = int(input())
xs = [int(x) for x in input().split()]

def solve(n, xs):
    x_min = min(xs)
    x_max = max(xs)

    if x_max - x_min > 1:
        return "No"

    if x_max == x_min:
        if n == x_max+1:
            return "Yes"
        elif x_max*2 <= n:
            return "Yes"
        else:
            return "No"

    solo_num = sum(1 for x in xs if x==x_min)

    if solo_num >= x_max:
        return "No"

    dup_color = x_max - solo_num
    dup_cat = sum(1 for x in xs if x==x_max)

    if dup_cat < dup_color*2:
        return "No"

    return "Yes"

print(solve(n, xs))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mi = min(a)
ma = max(a)
if ma - mi >= 2:
  print('No')
elif ma - mi == 1:
  alone = a.count(mi)
  if alone < ma and (ma - alone) * 2 <= n - alone:
    print('Yes')
  else:
    print('No')
else:
  if mi * 2 <= n or mi == n-1:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:

N = int(input())

a = list(map(int,input().split()))


dic = {}

for i in a:

    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

if len(dic) > 2:
    print ("No")

else:
    mi = float("inf")
    ma = -1

    for i in dic:
        mi = min(mi,i)
        ma = max(ma,i)

    if ma - mi > 1:
        print ("No")

    elif ma - mi == 1:
        

        if dic[mi] + dic[ma] // 2 == ma and dic[ma] > 1:
            print ("Yes")
        else:
            print ("No")

    else:

        if ma == N-1 or N // 2 >= ma:
            print ("Yes")
        else:
            print ("No")

Submission status: Accepted

Solution code:
n,*a=list(map(int,open(0).read().split()))
b,c=max(a),min(a)
if b-c==1:
    d,e=a.count(b),a.count(c)
    if e<b and 2*(b-e)<=d:print("Yes")
    else:print("No")
elif b-c==0:
    if a[0]==n-1 or a[0]*2<=n:print("Yes")
    else:print("No")
else:print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

max_a = max(a)
min_a = min(a)
if max_a - min_a >= 2:
    print("No")
    exit()

if max_a == min_a:
    if max_a == n - 1:
        print("Yes")
    elif max_a <= n // 2:
        print("Yes")
    else:
        print("No")
    exit()

nokori = min_a + 1 - a.count(min_a)
if nokori <= 0:
    print("No")
elif a.count(max_a) // nokori <= 1:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
maxa = max(a)
mina = min(a)
if maxa - mina == 0:
    if maxa <= n // 2 or maxa == n - 1:
        print("Yes")
    else:
        print("No")
elif maxa - mina == 1:
    loneCatNum = len([x for x in a if x == mina])
    if loneCatNum + 1 <= maxa and maxa <= (n + loneCatNum) / 2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
c=0
if(b[n-1]-b[0]>1):
    print('No')
elif(b[n-1]-b[0]==0):
    if(1<=b[0]<=n//2 or b[0]==n-1):
        print('Yes')
    else:
        print('No')
else:
    for i in range(n-1):
        if(b[i]<b[i+1]):
            c=i
            break
    if(c==n-2):
        print('No')
    elif(c+1<=b[0]<=c+(n-c-1)//2):
        print('Yes')        
    else:
        print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
L = list(map(int, input().split()))
ans = "Yes"

L_max = max(L)
L_min = min(L)

if L_max - L_min >= 2:
    ans = "No"
elif L_max == L_min:
    if not(N >= L[0]*2 or L[0] == N-1):
        ans = "No"
else:
    num_alone = L.count(L_min)
    not_alone_L = [v-num_alone for v in L if v == L_max]
    if not_alone_L[0] <= 0 or len(not_alone_L) < not_alone_L[0]*2:
        ans = "No"
print(ans)

Submission status: Accepted

Solution code:
n,a=open(0)
n=int(n)
a=sorted(map(int,a.split()))
if a[0]==a[-1]:
  if n-1==a[0]or n//a[0]>=2:
    print('Yes')
  else:
    print('No')
elif a[-1]-1==a[0]:
  x=a.count(a[0])
  if x<a[-1]and(n-x)//(a[-1]-x)>=2:
    print('Yes')
  else:
    print('No')
else:
  print('No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter

N = int(input())
A = list(map(int, input().split()))

C = Counter(A)
if len(C) == 1:
    X = A[0]
    if N >= 2*X or N == X + 1:
        ans = "Yes"
    else:
        ans = "No"
elif len(C) == 2:
    Xs = sorted(C.keys())
    if Xs[0] + 1 != Xs[1]:
        ans = "No"
    else:
        X = Xs[0]
        if C[X] <= X and C[X+1] >= 2*(X-C[X]+1):
            ans = "Yes"
        else:
            ans = "No"
else:
    ans = "No"

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
M=max(a)
m=min(a)

if M-m>=2:
    print("No")

elif M-m==0:
    count=0
    for i in range(N):
        if a[i]==N-1 or a[i]<=N//2:
            count+=1
    if count==N:
        print("Yes")
    else:
        print("No")
else:
    q=0
    p=0
    for i in range(N):
        if a[i]==M:
            q+=1
        elif a[i]==m:
            p+=1
    if p+q//2 >= max(a) and max(a)>=p+1:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]
c = collections.Counter(A)
l = min(c)
r = max(c)
if r != l + 1:
    print('Yes' if r == l == N - 1 or r == l <= N // 2 else 'No')
    exit()
cl = c[l]
cr = c[r]
print('Yes' if cl + 1 <= r <= cl + cr // 2 else 'No')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(a)
b.sort()
if b[n-1]-b[0] >=2:
    print("No")
else:
    b = sum(a)%n
    c = int((sum(a)-b)/n)
    if b == 0:
        if 2*c > n and n != c+1:
            print("No")
        else:
            print("Yes")
    else:
        if b == 1:
            print("No")
        else:
            if n - b/2 >= c+1 and n <= c+b:
                print("Yes")
            else:
                print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
L = LI()
A = sorted(list(set(L)))
if len(A) == 1:
    if 1 <= A[0] <= n // 2 or A[0] == n - 1:
        print('Yes')
    else:
        print('No')
elif len(A) == 2 and A[0] + 1 == A[1]:
    cnt = Counter(L)
    min_type_num = cnt[min(L)]  + 1
    max_type_num = cnt[min(L)] + cnt[max(L)] // 2
    if min_type_num <= max(L) <= max_type_num:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
c=sorted(Counter(A).most_common(),reverse=True)
r=0
if len(c)==2 and c[0][0]==c[1][0]+1 and 0<c[0][0]-c[1][1]<=c[0][1]//2:
    r=1
elif len(c)==1 and (c[0][0]==c[0][1]-1 or c[0][0]<=c[0][1]//2):
    r=1
print(['No','Yes'][r])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

def solve():
    if max(a)-min(a) > 1:
        return False
    if all(i==a[0] for i in a):
        if a[0] == n-1 or a[0] <= n//2:
            return True
        else:
            return False
    color = [0]*n
    unique = min(a)
    for i, ai in enumerate(a):
        if ai == unique:
            color[i] = 1
    s = sum(color)
    can = (n-s)//2

    for i, ai in enumerate(a):
        if ai == unique:
            if not (s <= ai <= s-1+can):
                return False
        else:
            if not (s+1 <= ai <= s+can):
                return False
    return True

if solve():
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n=input()
m=map(int,input().split())
a=[int(i) for i in m]
d=max(a)-min(a)
if d>1:
    ans=False
elif d==0:
    if (max(a)==len(a)-1 or max(a)*2<=len(a)):
        ans=True
    else:
        ans=False
else:
    max_num=a.count(max(a))
    min_num=a.count(min(a))
    dif=max(a)-min_num
    if (min_num<max(a) and dif*2<=max_num):
            ans=True
    else:
        ans=False
        
if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
import collections
l1 = collections.Counter(a).most_common()
l1.sort()
if len(l1) > 2:
    print("No")
elif len(l1) == 1:#発言が１種類の場合
    if l1[0][0] * 2 <= n or l1[0][0] == n - 1:
        print("Yes")
    else:
        print("No")
else:
    if l1[1][0] - l1[0][0] > 1:
        print("No")
    elif l1[1][1] >= (l1[1][0] - l1[0][1]) * 2 and l1[1][0] > l1[0][1]:
        print("Yes")#多い発言の人数が残りの色数かけ２より多い、全体色数が少ない発言の人数より多い
    else:
        print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
L = len(set(a))
if L ==1:
  if a[0] < n//2+1 or a[0]==n-1:
    print('Yes')
  else:
    print('No')
elif L == 2:
  M,m =max(a),min(a)
  m_c =a.count(m)
  if M == m+1 and m_c <= m and n-m_c >= 2*(M-m_c):
    print('Yes')
  else:
    print('No')
else:
  print('No')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
min_A = min(A)
if max_A - min_A >= 2:
    print("No")
elif max_A - min_A == 1:  # 他の猫とと色がかぶらない猫と、色が被る猫の両方が存在する
    M = A.count(max_A)
    print("Yes") if N - M + 1 <= max_A <= (N - M) + M // 2 else print("No")
else:  # 他の猫とと色がかぶらない猫が存在しない or 皆違う色
    print("Yes") if max_A <= N // 2 or max_A == N - 1 else print("No")

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split())))
flag = False
if A[-1] - A[0] == 0:
    a = A[0]
    if N == a + 1 or N >= 2 * a:
        flag = True
elif A[-1] - A[0] == 1:
    c = bisect_left(A, A[-1])
    if A[-1] > c and 2 * A[-1] - c <= N:
        flag = True
print("Yes" if flag else "No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
M = max(a)
m = min(a)
if M-m >= 2:
  print("No")
elif M == m:
  if a[0] == n-1 or a[0]*2 <= n:
    print("Yes")
  else:
    print("No")
else:
  alone = a.count(m)
  left = n - alone
  if alone >= M:
    print("No")
  elif (M - alone)*2 <= left:
    print("Yes")
  else:
    print("No")

Submission status: Accepted

Solution code:
import sys
def printans(t):
    print(t)
    sys.exit()

N=int(input())
A=[int(i) for i in input().split()]

if all([a==A[0] for a in A]):#全部同じ
    shurui=A[0]
    if shurui==N-1 or shurui*2<=N:
        printans("Yes")
    else:printans("No")
else:#少ないやつは自分だけの色、そいつら以外で上と同じ処理
    maxshurui = max(A)
    if all([a in (maxshurui,maxshurui-1) for a in A]):
        unique = A.count(maxshurui-1)
        shurui = maxshurui-unique
        if shurui<=0:
            printans("No")
        if shurui*2<=N-unique:
            printans("Yes")
        else:printans("No")
    else:printans("No")

Submission status: Accepted

Solution code:
import sys

n = int(input())
a = list(map(int,input().split()))
mi,ma = 10 ** 6,0
cnt = [0] * n
for v in a:
    cnt[v] += 1
    mi = min(mi,v)
    ma = max(ma,v)
if ma - mi >= 2:
    print("No")
    sys.exit()
if mi != ma:
    if cnt[mi] == ma or (n - cnt[mi]) // (ma - cnt[mi]) < 2:
        print("No")
    else:
        print("Yes")
else:
    if mi == n - 1 or mi * 2 <= n:
        print("Yes")
    else:
        print("No")