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: Wrong Answer

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

result = True

if len(set(a)) > 1:
    set_min = list(set(a))[0]
    set_max = list(set(a))[1]

    if len(set(a)) > 2:
        result = False
    elif (set_max - set_min) != 1:
        result = False
    else:
        if set_max == N-1:
            result = (a.count(set_min) == N-2)
        else:
            result = (a.count(set_min) < set_max)
else:
    result = (list(set(a))[0] <= N/2 or list(set(a))[0] == N-1)



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

Submission status: Wrong Answer

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

result = True

if len(set(a)) > 1:
    set_min = list(set(a))[0]
    set_max = list(set(a))[1]

    if len(set(a)) > 2:
        result = False
    elif (set_max - set_min) != 1:
        result = False
    else:
        if set_max == N-1:
            result = (a.count(set_min) == N-2)
else:
    result = (list(set(a))[0] <= N/2 or list(set(a))[0] == N-1)



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

Submission status: Wrong Answer

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

result = False

if len(set(a)) > 1:
    set_min = list(set(a))[0]
    set_max = list(set(a))[1]

    if len(set(a)) > 2:
        result = False
    elif (set_max - set_min) != 1:
        result = False
    else:
        if set_max == N-1:
            result = (a.count(set_min) == N-2)
        else:
            result = True
else:
    result = (list(set(a))[0] <= N/2 or list(set(a))[0] == N-1)



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

Submission status: Wrong Answer

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

result = False

if len(set(a)) > 1:
    set_min = list(set(a))[0]
    set_max = list(set(a))[1]

    if len(set(a)) > 2:
        result = False
    elif (set_max - set_min) != 1:
        result = False
    else:
        if set_max == N-1:
            result = (a.count(set_min) == N-2)
        pass
else:
    result = (list(set(a))[0] <= N/2 or list(set(a))[0] == N-1)



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

Submission status: Wrong Answer

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

result = False

if len(set(a)) > 1:
    set_min = list(set(a))[0]
    set_max = list(set(a))[1]

    if len(set(a)) > 2:
        result = False
    elif (set_max - set_min) != 1:
        result = False
    else:
        pass
else:
    result = (list(set(a))[0] <= N/2 or list(set(a))[0] == N-1)



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

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
if a[N-1]==1:
  print("Yes")
  sys.exit()
if a[0]==a[N-1]:
  if 2*a[0]<=N:
    print("Yes")
  else:
    print("No")
  sys.exit()

count=a.index(a[N-1])
if count+1<=a[N-1] and a[N-1]<=count+int((N-a[count])/2):
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())

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


#1匹からでは不可能なので
if a[-1]-a[0]>1:
	print("No")
else:
	#全部が同じではない場合
	for i in range(1,N):
		#a[i]の要素が1個増えたタイミング
		if a[i]!=a[0]:
			if 1<=a[-1]-i<=int((N-i)/2):
				print("Yes")
			else:
				print("No")
			break
	else:
		#全部同じ場合
		if 1<=a[0]<=int(N/2):
			print("No")
		else:
			print("Yes")

Submission status: Wrong Answer

Solution code:
N=int(input())

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


#1匹からでは不可能なので
if a[-1]-a[0]>1:
	print("No")
else:
	#全部が同じではない場合
	for i in range(1,N):
		#a[i]の要素が1個増えたタイミング
		if a[i]!=a[0]:
			if 1<=a[-1]-i<=int((N-i)/2):
				print("Yes")
			else:
				print("No")
			break
	else:
		#全部同じ場合
		if 1<=a[0]<=int(N/2):
			print("Yes")
		else:
			print("No")

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
if a[N-1]==1:
  print("Yes")
  sys.exit()
if a[0]==a[N-1]:
  if 2*a[0]<=N:
    print("Yes")
  else:
    print("No")
  sys.exit()

count=a.index(a[N-1])
if a[N-1]==count+1:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
if a[N-1]==1:
  print("Yes")
  sys.exit()
if a[0]==a[N-1]:
  if 2*a[0]<=N:
    print("Yes")
  else:
    print("No")
  sys.exit()

count=a.index(a[N-1])
if a[0]<=count:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

cnt = 0
for i in range(n):
    if a[i] == a[0]:
        cnt = i+1
    else:
        break

if a[-1] - a[0] > 1:
    print('No')
    exit()
elif a[-1] - a[0] == 1:
    actual = a[-1]
    if actual >= n:
        print('No')
    elif cnt <= actual - 1 and actual <= cnt + 1:
        print('Yes')
    else:
        print('No')
    exit()
