Problem:


Score : 400 points

Problem Statement

We have an H-by-W matrix.
Let a_{ij} be the element at the i-th row from the top and j-th column from the left.
In this matrix, each a_{ij} is a lowercase English letter.

Snuke is creating another H-by-W matrix, A', by freely rearranging the elements in A.
Here, he wants to satisfy the following condition:

Every row and column in A' can be read as a palindrome.

Determine whether he can create a matrix satisfying the condition.

Note

A palindrome is a string that reads the same forward and backward.
For example, a, aa, abba and abcba are all palindromes, while ab, abab and abcda are not.

Constraints

1 ≤ H, W ≤ 100

a_{ij} is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}

Output

If Snuke can create a matrix satisfying the condition, print Yes; otherwise, print No.

Sample Input 1

3 4
aabb
aabb
aacc

Sample Output 1

Yes

For example, the following matrix satisfies the condition.

abba
acca
abba

Sample Input 2

2 2
aa
bb

Sample Output 2

No

It is not possible to create a matrix satisfying the condition, no matter how we rearrange the elements in A.

Sample Input 3

5 1
t
w
e
e
t

Sample Output 3

Yes

For example, the following matrix satisfies the condition.

t
e
w
e
t

Sample Input 4

2 5
abxba
abyba

Sample Output 4

No

Sample Input 5

1 1
z

Sample Output 5

Yes



Sample input:
3 4
aabb
aabb
aacc


Sample output:
Yes

Submission status: Accepted

Solution code:
H,W=list(map(int,input().split()))
l=[]
for i in range(H):
   l.append(list(input()))
