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:
# -*- 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(H, W, M):
    C = Counter()
    for r in M:
        C.update(r)
    f = (H // 2) * (W // 2)
    t = (H % 2) * (W // 2) + (H // 2) * (W % 2)

    v = list(map(lambda x: -x, C.values()))
    heapq.heapify(v)
    for _ in range(f):
        c = -heapq.heappop(v)
        if c == 4:
            pass
        elif c > 4:
            c -= 4
            heapq.heappush(v, -c)
        else:
            return 'No'

    for _ in range(t):
        c = -heapq.heappop(v)
        if c == 2:
            pass
        elif c > 2:
            c -= 2
            heapq.heappush(v, -c)
        else:
            return 'No'
    return 'Yes'


def main():
    H, W = read_int_n()
    M = [read_str() for _ in range(H)]
    print(slv(H, W, M))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def examC():
    H, W = LI()
    A = [SI() for _ in range(H)]
    d = defaultdict(int)
    ans = "Yes"
    for a in A:
        for s in a:
            d[s] +=1
#    print(d)
    h = H//2; w = W//2; k = h*w
    for key,i in d.items():
        if k == 0:
            break
        while(d[key]>=4):
            d[key]-=4
            k -=1
            if k == 0:
                break
    if k>0:
        ans = "No"
#    print(d,k)
    k = 0
    if H%2==1:
        k +=w
    if W%2==1:
        k +=h
    for key,i in d.items():
        if k ==0:
            break
        while(d[key]>=2):
            d[key] -= 2
            k -= 1
            if k == 0:
                break
    if k>0:
        ans = "No"
#    print(d,k)
    print(ans)

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__':
    examC()

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())
table = collections.defaultdict(int)
for i in range(H):
    for x in input():
        table[x] += 1

tmp = 0

for x in table:
    if table[x] % 2 == 1:
        table[x] -= 1
        tmp += 1
num = [0, 0]
for x in table:
    num[1] += table[x] // 4
    if table[x] % 4 != 0:
        num[0] += 1


if H % 2 == 1 and W % 2 == 1:
    if tmp != 1:
        print("No")
        exit(0)
    else:
        if H+W - 2 < num[0] * 2:
            print("No")
            exit(0)
        else:
            if ((H+W - 2) - num[0]*2) % 4 != 0:
                print("No")
                exit(0)

elif H % 2 == 1 or W % 2 == 1:
    if tmp != 0:
        print("No")
        exit(0)
    else:
        if W % 2 == 1:
            H, W = W, H
        if W < num[0]*2:
            print("No")
            exit(0)
        else:
            if (W - num[0]*2) % 4 != 0:
                print("No")
                exit(0)

else:
    if num[0] != 0 or tmp != 0:
        print("No")
        exit(0)


print("Yes")

Submission status: Accepted

Solution code:
import collections

h,w=map(int, input().split())
a=[list(input()) for i in range(h)]
x=[]

for i in range(h):
    x+=a[i]

c = collections.Counter(x)
c = c.most_common()


if h%2==0 and w%2==0:
    for i in range(len(c)):
        if c[i][1]%4!=0:
            print('No')
            exit()

elif h%2==1 and w%2==0:
    for i in range(len(c)):
        if c[i][1]%4==0:
            continue
        elif c[i][1]%4==2:
            w-=2
            if w<0:
                print('No')
                exit()
        else:
            print('No')
            exit()
    

elif h%2==0 and w%2==1:
    for i in range(len(c)):
        if c[i][1]%4==0:
            continue
        
        elif c[i][1]%4==2:
            h-=2
            if h<0:
                print('No')
                exit()
        else:
            print('No')
            exit()

else:
    v=h+w-2
    r=1
    for i in range(len(c)):
        if c[i][1]%4==0:
            continue
        
        elif c[i][1]%4==3:
            v-=2
            r-=1
            if v<0 or r<0:
                print('No')
                exit()
                
        elif c[i][1]%4==2:
            v-=2
            if v<0:
                print('No')
                exit()
        
        else:
            r-=1
            if r<0:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

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

H, W = map(int, readline().split())
a = read().split()
s = []
for i in a:
    s.extend(list(i))

s = Counter(s)
r = [0] * 4
for i in s.values():
    r[i % 4] += 1

if r[1] + r[3] > 1:
    print('No')
    exit()

h = H % 2
w = W % 2

if h and w:
    if not r[1]:
        r[3] -= 1
        r[2] += 1
    if H + W - r[2] * 2 >= 0 and (H + W - 2 - r[2] * 2) % 4 == 0:
        print('Yes')
    else:
        print('No')
else:
    if r[1] + r[3] != 0:
        print('No')
        exit()
    if h:
        if W - r[2] * 2 >= 0 and (W - r[2] * 2) % 4 == 0:
            print('Yes')
        else:
            print('No')
    elif w:
        if H - r[2] * 2 >= 0 and (H - r[2] * 2) % 4 == 0:
            print('Yes')
        else:
            print('No')
    else:
        if r[0] and r.count(0) == 3:
            print('Yes')
        else:
            print('No')

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
d = {}
for i in range(h):
  for c in input():
    if c in d:
      d[c] += 1
    else:
      d[c] = 1
m = ((w + 1)// 2) * ((h + 1) // 2)
ans = "Yes"
if len(d.keys()) > m:
  ans = "No"
oc = 0
fc = 0
for key in d:
  oc += d[key] % 2
  fc += d[key] // 4
if oc > 1 or fc < (w//2) * (h//2):
  ans = "No"
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]

def solve() :
    d = defaultdict(int)
    for y in range(H) :
        for x in range(W) :
            d[a[y][x]] += 1
            
    one = 1 if H % 2 == W % 2 == 1 else 0
    two = 0

    if H % 2 == 1 : two += W // 2
    if W % 2 == 1 : two += H // 2
        
    for v in d.values() :
        if v % 4 == 3 :
            one -= 1
            two -= 1
        elif v % 4 == 2 :
            two -= 1
        elif v % 4 == 1 :
            one -= 1
        
        if one < 0 or two < 0 :
            return 'No'
            
    return 'Yes'
    
print(solve())

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():
    h,w = LI()
    a = [input() for i in range(h)]
    d = defaultdict(lambda : 0)
    for i in a:
        for j in i:
            d[j] += 1
    l = []
    s = deque()
    for i in d.keys():
        if d[i]&1:
            l.append(i)
        elif d[i]&3:
            s.append(i)
    if len(l) > 1:
        print("No")
        return

    if (h&1) and (w&1):
        if not l:
            print("No")
            return
        d[l[0]] -= 1
        if d[l[0]]&3:
            s.append(l[0])
    n = (h>>1)*(w&1)+(w>>1)*(h&1)
    for i in range(n):
        if not s:
            break
        x = s.pop()
        d[x] -= 2
        if d[x]&3:
            s.append(x)
    if not s:
        print("Yes")
        return
    print("No")
    return


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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[chr(i) for i in range(97, 97+26)]
d={i:j for i,j in zip(l,range(26))}
c=[0]*26
for i in range(h):
    s=input()
    for j in s:
        c[d[j]]+=1
if h%2==0 and w%2==0:
    if all([i%4==0 for i in c]):#偶数×偶数のとき、全てが4の倍数でなければならない
        print("Yes")
    else:print("No")
else:
    k=(h//2)*(w//2)
    if h%2==1 and w%2==1:
        if sum([i%2 for i in c])==1:
            if h==1 or w==1:
                print("Yes") 
            elif sum([i//4 for i in c])>=k:
                print("Yes")
            else:print("No")
        else:
            print("No")
    else:
        if sum([i%2 for i in c])==0:
            if h==1 or w==1:
                print("Yes")
            elif sum([i//4 for i in c])>=k:
                print("Yes")
            else:print("No")
        else:print("No")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#n,mの偶奇で場合分け
#n,mがともに偶数の時は全部４の倍数個なきゃダメ
#n,mの片方のみ奇数の時は、例えばnが奇数の時は個数が偶数だが４の倍数でない組みがm//2組みまで許される
#n,mがともに奇数の時は個数が偶数だが４の倍数でない組みが(n+m)//2組み許され、ただ一つ奇数が必要
l=[]
for i in range(n):
  l.append(list(input()))
from collections import defaultdict
d=defaultdict(int)
for i in range(n):
  for j in range(m):
    d[l[i][j]]+=1
b=True
count2=0
count1=0
for i in d:
  if d[i]%4==0:
    pass
  elif d[i]%2==0:
    count2+=1
  else:
    if count1!=0:
      b=False
    else:
      count1=1
if not b:#奇数個あるのが２組以上
  print("No")
else:
  if n%2==0 and m%2==0:
    if count2>0 or count1>0:
      print("No")
    else:
      print("Yes")
  elif n%2==0 and m%2==1:
    if count1>0 or count2>n//2:
      print("No")
    else:
      print("Yes")
  elif n%2==1 and m%2==0:
    if count1>0 or count2>m//2:
      print("No")
    else:
      print("Yes")
  else:
    if (count1-1)%4==2:
      count2+=1
    if count2>(n+m-2)//2:
      print("No")
    else:
      print("Yes")

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


H, W = list(map(int, sys.stdin.buffer.readline().split()))
A = [list(sys.stdin.buffer.readline().decode().rstrip()) for _ in range(H)]

S = []
for a in A:
    S += a
counts = Counter(S)


def solve(counts, H, W):
    if H & 1 and W & 1:
        for c in string.ascii_lowercase:
            if counts[c] & 1:
                counts[c] -= 1
                break
        for c in string.ascii_lowercase:
            if counts[c] & 1:
                return False

        cnt = (H + W - 2) // 2
        for c in string.ascii_lowercase:
            if counts[c] % 4:
                counts[c] -= 2
                cnt -= 1
            if cnt < 0:
                return False

    if H & 1 or W & 1:
        if W & 1:
            H, W = W, H
        assert H & 1 == 1

        cnt = W // 2
        for c in string.ascii_lowercase:
            if counts[c] % 4:
                counts[c] -= 2
                cnt -= 1
            if cnt < 0:
                return False

    for c in string.ascii_lowercase:
        if counts[c] % 4:
            return False
    return True


ok = solve(counts, H, W)
if ok:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int, input().split())

S = ""
for _ in range(H):
    S += input()

# print(S)
character_counter = Counter(S)
# print(character_counter)
g1 = (H % 2) * (W % 2)  # 行と列のどちらかが偶数であれば0
g2 = (W // 2) * (H % 2) + (H // 2) * (W % 2)  # 奇数のときに2つのブロックのペアをもてる
g4 = (H // 2) * (W // 2)
# 
# print(g1*1+g2*2+g4*4)  # この値を使い切る必要がある
# print(g1)
# print(g2)
# print(g4)
# print(character_counter)

character_counter_list = sorted(list(character_counter.values()), reverse=True)
# print(character_counter_list)

# g1を使う
for i in range(len(character_counter_list)):
    if character_counter_list[i] % 2 == 1 and g1 > 0:
        character_counter_list[i] -= 1
        g1 -= 1

# g2を使う
for i in range(len(character_counter_list)):
    if character_counter_list[i] % 4 == 2 and g2 > 0:
        character_counter_list[i] -= 2  # これによってmod4で0になっている
        g2 -= 1

if g2 % 2 == 1:  # g2が奇数個余っていたら終わり
    print("No")
    exit()

# 余ったg2は2つで1個分のg4として使える
g4 += (g2//2)
g2 = 0
# g4を使う
for i in range(len(character_counter_list)):
    if character_counter_list[i] % 4 == 0 and g4 > 0:
        tmp = (character_counter_list[i] // 4)
        character_counter_list[i] -= (4*tmp)  # もし文字の数が8個とかなら、g4を2つ使える
        g4 -= tmp
# print(character_counter_list)
# print(g1)
# print(g2)
# print(g4)

if g1 == 0 and g2 == 0 and g4 == 0 and sum(character_counter_list) == 0:  # 無事に使い切れたらYes
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
l=[chr(i) for i in range(97, 97+26)]
ctl=[0]*26
for i in range(h):
  for j in range(w):
    ctl[l.index(a[i][j])]+=1

if h%2==0 and w%2==0:
  ct1=0;ct2=0;ct4=h*w
elif h%2==1 and w%2==1:
  ct1=1;ct2=h+w-2;ct4=h*w-ct1-ct2
elif h%2==0 and w%2==1:
  ct1=0;ct2=h;ct4=h*w-ct2
else:
  ct1=0;ct2=w;ct4=h*w-ct2
ct2=ct2//2;ct4=ct4//4

for i in range(26):
  while ctl[i]>=4 and ct4!=0:
    ctl[i]-=4
    ct4-=1
  if ct4==0:
    break
if ct4!=0:
  print('No')
  sys.exit()

for i in range(26):
  while ctl[i]>=2 and ct2!=0:
    ctl[i]-=2
    ct2-=1
  if ct2==0:
    break
if ct2!=0:
  print('No')
  sys.exit()

for i in range(26):
  while ctl[i]>=1 and ct1!=0:
    ctl[i]-=1
    ct1-=1
  if ct1==0:
    break
if ct1!=0:
  print('No')
  sys.exit()

print('Yes')

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
C = {}
for i in range(h):
    for c in input():
        C[c] = C.get(c, 0) + 1
if h == 1 or w == 1:
    odd = 0
    for c in C:
        if C[c] % 2 == 1:
            odd += 1
    if h % 2 == 1 and w % 2 == 1:
        if odd == 1:
            print('Yes')
        else:
            print('No')
    else:
        if odd == 0:
            print('Yes')
        else:
            print('No')
else:
    #print(C)
    four = 0
    odd = 0
    for c in C:
        if C[c] % 2 == 1:
            odd += 1
        if C[c] >= 4:
            four += C[c]//4
    needf = (h//2*2) * (w//2*2) // 4
    #print(needf)
    if h % 2 == 1 and w % 2 == 1:
        if four >= needf and odd == 1:
            print('Yes')
        else:
            print('No')
    else:
        if four >= needf and odd == 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()

cA = Counter(A)

if H % 2 == 1 and W % 2 == 1:
  one = 1
  two = H // 2 + W // 2
  four = (H // 2) * (W // 2)
else:
  one = 0
  two = (H * (W % 2) + W * (H % 2)) // 2
  four = (H // 2) * (W // 2)

# print(one, two, four)

vals =[val for val in cA.values()]

# print(vals)

# one
while one > 0:
  for i in range(len(vals)):
    _, m = divmod(vals[i], 4)
    if m == 1 or m == 3:
      vals[i] -= 1
      break # 
  one -= 1

# print(vals)    

# two
if two > 0:
  for i in range(len(vals)):
    _, m = divmod(vals[i], 4)
    if two > 0 and m == 2:
      vals[i] -= 2
      two -= 1
          
# print(vals)

# four
while four > 0:
  for i in range(len(vals)):
    _, m = divmod(vals[i], 4)
    if vals[i] != 0 and m == 0:
      vals[i] -= 4
      break
  four -= 1

# print(vals)      
# print(one, two, four)

# two
while two > 0:
  for i in range(len(vals)):
    _, m = divmod(vals[i], 2)
    if vals[i] != 0 and m == 0:
      vals[i] -= 2
      break
  two -= 1

# print(vals)      
# print(one, two, four)
  
if all([val == 0 for val in vals]):
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

    odd = 0
    even = 0
    if H % 2 and W % 2:
        odd += 1
    if H % 2:
        even += W // 2
    if W % 2:
        even += H // 2

    for key, value in d.items():
        value %= 4
        if value % 2:
            odd -= 1
            value -= 1
        if value == 2:
            even -= 1
        if even < 0 or odd < 0:
            break

    if even < 0 or odd < 0:
        print('No')
    else:
        print('Yes')
        


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
import collections
c=collections.Counter() 
for i in range(h):
    s=input()
    a.append(s)
    for j in s:
        c[j]+=1
l=c.most_common()
if h%2==1:
    n=h-1
else:
    n=h
if w%2==1:
    m=w-1
else:
    m=w
p=n*m
r=(h*w-p)%2
q=(h*w-p)-r

for i,j in l:
    if j>=4 and p>=4:
        tmp=min(j-j%4,p)
        p-=tmp
        j-=tmp
    if j>=2 and q>=2:
        tmp=min(j-j%2,q)
        q-=tmp
        j-=tmp
    if j>=1 and r==1:
        r=0
        j=0
    elif j==1 and r==0:
        print("No")
        exit()
if p+q+r==0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
from collections import Counter
l=[]
for _ in range(h):
    l+=list(input())
c=Counter(l)

if h==1 and w==1:
    print("Yes")
elif h==1:
    two=w//2
    for k,v in c.items():
        c[k]-=2*(v//2)
        two-=v//2
    if two==0:
        print("Yes")
    else:
        print("No")
elif w==1:
    two=h//2
    for k,v in c.items():
        c[k]-=2*(v//2)
        two-=v//2
    if two==0:
        print("Yes")
    else:
        print("No")
else:
    four=((w//2)*(h//2))
    two=0
    if w%2==1 and h%2==1:
        two=(h+w-2)//2
    elif w%2==1:
        two=h//2
    elif h%2==1:
        two=w//2
    for k,v in c.items():
        four-=v//4
        c[k]-=4*(v//4)
        two-=c[k]//2
        c[k]-=2*(c[k]//2)

    if four==0 and two==0:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
from collections import Counter
C = Counter()
h, w = map(int, input().split())
for _ in range(h):
	C += Counter(input())
lim = (h // 2) * (w % 2) + (w // 2) * (h % 2)
cnt = flg = 0
for k, v in C.items():
	while v >= 4:
		v -= 4
	if v >= 2:
		cnt += 1
		if cnt > lim:
			print("No")
			exit()
	if v % 2:
		if flg or h % 2 == w % 2 == 0:
			print("No")
			exit()
		flg = 1
print("Yes")

Submission status: Accepted

Solution code:
import collections
h,w=map(int,input().split())
a=''
for i in range(h):
    a+=str(input())
l=list(a)
r=collections.Counter(l)
rr=list(r.values())
R=[]
x=0;y=0;z=0
for i in rr:
    R.append(i%4)
    if i%4==1 or i%4==3:
        x+=1
    elif i%4==2:
        y+=1
    else:
        z+=1

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

Submission status: Accepted

Solution code:
from collections import Counter
C=Counter()

h,w=map(int,input().split())
for _ in range(h):
	C+=Counter(input())

one=[]
two=[]
four=[]
twolim=(h//2)*(w%2)+(w//2)*(h%2)
twocnt=0
for k,v in C.items():
	while v>=4:
		v-=4
		four.append(k)
	if v>=2:
		twocnt+=1
		if twocnt>twolim:
			print("No")
			exit()
		two.append(k)
	if v%2:
		if one or h%2==w%2==0:
			print("No")
			exit()
		one.append(k)
print("Yes")		
		
"""
ans=[""]*h

for i in range(h//2):
	c=0
	while c<w//2:
		c+=1
		x=four.pop()
		ans[i]+=x
		ans[~i]+=x
	if w%2:
		if two:
			x=two.pop()
			ans[i]+=x
			ans[~i]+=x
		else:
			x=four.pop()
			ans[i]+=x
			ans[~i]+=x
			four.append(x)
if h%2:
	for x in two+four+four+one:
		ans[h//2]+=x
for l in ans:
	print(l+l[:w//2][::-1])
"""

Submission status: Accepted

Solution code:
import sys
from collections import Counter
h, w = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
ct = Counter()
for y in range(h):
    a = [i for i in sys.stdin.readline().strip()]
    a_ls.append(a)
    ct.update(a)
g1 = h % 2 & w % 2
g2 = (h // 2) * (w % 2) + (w // 2) * (h % 2)
g4 = (h // 2) * (w // 2)
cnt = 0
for c in ct.keys():
    if cnt == g1:
        break
    if ct[c] % 2 == 1:
        ct[c] -= 1
        cnt += 1
cnt = 0
for c in ct.keys():
    if cnt == g2:
        break
    if ct[c] % 4 == 2:
        ct[c] -= 2
        cnt += 1
if all([ct[c] % 4 == 0 for c in ct.keys()]):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:

H,W = map(int,input().split())

dic = {}

for i in range(H):

    s =  input()

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

n4 = 0
n2 = 0
n1 = 0

for i in dic:

    n4 += dic[i] // 4
    dic[i] = dic[i] % 4
    n2 += dic[i] // 2
    dic[i] = dic[i] % 2
    n1 += dic[i]


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

    if n2 == 0 and n1 == 0:
        print ("Yes")
    else:
        print ("No")

elif H % 2 == 0 and W % 2 == 1:

    if n1 == 0 and n2 <= H // 2:
        print ("Yes")
    else:
        print ("No")

elif H % 2 == 1 and W % 2 == 0:

    if n1 == 0 and n2 <= W // 2:
        print ("Yes")
    else:
        print ("No")

else:

    if n1 <= 1 and n2 <= H // 2 + W // 2:
        print ("Yes")
    else:
        print ("No")

Submission status: Accepted

Solution code:
alpha2num = lambda c: ord(c) - ord('a') + 1
c = [0] * 27

h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        c[alpha2num(s[i][j])] += 1

if h % 2 == 0 and w % 2 == 0:
    flag = 1
elif h % 2 == 0 and w % 2 == 1:
    flag = 2
elif h % 2 == 1 and w % 2 == 0:
    flag = 3
elif h % 2 == 1 and w % 2 == 1:
    flag = 4


#print(c)
c1 = 0
c2 = 0
for i in range(len(c)):
    if c[i] % 4 == 1:
        c1 += 1
    elif c[i] % 4 == 2:
        c2 += 1
    elif c[i] % 4 == 3:
        c1 += 1
        c2 += 1

#print(c1, c2)

ans = 'No'
if flag == 1:
    if c1 == c2 == 0:
        ans = 'Yes'
elif flag == 2:
    if c1 == 0 and c2 <= h//2:
        ans = 'Yes'
elif flag == 3:
    if c1 == 0 and c2 <= w//2:
        ans = 'Yes'  
else:
    if c1 == 1 and c2 <= h//2 + w//2:
        ans = 'Yes'

print(ans)

Submission status: Accepted

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


def main():
    h, w = map(int, input().split())
    alpha = [0 for _ in range(26)]

    # 各アルファベットの個数を数える
    for i in range(h):
        ai = list(input())

        for aii in ai:
            # アルファベットを数値に変換
            index = ord(aii) - ord('a')
            alpha[index] += 1

    mod = [0 for _ in range(4)]

    for a in alpha:
        mod[a % 4] += 1

    # 回文となる条件
    # 1. hとwがともに偶数：
    # アルファベットの個数が全て4の倍数のとき，Yes
    # 2. hとwのどちらかが偶数：
    # アルファベットの個数が全て2の倍数のとき，Yes
    # 3. hとwがともに奇数：
    # (h - 1) * (w - 1)マス分，アルファベットの個数が4の倍数であり，
    # かつ，1種類を除いて，2の倍数のとき，Yes
    if h % 2 == 0 and w % 2 == 0:
        for a in alpha:
            if a % 4 != 0:
                print('No')
                exit()

        print('Yes')
    elif h % 2 == 1 and w % 2 == 1:
        # 気がつけなかった点
        # 4で割ったときに2余る数が使われるのが，(h - 1) // 2 + (w - 1) // 2以下
        # See:
        # https://www.hamayanhamayan.com/entry/2017/09/24/012523
        if mod[3]:
            print('No')
        elif mod[1] != 1:
            print('No')
        elif mod[2] > ((h - 1) // 2 + (w - 1) // 2):
            print('No')
        else:
            print('Yes')
    else:
        if w % 2 == 1:
            h, w = w, h

        # 気がつけなかった点
        if mod[3] or mod[1]:
            print('No')
        elif mod[2] > w // 2:
            print('No')
        else:
            print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
counts = {}
for a_ in A:
  for a in a_:
    if not a in counts:
      counts[a] = 1
    else:
      counts[a] += 1
ans = "Yes"
oe = H%2+W%2
mod1 = 1 if oe == 2 else 0
mod2 = (H//2)*(W%2)+(W//2)*(H%2)
mod4 = (H//2)*(W//2)
for _ in range(mod1):
  for c in counts.keys():
    if counts[c] % 4 == 1:
      counts[c] -= 1
      break
for _ in range(mod2):
  for c in counts.keys():
    if counts[c] % 4 == 2:
      counts[c] -= 2
      mod2 -= 1
      break
if mod2 % 2 == 0:
  mod4 += mod2//2
  for _ in range(mod4):
    for c in counts.keys():
      if counts[c] % 4 == 0 and counts[c] > 0:
      	counts[c] -= 4
      	break
  for n in counts.values():
    if n > 0:
      ans = "No"
      break
else:
  ans = "No"
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
counts = {}
for a_ in A:
  for a in a_:
    if not a in counts:
      counts[a] = 1
    else:
      counts[a] += 1
ans = "Yes"
oe = H%2+W%2
if oe == 0:
  for n in counts.values():
    if n % 4 != 0:
      ans = "No"
      break
elif oe == 1:
  even = H if H % 2 == 0 else W
  modis2 = 0
  for n in counts.values():
    if n % 4 == 2:
      modis2 += 1
      if modis2 > even / 2:
        ans = "No"
        break
    elif n % 4 != 0:
      ans = "No"
      break
else:
  if H == 1 or W == 1:
    oddcount = 0
    for n in counts.values():
      if n % 2 == 1:
        oddcount += 1
        if oddcount > 2:
          ans = "No"
          break
  else:
    modcount = [0] * 4
    for n in counts.values():
      modcount[n%4] += 1
    if modcount[1]+modcount[3] == 1 and modcount[2] + modcount[3] == (H//2)+(W//2):
      ans = "Yes"
    else:
      ans = "No"
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from collections import defaultdict, Counter

def main():
    h, w = map(int, input().strip().split())
    mat = [0] * h
    d = {}
    for i in range(h):
        s = input().strip()
        for k, v in dict(Counter(s)).items():
            if k in d:
                d[k] += v
            else:
                d[k] = v
    num = [0] * 4
    for k, v in d.items():
        num[v % 4] += 1

    ans = "No"
    if h % 2 == 1 and w % 2 == 1:
        if num[1] + num[3] == 1 and num[2] <= h // 2 + w // 2:
            ans = "Yes"
    elif h % 2 == 1:
        if num[1] + num[3] == 0 and num[2] <= w // 2:
            ans = "Yes"
    elif w % 2 == 1:
        if num[1] + num[3] == 0 and num[2] <= h // 2:
            ans = "Yes"
    else:
        if num[1] + num[3] + num[2] == 0:
            ans = 'Yes'
    print(ans)
    # print(num)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
dct=defaultdict(int)
dct2=defaultdict(int)

h,w=map(int,input().split())
for i in range(h):
  s=input()
  for j in range(w):
    dct[s[j]]+=1


for k,v in dct.items():
  dct2[4]+=v//4
  dct2[2]+=v//2-2*(v//4)
  dct2[1]+=v%2


f=0

if h%2==0 and w%2==0:
  if dct2[1]==dct2[2]==0:
    f=1
elif h%2==1 and w%2==1:
  if dct2[1]==1 and dct2[4]>=((h-1)*(w-1))//4:
    f=1
elif h%2==1:
  if dct2[1]==0 and dct2[4]>=((h-1)*(w))//4:
    f=1
else:
  if dct2[1]==0 and dct2[4]>=((w-1)*(h))//4:
    f=1

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
dic = {}
for h in range(H):
  s = list(input())
  for x in s:
    dic[x] = dic.get(x,0) + 1

c1 = 0
c2 = 0
for x in dic.values():
  if x%2 == 1:
    c1 += 1
    x -= 1
  if x%4 == 2:
    c2 += 1
if c1>(H%2)*(W%2):
  print("No")
elif c2>((W*(H%2))//2)+((H*(W%2))//2):
  print("No")
else:
  print("Yes")

Submission status: Accepted

Solution code:
H,W = [int(x) for x in input().split()]
A = [input() for _ in range(H)]
char_cnts = [0]*26
for a in A:
    for c in a:
        char_cnts[ord(c)-97] += 1
if(H==1 or W==1):
    num_cnt1 = 0
    for i in char_cnts:
        if(i%2==1):
            num_cnt1 += 1
        if(num_cnt1>1):
            print('No')
            break
    else:
        print('Yes')

elif(H==2 and W==2):
    for i in char_cnts:
        if(i%4!=0):
            print('No')
            break
    else:
        print('Yes')
elif(H==2 or W==2):
    for i in char_cnts:
        if(i%2!=0):
            print('No')
            break
    else:
        print('Yes')
else:
    cnt = (H//2)*(W//2)
    for i in char_cnts:
        cnt -= i//4
        if(cnt<=0):
            print('Yes')
            break
    else:
        print('No')