elif a[-1] - a[0] == 0:
    solve = False
    actual = a[0]
    if n >= actual * 2 or n-1 == actual:
        solve = True
    if solve:
        print('Yes')
    else:
        print('No')
    exit()
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N=int(input())

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


#1匹からでは不可能なので
if a[-1]-a[0]>1:
	print("No")
else:
	#全部が同じではない場合
	for i in range(1,N):
		#a[i]の要素が1個増えたタイミング
		if a[i]!=a[0]:
			if 1<=a[-1]-i<=int((N-i)/2):
				print("Yes")
			else:
				print("No")
			break
	else:
		#全部同じ場合
		if a[0]*2<=N or N==2:
			print("Yes")
		else:
			print("No")

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
if max(a)-min(a)>=2:
    print "No"
    exit()
if max(a)==min(a):
    if max(a)==n-1:
        print "Yes"
    elif max(a)*2>n:
        print "No"
    else:
        print "Yes"
    exit()
cntmx=a.count(max(a))
cntmn=a.count(min(a))
if cntmn==1 and cntmx==n-1:
    print "Yes"
else:
    print "No"

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[-1] - a[0] > 1:
    print('No')
    exit()
elif a[-1] - a[0] == 1:
    actual = a[-1]
    if actual >= n:
        print('No')
    elif a[actual-1] == a[-1]:
        print('Yes')
    else:
        print('No')
    exit()
elif a[-1] - a[0] == 0:
    solve = False
    actual = a[0]
    if n >= actual * 2 or n-1 == actual:
        solve = True
    if solve:
        print('Yes')
    else:
        print('No')
    exit()
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
array = [int(x) for x in input().split(' ')]
maxa = max(array)
mina = min(array)
if maxa - mina > 1:
    print('No')
elif maxa == mina:
    if n/2 >= maxa:
        print('Yes')
    else:
        print('No')
else:
    sum = 0
    for j in array:
        if j == mina:
            sum += 1
    if sum >= maxa:
        print('No')
        exit()
    if 2*(maxa - sum) <= n - sum:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[-1] - a[0] > 1:
    print('No')
    exit()
elif a[-1] - a[0] == 1:
    actual = a[-1]
    if actual >= n:
        print('No')
    elif a[actual-1-1] == a[0] and a[actual-1] == a[-1]:
        print('Yes')
    else:
        print('No')
    exit()
elif a[-1] - a[0] == 0:
    solve = False
    actual = a[0]
    if n >= actual * 2 or n-1 == actual:
        solve = True
    if solve:
        print('Yes')
    else:
        print('No')
    exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[-1] - a[0] > 1:
    print('No')
    exit()
elif a[-1] - a[0] == 1:
    actual = a[-1]
    if a[actual-1-1] == a[0] and a[actual-1] == a[-1]:
        print('Yes')
    else:
        print('No')
    exit()
elif a[-1] - a[0] == 0:
    solve = False
    actual = a[0]
    if n >= actual * 2 or n-1 == actual:
        solve = True
    if solve:
        print('Yes')
    else:
        print('No')
    exit()

Submission status: Wrong Answer

Solution code:
import sys

N=int(raw_input())
a=map(int,raw_input().split())

T=0
for i in a:
    if i != a[0]:
        T=max(i,a[0])
        break

if T == 0:
    if a[0] <= N/2 or a[0] == N-1:
        print "Yes"
    else:
        print "No"
    sys.exit()

uni=0
nu=0
for i in a:
    if i==T:
        nu+=1
    else:
        uni+=1

if T>=uni+1 and T<=uni+nu/2:
    print "Yes"
else:
    print "No"

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
b = max(a)
c = min(a)
if b - c > 1:
    print "No"
elif b == c:
    print "Yes" if b == n - 1 or 2 * b <= n else "No"
else:
    t = sum(c == x for x in a)
    if t >= b:
        print "No"
    else:
        print "Yes" if (b - t) * 2 <= t else "No"

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())

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


X = Counter(a)
if(len(X) >2 ):
    print("No")
    exit()

min_val = min(a)
max_val = max(a)
if not min_val == max_val-1 and  not min_val==max_val:
    print("No")
    exit()

a.sort()

#only 1 color
unique_cat = X[min_val]

# 2 or more cat color  : max_val - unique_cat
last_cat =  N- unique_cat