from collections import Counter
l=sum(l,[])
l=Counter(l)
one=(H%2)*(W%2)
two=(H%2)*(W//2)+(W%2)*(H//2)
four=(H//2)*(W//2)
for i in l.values():
   j=i//4
   i=i%4
   four-=j
   if i==1:
      one-=1
   elif i==2:
      two-=1
   elif i==3:
      one-=1;two-=1
if set([0]) == set([one,two,four]):
   print("Yes")
else:
   if four<0:
      two+=four*2
   four=0
   if set([0]) == set([one,two,four]):
      print("Yes")
   else:
      print("No")

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int,input().split())
d = Counter()
for _ in range(H):
  d.update(list(input()))

# check palindrome
def main():
  num1 = (H*W) % 2 
  num2 = (W % 2)*H//2 + (H % 2)*W//2
  num4 = ((H*W) - num1 - num2*2)//4
  #print(num1,num2,num4)

  check1 = sum([val % 2 for key,val in d.items()])
  #print(check1)
  if check1 != num1:
    return False
  
  check4 = 0
  for key,val in d.items():
    if val >= 4:
      deduct = min(num4-check4,val//4)
      d[key] = val - deduct*4
      check4 += deduct
      
      if check4 == num4:
        break
    
  #print(check4)
  if check4 != num4:
    return False
  
  check2 = sum([val//2 for key,val in d.items()])
  #print(check2)
  if check2 != num2:
    return False
      
  return True
      
  
ans = main()
if ans:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
S = []
for _ in range(H):
  S.append(input())

# check palindrome

def main():
  num1 = (H*W) % 2 
  num2 = (W % 2)*H//2 + (H % 2)*W//2
  num4 = ((H*W) - num1 - num2*2)//4
  #print(num1,num2,num4)
  d = {}
  for i in range(H):
    for j in range(W):
      ch = S[i][j]
      if ch in d:
        d[ch] += 1
      else:
        d[ch] = 1

  check1 = sum([val % 2 for key,val in d.items()])
  #print(check1)
  if check1 != num1:
    return False
  
  check4 = 0
  for key,val in d.items():
    if val >= 4:
      deduct = min(num4-check4,val//4)
      d[key] = val - deduct*4
      check4 += deduct
      
      if check4 == num4:
        break
    
  #print(check4)
  if check4 != num4:
    return False
  
  check2 = sum([val//2 for key,val in d.items()])
  #print(check2)
  if check2 != num2:
    return False
      
  return True
      
  
ans = main()
if ans:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
from collections import Counter

H, W = map(int, input().split())
S = Counter()
for _ in range(H):
    S.update(list(input()))

val1, val2 = 0, 0
for v in S.values():
    if v % 2:
        val1 += 1
    elif v % 4:
        val2 += 1

val1_lim = 1 if (H % 2 and W % 2) else 0
val2_lim = 0
if H % 2:
    val2_lim += W // 2
if W % 2:
    val2_lim += H // 2

print('Yes' if val1 <= val1_lim and val2 <= val2_lim else 'No')

Submission status: Accepted

Solution code:
from collections import defaultdict
h, w = map(int, input().split())

a = [list(input()) for _ in range(h)]
d = defaultdict(int)
for i in range(h):
    for j in range(w):
        d[ord(a[i][j]) - ord('a')] += 1

odd = 0
two = 0
four = 0
for i in range(26):
    four += d[i] // 4
    d[i] %= 4
    if d[i] % 2 == 0:
        two += d[i] // 2
    else:
        odd += 1

if h % 2 == 1 and w % 2 == 1:
    if odd == 1 and two <= h // 2 + w // 2:
        print('Yes')
    else:
        print('No')
elif h % 2 == 1:
    if odd == 0 and two <= w // 2:
        print('Yes')
    else:
        print('No')
elif w % 2 == 1:
    if odd == 0 and two <= h // 2:
        print('Yes')
    else:
        print('No')
else:
    if odd == 0 and two == 0:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
from collections import Counter
h,w=map(int,input().split())
#a=[list(input()) for i in range(w)]
a=[]
flag=True
for i in range(h):
  a+=list(input())
ca=Counter(a)
if h%2==0 and w%2==0:
  for i in ca:
    if ca[i]%4!=0:
      flag=False
      print('No')
      break
  if flag:
    print('Yes')

elif h%2!=0 and w%2!=0:
  yon=(h-1)*(w-1)
  ni=h*w-yon-1
  iti=1
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      elif iti>0:
        iti-=1
        ca[i]-=1
      else:
        break
  if yon==0 and ni==0 and iti==0:
    print('Yes')
  else:
    print('No')
else:
  if h%2==0:
    yon=(h)*(w-1)
  else:
    yon=(h-1)*(w)
  ni=h*w-yon
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      else:
        break
  if yon==0 and ni==0:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


H,W = MI()
a = [LS2() for _ in range(H)]

from collections import defaultdict

d = defaultdict(int)
for i in range(H):
    for j in range(W):
        d[a[i][j]] += 1

if H % 2 == 0 and W % 2 == 0:
    for key in d.keys():
        if d[key] % 4 != 0:
            print('No')
            exit()
    print('Yes')

if H % 2 == 0 and W % 2 != 0:
    H,W = W,H

if H % 2 != 0 and W % 2 == 0:
    a = 0  # 登場回数が4で割って2余るような、英小文字の個数
    for key in d.keys():
        if d[key] % 2 != 0:
            print('No')
            exit()
        elif d[key] % 4 != 0:
            a += 1
    if a <= W//2:
        print('Yes')
        exit()
    else:
        print('No')
        exit()

if H % 2 != 0 and W % 2 != 0:
    a,b = 0,0  # 登場回数が奇数,2(mod 4)であるような、英小文字の個数
    for key in d.keys():
        if d[key] % 4 == 1:
            a += 1
        elif d[key] % 4 == 3:
            a += 1
            b += 1
        elif d[key] % 4 == 2:
            b += 1
    if a <= 1 and b <= H//2 + W//2:
        print('Yes')
        exit()
    else:
        print('No')
        exit()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
C = {chr(i):0 for i in range(97,123)}
for i in range(H):
    for j in range(W):
        C[A[i][j]] += 1
if H%2==0 and W%2==0:
    flag = 0
    for a in C:
        if C[a]%4!=0:
            flag = 1
            break
    if flag==0:
        print("Yes")
    else:
        print("No")
elif H%2==0 and W%2==1:
    cnt = 0
    flag = 0
    for a in C:
        if C[a]%4==2:
            cnt += 1
        elif C[a]%4!=0:
            flag = 1
            break
    if flag==1:
        print("No")
    else:
        if cnt<=H//2:
            print("Yes")
        else:
            print("No")
elif H%2==1 and W%2==0:
    flag = 0
    cnt = 0
    for a in C:
        if C[a]%4==2:
            cnt += 1
        elif C[a]%4!=0:
            flag = 1
            break
    if flag==1:
        print("No")
    else:
        if cnt<=W//2:
            print("Yes")
        else:
            print("No")
else:
    cnt1 = 0
    cnt2 = 0
    for a in C:
        if C[a]%4==2:
            cnt2 += 1
        elif C[a]%2==1:
            cnt1 += 1
    if cnt1!=1:
        print("No")
    else:
        if cnt2<=(H-1)//2+(W-1)//2:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
import sys
from collections import Counter
 
H, W = map(int, sys.stdin.readline().split())
 
string = ""
for _ in range(H):
    string += sys.stdin.readline().strip()
 
counter = Counter(string)
e_one = 0
e_two = 0
e_four = 0
for key, count in counter.items():
    tmp = count // 4
    e_four += tmp
    count -= 4 * tmp
    tmp = count // 2
    e_two += tmp
    count -= 2 * tmp
    e_one += count
 
one = 0
two = 0
four = 0
if H % 2 == 0 and W % 2 == 0:
    four = H * W // 4
# 奇数の場合、中心の文字は1つしかなくても回文になる
elif H % 2 == 1 and W % 2 == 1:
    one = 1
    two = H // 2 + W // 2
    four = (H * W - (one + two * 2)) // 4
else:
    # 縦を奇数とする
    if W % 2 == 1:
        H, W = W, H
 
    two = W // 2
    four = (H * W - two * 2) // 4
 
if four > e_four:
    print("No")
else:
    e_four -= four
    e_two += e_four * 2
    if two > e_two:
        print("No")
    else:
        e_two -= two
        e_one += e_two * 2
        if e_one == one:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w = inpl()
cnt = defaultdict(int)
for _ in range(h):
    for x in input():
        cnt[x] += 1
one = two = 0
for va in cnt.values():
    now = va%4
    if now == 1 or now == 3:
        one += 1
    if now == 2 or now == 3:
        two += 1
res = False
if h%2 == 0 and w%2 == 0:
    if not one and not two:
        res = True
elif h%2 and w%2:
    if one == 1 and two <= (w-1)//2 + (h-1)//2:
        res = True
else:
    now = h if w%2 else w
    if not one and two <= now//2:
        res = True
print('Yes' if res else 'No')

Submission status: Accepted

Solution code:
from collections import Counter
h, w, *s = open(0).read().split()
h = int(h)
w = int(w)

s = Counter(''.join(s))

odd = 0
two = 0
four = 0
for k, v in s.items():
    four += v // 4
    v %= 4
    if v % 2 == 0:
        two += v // 2
    else:
        odd += 1
if h % 2 == 1 and w % 2 == 1:
    if odd == 1 and two <= h // 2 + w // 2:
        print('Yes')
    else:
        print('No')
elif h % 2 == 1:
    if odd == 0 and two <= w // 2:
        print('Yes')
    else:
        print('No')
elif w % 2 == 1:
    if odd == 0 and two <= h // 2:
        print('Yes')
    else:
        print('No')
else:
    if odd == 0 and two == 0:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int, input().split())
a = ''
for _ in range(H):
    a += input()
cnt_counter = list(Counter(a).values())
yes_flag = False
if H % 2 == 0 and W % 2 == 0:
    if all([i % 4 == 0 for i in cnt_counter]):
        yes_flag = True
elif H % 2 == 1 and W % 2 == 1:
    two_cnt = (H // 2) + (W // 2)
    four_cnt = (H // 2) * (W // 2)
    for i in range(len(cnt_counter)):
        if cnt_counter[i] % 2 == 1:
            cnt_counter[i] -= 1
            break
    else:
        print('No')
        exit()
    for i in range(len(cnt_counter)):
        if cnt_counter[i] <= 0:
            continue
        if cnt_counter[i] % 2 == 0 and cnt_counter[i] % 4 != 0:
            two_cnt -= 1
            cnt_counter[i] -= 2
        if two_cnt == 0:
            break
    for i in range(len(cnt_counter)):
        if cnt_counter[i] <= 0:
            continue
        if cnt_counter[i] % 4 != 0:
            break
        while two_cnt > 1 and cnt_counter[i]:
            two_cnt -= 2
            cnt_counter[i] -= 4
        while four_cnt > 0 and cnt_counter[i]:
            four_cnt -= 1
            cnt_counter[i] -= 4
    if two_cnt == four_cnt == 0:
        yes_flag = True
else:
    if H % 2 == 0:
        two_cnt = H // 2
    else:
        two_cnt = W // 2
    four_cnt = (H // 2) * (W // 2)
    for i in range(len(cnt_counter)):
        if cnt_counter[i] % 2 == 0 and cnt_counter[i] % 4 != 0:
            two_cnt -= 1
            cnt_counter[i] -= 2
        if two_cnt == 0:
            break
    for i in range(len(cnt_counter)):
        if cnt_counter[i] <= 0:
            continue
        if cnt_counter[i] % 4 != 0:
            break
        while two_cnt > 1 and cnt_counter[i]:
            two_cnt -= 2
            cnt_counter[i] -= 4
        while four_cnt > 0 and cnt_counter[i]:
            four_cnt -= 1
            cnt_counter[i] -= 4
    if two_cnt == four_cnt == 0:
        yes_flag = True
if yes_flag:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
H,W = map(int,input().split())

A = [list(input()) for _ in range(H)]

memo = {}
for a in A:
    for ai in a:
        if ai in memo:
            memo[ai] += 1
        else:
            memo[ai] = 1
            
mod0 = []
mod1_3 = []
mod2 = []
for key, value in memo.items():
    if value % 4 == 0:
        mod0.append(key)
    elif value % 4 == 2:
        mod2.append(key)
    else:
        mod1_3.append(key)

if W % 2 == 0 and H % 2 == 0:
    if len(mod1_3) > 0 or len(mod2) > 0:
        print("No")
    else:
        print("Yes")

elif W % 2 == 0 or H % 2 == 0:
    if H % 2 == 0:
        W, H = H, W
 
    if W // 2 < len(mod2):
        print("No")
    elif len(mod1_3) > 0:
        print("No")
    else:
        print("Yes")

else:
    if len(mod1_3) == 1 and len(mod2) <= H // 2 + W // 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = ""
inf = 1e5
cnt = {}
ans = "Yes"
for i in range(H):
    a = input()
    A += a

for a in A:
    if a not in cnt.keys():
        cnt[a] = 1
    else:
        cnt[a] += 1
jud = [inf, 0, 0, 0]
if H % 2 == 1 and W % 2 == 1:
    jud[2] = H//2+W//2
    jud[1] = 1
elif H % 2 == 1:
    jud[2] = W//2
elif W % 2 == 1:
    jud[2] = H//2
for i in cnt.values():
    b = i % 4
    jud[b] -= 1
    if jud[b] < 0:
        ans = "No"
print(ans)

Submission status: Accepted

Solution code:
def main():
    examB()

def examA():
    S = SI()
    S = ">" + S + "<"
    N = len(S)
    A = [0]*N
    i = 0
    while(i<N-1):
        r = i + 1
        if S[i]==">" and S[i+1]=="<":
            A[i] = 0
            l = i-1
            cur = 0
            while(1<=l):
                cur += 1
                A[l] = max(A[l], cur)
                l -= 1
                if S[l+1]=="<":
                    #print("break",l,A)
                    break
            r = i+1
            cur = 0
            while(r<N-1):
                cur += 1
                A[r] = max(A[r], cur)
                r += 1
                if r==N-1:
                    break
                if S[r]==">":
                    break
        #print(i,A)
        i = r
    #print(A)
    A[0] = 0; A[-1] = 0
    ans = sum(A)
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI()for _ in range(H)]
    C = defaultdict(int)
    for a in A:
        for s in a:
            C[s] += 1
    B = sorted(C.items())
    # print(B)
    flag_odd = not (H%2==1 and W%2==1)
    upper_2 = (H%2==1) * (W//2) + (W%2==1) * (H//2)
    for s,c in B:
        if c%2==1:
            if flag_odd:
                print("No")
                return
            flag_odd = True
        elif c%4==2:
            upper_2 -= 1
            if upper_2<0:
                print("No")
                return
    print("Yes")
    return

def examC():
    N, K = LI()
    P = LI()
    C = LI()

    if max(C)<0:
        print(max(C))
        return

    loop = [[0,0]for _ in range(N)]

    for i in range(N):
        checked = set()
        now = i
        score = 0
        while(now not in checked):
            checked.add(now)
            now = P[now]-1
            score += C[now]
        n = len(checked)
        for j in checked:
            loop[j] = [n,score]
    # print(loop)
    ans = 0
    for i in range(N):
        n,s = loop[i]
        score = 0
        if s>0:
            score += (K//n - 1) * s
        ans = max(ans,score)
        now = i
        for j in range(n + K%n):
            now = P[now] - 1
            score += C[now]
            ans = max(ans,score)

    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,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()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np

h, w = map(int, input().split())
arr = [list(map(str, input().rstrip())) for _ in range(h)]

arr = sum(arr, [])

arr = Counter(arr)
arr = np.array(list(arr.values()))


def solve(arr):
    # 偶数×偶数なら、制約がかなりきつい
    if h % 2 == 0 and w % 2 == 0:
        return np.all(arr % 4 == 0)

    # 奇数×奇数なら、
    elif h % 2 == 1 and w % 2 == 1:
        even = (h + w) // 2 - 1
        if (arr % 2 == 1).sum() != 1:
            return False
        odd = arr[np.where(arr % 2 == 1)].sum()
        if odd % 4 == 3:
            even -= 1
        arr = arr[np.where(arr != odd)]
        ans = (arr % 4 == 2).sum() <= even
        ans &= np.all(arr[np.where(arr % 4 != 2)] % 4 == 0)
        return ans

    #　どちらかの辺が偶数なら
    else:
        even = h // 2 if h % 2 == 0 else w // 2
        ans = (arr % 4 == 2).sum() <= even
        ans &= np.all(arr[np.where(arr % 4 != 2)] % 4 == 0)
        return ans


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

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
al = [list(input()) for _ in range(h)]
cnts = {}
for row in al:
    for a in row:
        cnts.setdefault(a,0)
        cnts[a] += 1
        cnts[a]%= 4

c4 = [0]*5
for i,v in cnts.items():
    c4[v] += 1
c4[4] = c4[0]


if w%2 == 0 and h%2 == 0:
    if c4[1] == 0 and c4[2] == 0 and c4[3] == 0:
        print('Yes')
    else:
        print('No')

elif w%2 == 1 and h%2 == 1:
    if c4[1] + c4[3] == 1 and c4[3] + c4[2] <= (h-1)//2 + (w-1)//2:
        print('Yes')
    else:
        print('No')

elif w%2 == 1 and h%2 == 0:
    if c4[1] + c4[3] == 0 and c4[2] <= h//2:
        print('Yes')
    else:
        print('No')

elif w%2 == 0 and h%2 == 1:
    if c4[1] + c4[3] == 0 and c4[2] <= w//2:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    alp = [0]*26
    for _ in range(h):
        s = input()
        for c in s:
            p = ord(c) - ord("a")
            alp[p] += 1
    f = True
    cnt_1, cnt_2, cnt_4 = 0, 0, 0
    if h%2 == 1 and w%2 == 1:
        cnt_1 = 1
        cnt_2 = w-1 + h-1
        cnt_4 = (w-1)*(h-1)
    elif h%2 == 1 and w%2 == 0:
        cnt_2 = w
        cnt_4 = w*(h-1)
    elif h%2 == 0 and w%2 == 1:
        cnt_2 = h
        cnt_4 = (w-1)*h
    else:
        cnt_4 = w*h
    for i in range(26):
        while cnt_4 > 0 and alp[i]>=4:
            alp[i] -= 4
            cnt_4 -= 4
    if cnt_4 > 0:
        f = False
    for i in range(26):
        while cnt_2 > 0 and alp[i]>=2:
            alp[i] -= 2
            cnt_2 -= 2
    if cnt_2 > 0:
        f = False
    for i in range(26):
        while cnt_1 > 0 and alp[i]>=1:
            alp[i] -= 1
            cnt_1 -= 1
    if cnt_1 > 0:
        f = False
    if f:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


H,W = MI()
a = [LS2() for _ in range(H)]

from collections import defaultdict

d = defaultdict(int)
for i in range(H):
    for j in range(W):
        d[a[i][j]] += 1

if H % 2 == 0 and W % 2 == 0:
    for key in d.keys():
        if d[key] % 4 != 0:
            print('No')
            exit()
    print('Yes')

if H % 2 == 0 and W % 2 != 0:
    H,W = W,H

if H % 2 != 0 and W % 2 == 0:
    a = 0
    for key in d.keys():
        if d[key] % 2 != 0:
            print('No')
            exit()
        elif d[key] % 4 != 0:
            a += 1
    if a <= W//2:
        print('Yes')
        exit()
    else:
        print('No')
        exit()

if H % 2 != 0 and W % 2 != 0:
    a,b = 0,0
    for key in d.keys():
        if d[key] % 4 == 1:
            a += 1
        elif d[key] % 4 == 3:
            a += 1
            b += 1
        elif d[key] % 4 == 2:
            b += 1
    if a <= 1 and b <= H//2 + W//2:
        print('Yes')
        exit()
    else:
        print('No')
        exit()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
X=[0 for i in range(26)]
a=[list(input()) for i in range(H)]
for i in range(H):
    for j in range(W):
        X[ord(a[i][j])-97]+=1
A=[i%4 for i in X]
B=[i%2 for i in X]
if H%2==0 and W%2==0:
    if sum(A)==0:
        print("Yes")
    else:
        print("No")
elif H%2==1 and W%2==1:
    if sum(B)==1 and sum(A)<=H+W-1:
        print("Yes")
    else:
        print("No")
else:
    if H%2==0:
        H,W=W,H
    #H:odd
    if sum(B)==0 and sum(A)<=W:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [input() for i in range(H)]
from collections import Counter
ctr = Counter()
for row in A:
    ctr.update(row)

if H%2==0 and W%2==0:
    print('Yes' if all(v%4==0 for v in ctr.values()) else 'No')
    exit()

if H%2==0 or W%2==0:
    if H%2: H,W = W,H
    if any(v%2 for v in ctr.values()):
        print('No')
        exit()
    pair = 0
    for v in ctr.values():
        if v%4==2:
            pair += 1
    print('Yes' if pair*2 <= H else 'No')

else:
    odd = 0
    for k in ctr.keys():
        if ctr[k]%2:
            odd += 1
            ctr[k] -= 1
    if odd != 1:
        print('No')
        exit()
    pair = 0
    for v in ctr.values():
        if v%4==2:
            pair += 1
    print('Yes' if pair*2 <= H+W-2 else 'No')

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import defaultdict
import sys

H, W = (int(x) for x in input().split())

freq = defaultdict(int)

for i in range(H):
    for c in input():
        freq[c] += 1

nDiv4 = 0
nDiv2 = 0
nDiv1 = 0
for c in freq:
    num = freq[c]

    d4 = num // 4
    nDiv4 += d4
    num -= d4 * 4

    d2 = num // 2
    nDiv2 += d2
    num -= d2 * 2

    nDiv1 += num 

canDiv2 = 0
if H % 2 != 0:
    canDiv2 += W // 2
if W % 2 != 0:
    canDiv2 += H // 2

if H % 2 != 0 and W % 2 != 0:
    if nDiv1 != 1:
        print("No")
        sys.exit(0)
else:
    if nDiv1 != 0:
        print("No")
        sys.exit(0)

if nDiv2 <= canDiv2:
    print("Yes")
else:
    print("No")

#print(nDiv1, nDiv2, nDiv4)
#print(nDiv2, canDiv2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    h, w = map(int, input().split())
    a = []
    for _ in range(h):
        a.extend(list(input()))
    a_ac = Counter(a)
    a_ac_v = list(a_ac.values())
    a_ac_v.sort(reverse=True)
    if h == 1 or w == 1:
        a_ac_v_parity_ac = Counter([i & 1 for i in a_ac_v])
        if h&1 == 1 and w&1 == 1:
            if a_ac_v_parity_ac[1] == 1:
                print('Yes')
            else:
                print('No')
            sys.exit()
        else:
            if a_ac_v_parity_ac[1] >= 1:
                print('No')
            else:
                print('Yes')
            sys.exit()

    num = []
    num.extend([4] * ((h // 2) * (w // 2)))

    if h&1:
        num.extend([2] * (w // 2))
    if w&1:
        num.extend([2] * (h // 2))
    if h&1 and w&1:
        num.extend([1])
    while sum(num):
        if a_ac_v[0] >= num[0]:
            a_ac_v[0] -= num[0]
            num[0] = 0
            a_ac_v.sort(reverse=True)
            num.sort(reverse=True)
        else:
            break
    if num[0] == 0 and a_ac_v[0] == 0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = ''

for i in range(h):
    a += input()
from collections import Counter
c = Counter(a)

if h==1 or w==1:
    odd = 0
    for i in c:
        if c[i]%2==1:
            odd += 1
    print('Yes' if odd<=1 else 'No')
    exit()

x = h*(w%2)+w*(h%2)-(h*w)%2
y = 0
z = 0
for i in c:
    y += c[i]%4
    c[i] = c[i]%4
    if c[i]%2==1:
        z += 1

print('Yes' if y<=x and z<=1 else 'No')

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
h,w=map(int,input().split())
a=[input() for _ in range(h)]
cnt={}
for i in range(h):
    ar=a[i]
    for j in ar:
        if j in cnt:
            cnt[j]+=1
        else:
            cnt[j]=1
if h%2==0:
    if w%2==0:
        for i in cnt:
            if cnt[i]%4!=0:
                print("No")
                break
        else:
            print("Yes")
    else:
        res=0
        for i in cnt:
            if cnt[i]%4!=0 and cnt[i]%4!=2:
                print("No")
                break
            elif cnt[i]%4==2:
                res+=1
        else:
            if res>h//2:
              print("No")
            else:
              print("Yes") 
else:
    res=0
    if w%2==0:
        for i in cnt:
            if cnt[i]%4!=0 and cnt[i]%2==0:
                res+=1
            elif cnt[i]%2!=0:
                print("No")
                break
        else:
            if res>w//2:
                print("No")
            else:
                print("Yes")
    else:
        res1=0
        for i in cnt:
            if cnt[i]%4!=0  and cnt[i]%2==1:
                res1+=1
            if cnt[i]%4!=0 and cnt[i]%2==0:
                res+=1       
        if res1==1 and res<=(h-1)//2+(w-1)//2:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
D={}
for y in range(H):
    S=input()
    for s in S:
        if s in D:
            D[s]+=1
        else:
            D[s]=1

if (H%2)+(W%2)==0:
    F=True
    for s in D:
        if D[s]%4:
            F=False
elif (H%2)+(W%2)==1:
    if H%2:
        H,W=W,H

    F=True
    G=0
    for s in D:
        if D[s]%2:
            F=False
        elif D[s]%4==2:
            G+=1
    if G>H//2:
        F=False
else:
    G=0
    I=0
    for s in D:
        if D[s]%2:
            I+=1
        elif D[s]%4==2:
            G+=1
    F=(I==1) and (G<=(H+W-2)//2)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    d = defaultdict(int)

    for h in range(H):
        for w in range(W):
            d[A[h][w]] += 1
            d[A[h][w]] %= 4

    e = defaultdict(int)
    for a in d.values():
        e[a] += 1

    if H % 2 == 0 and W % 2 == 0:
        if e[1] or e[2] or e[3]:
            print('No')
        else:
            print('Yes')
    elif H % 2 == 1 and W % 2 == 1:
        if e[1] + e[3] == 1:
            if e[2] <= (H // 2 + W // 2):
                print('Yes')
            else:
                print('No')
        else:
            print('No')
    else:
        if e[1] or e[3]:
            print('No')
        else:
            if H % 2 == 0:
                cnt = H // 2
            else:
                cnt = W // 2
            if e[2] <= cnt:
                print('Yes')
            else:
                print('No')




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
h,w,*a = map(int,input().split())
a = []
for i in range(h):
  a += list(input().strip())
m1 = (h%2)*(w%2)
m2 = (h%2)*(w//2)+(h//2)*(w%2)
c = Counter(a)
c1,c2, = 0,0
for i in c.values():
  dc2,dc1 = divmod(i%4,2)
  c1 += dc1
  c2 += dc2
print("Yes" if m1>=c1 and m2>=c2 else "No")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())

a=[]
for i in range(h):
  a.append(input())

alpha=[0 for i in range(26)]

for i in range(h):
  for j in range(w):
    alpha[ord(a[i][j])-ord("a")]+=1


l=[0,0,0]
for i in range(26):
  l[0]+=alpha[i]//4
  alpha[i]=alpha[i]%4
  l[1]+=alpha[i]//2
  alpha[i]=alpha[i]%2
  l[2]+=alpha[i]
  alpha[i]=0

if l[1]<=(h//2)*(w%2)+(w//2)*(h%2) and l[2]==(h%2)*(w%2):
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=dict(zip([chr(i+97) for i in range(26)],[0]*26))
for i in range(h):
  for j in range(w):
    d[s[i][j]]+=1
a=[i%4 for i in d.values()]
print(['No','Yes'][a.count(1)+a.count(3)==h%2*w%2 and a.count(2)<=(h//2)*(w%2)+(w//2)*(h%2)])