last_colors = max_val - unique_cat
#print(last_cat,last_colors,unique_cat)
if 2*last_colors <= last_cat and not (last_cat>0 and last_colors==0)\
        and last_colors>0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

L = []

def ans(tf):
  if tf:
    print("Yes")
  else:
    print("No")

for x in a:
  for i in range(len(L)):
    if L[i][0] == x:
      L[i][1] += 1
      break
  else:
    L.append([x, 1])
    if len(L) >= 3:
      ans(False)

if len(L) == 1:
  x = L[0][0]
  if x == N - 1 or x <= N // 2:
    ans(True)
  else:
    ans(False)
else:
  x, xn = L[0]
  y, yn = L[1]
  if abs(x - y) != 1:
    ans(False)
    exit()
  if x < y:
    x, y = y, x
    xn, yn = yn, xn
  if yn >= x:
    ans(False)
    exit()
  n = x - yn
  if n <= xn // 2:
    ans(True)
  else:
    ans(False)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = []
C = []
for num in A:
    if num in B: 
        C[B.index(num)] += 1
    else:
        B.append(num)
        C.append(1)

if len(B) > 2:
    print('No')
elif len(B) == 1:
    if n == B[0] +1:
        print('Yes')
    elif n//B[0] >= 2:
        print('Yes')
    else:
        print('No')
elif B[0]  == (B[1]+1):
    k = C[1]
    m = B[1]
    if m-k+1 <= 0:
        print('No')
    elif (n-k) % (m-k+1) == 0:
        print('Yes')
    else:
        print('No')
elif B[1] == (B[0]+1):
    k = C[0]
    m = B[0]
    if m-k+1 <= 0:
        print('No')
    elif (n-k) % (m-k+1) == 0:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
print([1/id('hoge')%5%2]*2**28**id('fuga')and'Yes')

Submission status: Time Limit Exceeded

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

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

elif max(a)-min(a)==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]==max(a):
            q+=1
        elif a[i]==min(a):
            p+=1
    if p+q//2 >= max(a) and max(a)>=p+1:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
#https://img.atcoder.jp/agc016/editorial.pdf
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  ans = 'Yes'
  alone = 0
  group = 0
  if max(a) - min(a) >= 2: ans = 'No'
  
  elif max(a) - min(a) == 1:
   for i in a:
     if i == max(a)-1 : alone += 1
     else: group += 1
   if alone < max(a) and 2*(max(a)-alone)<= group: pass
   else: ans = 'No'
  
  
  elif max(a) - min(a) == 0:
    if a[0] == n-1 or 2*a[0] <= n:
      pass
    else: ans = 'No'
  return ans

if __name__ == '__main__':
  print(solve())

Submission status: Accepted

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

if len(set(As)) >= 3:
    print("No")
    exit()
elif len(set(As)) == 1:
    print("Yes" if 1 <= As[0] <= N // 2 or As[0] == N - 1 else "No")
    exit()
else:
    p, q = sorted(set(As))
    if p + 1 != q:
        print("No")
        exit()
    t = As.count(p)
    u = N - t
    if t + 1 <= q <= t + u // 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()

if max(a) - min(a) == 0 and (a[0] == N-1 or a[0] <= N//2):
	print("Yes")
elif max(a) - min(a) == 1 and a.count(min(a))+1 <= max(a) <= a.count(min(a)) + a.count(max(a))//2:
	print("Yes")
else:
	print("No")

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
a = LIST()


if len(set(a)) == 1:
	if a[0] == N-1 or a[0] <= N//2:
		print("Yes")
	else:
		print("No")

elif len(set(a)) == 2:
	p, q = sorted(list(set(a)))
	p_cnt = a.count(p)
	q_cnt = a.count(q)
	if q == p+1 and  p_cnt + 1 <= q <= p_cnt + q_cnt//2:
		print("Yes")
	else:
		print("No")

else:
	print("No")

Submission status: Accepted

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

L = []

def ans(tf):
  if tf:
    print("Yes")
  else:
    print("No")
  exit()

for x in a:
  for i in range(len(L)):
    if L[i][0] == x:
      L[i][1] += 1
      break
  else:
    L.append([x, 1])
    if len(L) >= 3:
      ans(False)

if len(L) == 1:
  x = L[0][0]
  if x == N - 1 or x <= N // 2:
    ans(True)
  else:
    ans(False)
else:
  x, xn = L[0]
  y, yn = L[1]
  if abs(x - y) != 1:
    ans(False)
    exit()
  if x < y:
    x, y = y, x
    xn, yn = yn, xn
  if yn >= x:
    ans(False)
    exit()
  n = x - yn
  if n <= xn // 2:
    ans(True)
  else:
    ans(False)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = [[a[0], 0]]
for i in a:
    if cnt[0][0] == i:
        cnt[0][1] += 1
    else:
        if len(cnt) == 1:
            cnt.append([i, 1])
            if not abs(cnt[0][0] - cnt[1][0]) == 1:
                print("No")
                exit()
        else:
            if cnt[1][0] == i:
                cnt[1][1] += 1
            else:
                print("No")
                exit()
cnt.sort()
if len(cnt) == 1:
    print("Yes" if cnt[0][0] <= cnt[0][1] // 2 or cnt[0][0] + 1 == n else "No")
else:
    print("Yes" if 1 <= cnt[1][0] - cnt[0][1] <= cnt[1][1] // 2 else "No")

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    a = LI()
    max_a = max(a)
    min_a = min(a)

    if max_a > min_a + 1:
        print('No')
        return

    x = a.count(min_a)
    if max_a == min_a:
        if min_a == N-1 or min_a <= N//2:
            print('Yes')
        else:
            print('No')
        return

    if x < max_a and (N-x) >= (max_a - x) * 2:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
s = list(set(l))
if len(s)> 2:
    print("No")
    exit()
if len(s) == 1:
    if s[0] == n-1 or s[0] <= n//2:
        print("Yes")
    else:
        print("No")
    exit()
if abs(s[0]-s[1])>1:
    print("No")
    exit()
x,y = min(s),max(s)
a = l.count(x)
b = n-a
if a+b//2 >= y and a <= x:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    col = list(map(int, input().split()))
    col_min, col_max = min(col), max(col)
    if col_min == col_max:
        if col_min == 1 or col_min == n-1:
            print("Yes")
        elif 2*col_min <= n:
            print("Yes")
        else:
            print("No")
    elif col_min + 1 == col_max:
        cnt_min, cnt_max = 0, 0
        for v in col:
            if v == col_min:
                cnt_min += 1
            else:
                cnt_max += 1
        if cnt_max == 1:
            print("No")
        else:
            m = cnt_max//2
            if col_min < cnt_min-1 + 1 or cnt_min-1 + m < col_min:
                print("No")
            else:
                p = col_min - (cnt_min-1)
                if p + cnt_min == col_max:
                    print("Yes")
                else:
                    print("No")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 【考察】
# 最低限 abs(ai - aj) <= 1 じゃないとNG。（※）
# とはいえ、これだけでは不十分。
#     例：1 1 2（2・3と1・3が同じ種類で1・2が違う種類になることはない）
# ※の条件から、猫の発言内容は
# 1. 「n匹がk種類、N-n匹がk+1種類と発言」（0 < k < N - 1、0 < n < N）
# 2. 「N匹すべてk種類と発言」（0 < k < N）
# とまとめられる。
# （1. について）
# こうなるのは、猫全体の種類がk+1種類の場合に限られる。
# * 「k種類」と発言しているn匹の猫
#   これらの猫と同じ種類の猫は他に存在しない（自分を除外すると種類数が減る必要があるため）。
#   → 少なくともn+1種類存在することになるので k + 1 >= n + 1、つまりk >= nであればOK。
#   → n種類の割り当ては確定するので、割り当てが未確定な種類の残りは「k + 1 - n」種類。
# * 「k+1種類」と発言しているN-n匹の猫
#   これらの猫に残りの「k + 1 - n」種類を割り当てることになる。
#   これらの猫には、自分と同じ種類の猫が他にいないとNG（自分を除外した時に種類数が減ってしまう）。
#   各種類2匹以上確保できれば良いので
#   「2 * (k + 1 - n) <= N - n」が成り立てばOK。
# （2. について）
# 全体の種類がk種類の場合：
#   自分を除外して種類数が減らないようにしないといけない。
#   そのため、各種類2匹以上存在（2*k <= N）すればOK。
# 全体の種類がk+1種類の場合：
#   自分を除外して種類数が減るようにしないといけない。
#   そのため、各種類1匹ずつのみ存在（k + 1 == N）すればOK。
# 【解法まとめ】
# if max(a) - min(a) > 1
#   Noで終了。
# elif max(a) - min(a) == 1
#   猫の発言を「n匹がk種類、N-n匹がk+1種類と発言」（0 < k < N - 1、0 <= n < N）という形式に直す。
#   「k >= n and 2 * (k + 1 - n) <= N - n」ならYes、それ以外ならNoを出力。
# else (max(a) - min(a) == 0)
#   猫の発言を「N匹がk種類と発言」（0 < k < N）という形式に直す。
#  「2 * k <= N or k + 1 == N」ならYes、それ以外ならNoを出力。


def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_a, min_a = max(A), min(A)
    if max_a - min_a > 1:
        print('No')
    elif max_a - min_a == 1:
        k = min_a
        n = len([a for a in A if a == k])
        if k >= n and 2 * (k + 1 - n) <= N - n:
            print('Yes')
        else:
            print('No')
    else:  # max_a - min_a == 0
        k = min_a
        if 2 * k <= N or k + 1 == N:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    MAX = max(A)
    MIN = min(A)
    if MAX == MIN:
        print("Yes" if MAX + 1 == n or 2 * MAX <= n else "No")
    elif MAX - MIN == 1:
        cnt = A.count(MIN)
        print("Yes" if cnt < MAX and cnt + 2 * (MAX - cnt) <= n else "No")
    else:
        print("No")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
if (A[-1]-A[0])>1:
  print('No')
  exit()
elif (A[-1]-A[0])==0:
  if 1<=A[0] and A[0]<=N//2:
    print('Yes')
    exit()
  else:
    if A[0]+1==N:
      print('Yes')
      exit()    
    else:
      print('No')
      exit()
  
import bisect
a=bisect.bisect_right(A,A[0])
#少ない数a,多い数b
b=N-a
if b==1:
  print('No')
  exit()
if (a-1)+1<=A[0] and A[0]<=(a-1)+b//2 and a+1<=A[-1] and A[-1]<=a+b//2:
  print('Yes')
else:
  print('No')

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    M, m = max(a), min(a)
    c = a.count(m)
    C = a.count(M)
    
    if M == m:
        if n//2 >= m or m == n-1:
            judge = True
        else:
            judge = False
    else:
        if M - m > 1:
            judge = False
        elif M - c <= 0:
            judge = False
        elif n-c >= (M-c)*2:
            judge = True
        else:
            judge = False
        
    
    print("Yes" if judge else "No")
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    a_max = max(a)
    a_min = min(a)
    if a_max - a_min > 1:
        return print("No")
    elif a_max == a_min:
        if 1 <= a_min <= n // 2 or a_min == n - 1:
            return print("Yes")
        else:
            return print("No")
    else:
        c_min = a.count(a_min)
        c_max = a.count(a_max)

        if 1 <= a_max - c_min <= c_max // 2:
            return print("Yes")
        else:
            return print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n=II()
	A=LI()


	A.sort()

	a=A[0]
	b=A[-1]

	ans="No"

	if b-a==0:
		if n==a+1 or n>=a*2:
			ans="Yes"

	elif b-a==1:
		aa=A.count(a)
		if a>=aa and 2*a-aa+2<=n:
			ans="Yes"




	print(ans)




















if __name__ == "__main__":
	main()

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:
    # alone
    if M == n-1:
        print('Yes')
    elif M*2 <= n:
        print('Yes')
    else:
        print('No')
else:
    c = M
    x = 0
    for a in A:
        if a == m:
            x += 1
    if x < c and (c-x)*2 <= (n-x):
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
if max(a) - min(a) >= 2:
    print("No")
    exit()
else:
    M = max(a)
    m = min(a)
    if M == m:
        if m <= N / 2 or m == N - 1:
            print("Yes")
        else:
            print("No")
    else:
        if a.count(m) >= M or a.count(M) + 2 * a.count(m) < 2 * M:
            print("No")
        else:
            print("Yes")

Submission status: Accepted

Solution code:

def solve(A):
    N = len(A)
    p = max(A)
    if p > min(A)+1:
        return False

    cnt = sum(int(a==p) for a in A)

    if p == N-1 and cnt == N:
        return True

    cnt_max = 2*(N-p)
    cnt_min = N-p+1

    return cnt_min <= cnt <= cnt_max

if __name__ == '__main__':
    N = int(input())
    A = tuple(map(int,input().split()))
    print('Yes' if solve(A) else 'No')

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    mi = min(a)
    ma = max(a)

    if ma-mi > 1:
        print("No")
    elif ma == mi:
        if 1 <= mi <= n//2 or mi == n-1:
            print("Yes")
        else:
            print("No")
    else:
        nmi = a.count(mi)
        nma = a.count(ma)
        if nmi+1 <= ma <= nmi+nma//2:
            print("Yes")
        else:
            print("No")

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
amax=max(a)
amin=min(a)
if amax-amin>=2:
    print("No")
    exit()
elif amax==amin:
    if amax==n-1 or amax*2<=n:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
ac=a.count(amin)
ad=n-ac
if amin-ac<0:
    print("No")
    exit()

if (amax-ac)*2<=ad:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
M = max(a)
m = min(a)
if M > m + 1:
    print("No")
else:
    if M == m:
        if M == N-1:
            print("Yes")
        elif M*2 <= N:
            print("Yes")
        else:
            print("No")

    else:
        # ai == m　ならば、ai以外にその色はない
        c = a.count(m)
        if (M - c) * 2 <= N-c and c < M:  # (M-c) -> 一人だけではない色の種類一人だけではないはずなので*2 したものよりも残りの人数が多いはず
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
n = int(input())
A = list(int(x) for x in input().split())

ma = max(A)
mi = min(A)

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

if ma == mi:
    if n >= ma * 2 or n == ma + 1:
        print("Yes")
    else:
        print("No")
    exit()

# ma = mi + 1
if A.count(mi) <= mi and A.count(ma) >= (ma - A.count(mi)) * 2:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
ca=dict(Counter(a))
if len(ca.keys())>2:
  print('No')
elif len(ca.keys())==1:
  if 2*a[0]<=n or a[0]==n-1:
    print('Yes')
  else:
    print('No')
else:
  c=max(ca.keys())
  d=min(ca.keys())
  # cといった猫はその猫しかかぶっていない帽子をかぶっている
  # dといった猫はその猫以外にもかぶっている帽子をかぶっている
  if c!=d+1:
    print('No')
  else:
    tmp=c-ca[d]
    # tmp:dといった猫たちがかぶっている帽子の種類数
    if tmp>0 and 2*tmp<=ca[c]:
      print('Yes')
    else:
      print('No')

Submission status: Accepted

Solution code:
def answer(x):
  print(x)
  exit()

N=int(input())
A=list(map(int,input().split()))
if len(set(A))>=3:
  answer('No')
if len(set(A))==1:
  if N//2>=A[0] or A[0]==N-1:
    answer('Yes')
  else:
    answer('No')
A.sort()
if A[0]+1<A[-1]:
  answer('No')
X=1
for i in range(N-1):
  if A[i]==A[i+1]:
    X+=1
  else:
    break
if X==N-1:
  answer('No')
if X+1<=A[-1]<=X+(N-X)//2:
  answer('Yes')
else:
  answer('No')

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    K = A[-1]
    if A[0] == K:
        return K == N - 1 or (K >= 1 and 2 * K <= N)
    if A[0] != K - 1:
        return False
    counter = collections.Counter(A)
    d = counter[K - 1]
    if K <= d:
        return False
    if N - d <= 1:
        return False
    return 2 * (K - d) <= N - d


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

Submission status: Accepted

Solution code:
def check():
    N = int(input())
    A = list(map(int, input().split()))
    if len(set(A))==1:
        if max(A)==N-1:
            return 'Yes'
    large = max(A)
    small = large-1
    n_s = list(map(lambda x:x-small,A)).count(0)
    if large==n_s:
        if n_s==N:
            return 'Yes'
        return 'No'
    if large<n_s:
        return 'No'
    if 2*(large-n_s)+n_s<=N:
        return 'Yes'
    return 'No'
print(check())

Submission status: Accepted

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

if max(a)-min(a) == 0:
    if a[0] == n-1 or 2*a[0] <= n:
        print("Yes")
    else:
        print("No")
elif max(a)-min(a) == 1:
    A = max(a)
    alone = 0
    not_alone = 0
    for i in a:
        if i == A:
            not_alone += 1
        else:
            alone += 1
    if alone < A and 2*(A-alone) <= not_alone:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Accepted

Solution code:
yes="Yes"
no="No"
n=int(input())
a=list(map(int,input().split()))
if max(a)-min(a)>1:exit(print(no))
if a==[a[0]]*n:
  if a[0]==n-1:print(yes)
  elif 2*a[0]<=n:print(yes)
  else:print(no)
else:
  mi=a.count(min(a))
  ma=n-mi
  if mi<max(a) and 2*(max(a)-mi)<=ma:print(yes)
  else:print(no)