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:
import collections as c
import sys
H, W = map(int, input().split())
A = (sys.stdin.read()).replace('\n', '')
deck = c.Counter(list(map(str, A)))

is_Hodd = H%2
is_Wodd = W%2

count = list(deck.values())
if is_Hodd and is_Wodd:
	one = 1
	two = H//2 + W//2
	four = (H//2) * (W//2)

	for i in range(len(count)):
		if count[i] >= 4*four:
			count[i] -= 4*four
			four = 0
			break
		else:
			tmp = count[i]//4
			count[i] -= 4*tmp
			four -= tmp
			
	for i in range(len(count)):
		if count[i] >= 2*two:
			count[i] -= 2*two
			two = 0
			break
		else:
			tmp = count[i]//2
			count[i] -= 2*tmp
			two -= tmp

	for i in range(len(count)):
		if count[i] > 0:
			count[i] -= 1
			one = 0

	if four == 0 and two == 0 and one == 0:
		cond = 1
	else:
		cond = 0

elif is_Hodd or is_Wodd:
	if is_Hodd:
		two = W//2
	else:
		two = H//2

	four = (H//2) * (W//2)

	for i in range(len(count)):
		if count[i] >= 4*four:
			count[i] -= 4*four
			four = 0
			break
		else:
			tmp = count[i]//4
			count[i] -= 4*tmp
			four -= tmp
			
	for i in range(len(count)):
		if count[i] >= 2*two:
			count[i] -= 2*two
			two = 0
			break
		else:
			tmp = count[i]//2
			count[i] -= 2*tmp
			two -= tmp

	if four == 0 and two == 0:
		cond = 1
	else:
		cond = 0

else:
	four = (H//2) * (W//2)

	for i in range(len(count)):
		if count[i] >= 4*four:
			count[i] -= 4*four
			four = 0
			break
		else:
			tmp = count[i]//4
			count[i] -= 4*tmp
			four -= tmp

	if four == 0:
		cond = 1
	else:
		cond = 0

if cond:
	print('Yes')
else:
	print('No')

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter()
for h in range(H):
    c.update(input())

demand2 = W % 2 * (H // 2) + H % 2 * (W // 2)
demand4 = (H // 2) * (W // 2)

supply2 = supply4 = 0
for x in c.values():
    supply4 += x // 4
    supply2 += x % 4 // 2

yes = False
if supply4 >= demand4:
    supply2 += (supply4 - demand4) * 2
    if supply2 >= demand2:
        yes = True

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

Submission status: Accepted

Solution code:
from collections import Counter
h,w=map(int,input().split())
cnt=Counter()
for i in range(h):
  c=Counter(input())
  cnt+=c
sum1=0
sum2=0
sum4=0
for i in cnt.values():
  sum1+=i%2
  sum4+=i//4
  sum2+=(i-(i//4)*4)//2
if h%2==0 and w%2==0:
  print('Yes' if sum1==0 and sum2==0 else 'No')
elif h%2==1 and w%2==1:
  print('Yes' if sum1==1 and sum4>=((w-1)*(h-1))/4 else 'No')
elif h%2==1 and w%2==0:
  print('Yes' if sum1==0 and sum2<=w/2 else 'No')
else:
  print('Yes' if sum1==0 and sum2<=h/2 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter
h, w = map(int, input().split())
a = ''
for i in range(h):
    a += input()
c = Counter(a).values()
m1 ,m2 = 0, 0
for i in c:
    if i%2:
        m1 += 1
    elif i%4 == 2:
        m2 += 1
g1 = h%2 * w%2
g2 = h%2*(w//2) + w%2*(h//2)
# g4 = w//2 * h//2
if m1 <= g1 and m2 <= g2:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)


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



H, W = acinput()

# d=[0]*26
d = {}

for i in range(H):

    tmp = list(input())
    for c in tmp:
        try:
            d[c] += 1
        except:
            d[c] = 1
mod2 = mod4 = 0

mod1=0
for k in d:
    if d[k] % 4 == 0:
        mod4 += 1
    elif d[k] % 2 == 0:
        mod2 += 1
    elif d[k]%2==1:
        mod1+=1


am=H%2
bm=W%2

A1=0

if am==0 and bm==0:
    resid4 = np.floor((H)*(W))-mod4
    A2=0
elif am==0 and bm==1:
    resid2 = np.floor(W-1)-mod2
    resid4 = np.floor((H-1)*(W))-mod4
    A2=H//2
elif am==1 and bm==0:
    resid2 = np.floor(W-1)-mod2    
    resid4=np.floor((H-1)*(W))-mod4
    A2=W//2
else:
    resid2 = np.floor(W-1)+H-1-mod2
    resid4 = np.floor((H-1)*(W-1))-mod4
    A2=(W+H-2)//2
    A1=1

#print(resid4,mod2)

res = False

#print(A2,mod2)
if A2>=mod2 and A1>=mod1:
    res=True

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def get_n(a_c):
	return ord(a_c)-ord('a')

def main():
	h,w  = IN()
	dd=[0]*(get_n('z')+1)
	for _ in range(h):
		s = input()
		for c in s:
			v=get_n(c)
			dd[v] += 1
			
	pa(dd)
	mmmd=[0]*4
	for v in dd:
		mmmd[v%4]+=1
	
	pa(mmmd)
	th_1_3=(h%2)*(w%2)
	th_2=(h%2)*(w//2)+(w%2)*(h//2)
	pa(th_2)
	if mmmd[1]+mmmd[3] > th_1_3:
		return 'No'
	if mmmd[2] > th_2:
		return 'No'
	return 'Yes'
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w = inpm()
    a = inplT(h)
    dic = defaultdict(int)
    for i in range(h):
        for j in range(w):
            x = ord(a[i][j])
            dic[x] += 1
    aaa = 0
    q = 0
    for e in dic:
        if dic[e] != 1 and dic[e]%2 == 1:
            aaa += 1
            q = dic[e]
            if aaa == 2:
                print('No')
                return
    if h%2 == 0 and w%2 == 0:
        for e in dic:
            if dic[e]%4 != 0:
                print('No')
                return
    if (h%2 == 0 and w%2 == 1) or (h%2 == 1 and w%2 == 0):
        cnt = 0
        if aaa:
            print('No')
            return
        else:
            for e in dic:
                if dic[e]%2 != 0:
                    print('No')
                    return
                if dic[e]%4 == 2:
                    cnt += 1
            if h%2 == 0:
                key = h//2
            else:
                key = w//2
            if (key-cnt) < 0 or (key-cnt)%2 != 0:
                print('No')
                return
    if h%2 == 1 and w%2 == 1:
        cnt1 = 0
        cnt2 = 0
        if aaa:
            for e in dic:
                if dic[e]%2 == 1:
                    cnt1 += 1
                elif dic[e]%4 == 2:
                    cnt2 += 1
            if cnt1 != 1:
                print('No')
                return
            key = (h//2) + (w//2)
            if (key-cnt2) < 0 or (key-cnt2)%2 != 0:
                print('No')
                return
        else:
            for e in dic:
                if dic[e] == 1:
                    cnt1 += 1
                elif dic[e]%4 == 2:
                    cnt2 += 1
            if cnt1 != 1:
                print('No')
                return
            q -= 1
            if q%4 == 2:
                cnt2 += 1
            key = (h//2) + (w//2)
            if (key-cnt2) < 0 or (key-cnt2)%2 != 0:
                print('No')
                return
    print('Yes')

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter 

a,b = map(int,input().split())
l = ''
for i in range(a):
    t = input()
    l+=t
c = Counter(list(l))
dp = [0,0,0]
for i in c:
    if c[i]%2 ==1:
        dp[0] +=1
    elif c[i]%4 == 0:
        dp[2] += 1
    elif c[i]%2 == 0:
        dp[1] += 1
ans = 'No'
A = 0
if a%2 ==1 and b%2 ==1:
    A = 1
    B = (a+b-2)//2
elif  a%2 ==0 and b%2 ==0:
    B= 0
elif a%2 ==0 and b%2 ==1:
    B = a//2
else:
    B= b//2
if A >= dp[0] and B >= dp[1]:
    ans = 'Yes'
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter 

a,b = map(int,input().split())
l = ''
for i in range(a):
    t = input()
    l+=t

c = Counter(list(l))
# print(c)
dp = [0,0,0]
for i in c:
    if c[i]%2 ==1:
        dp[0] +=1
    elif c[i]%4 == 0:
        dp[2] += 1
    elif c[i]%2 == 0:
        dp[1] += 1
# print(dp)
ans = 'No'
if a%2 ==1 and b%2 ==1:
    A = 1
    B = (a+b-2)//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
elif  a%2 ==0 and b%2 ==0:
    A = 0
    B= 0
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
elif a%2 ==0 and b%2 ==1:
    A = 0
    B = a//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
else:
    A=0
    B= b//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

need = [0] * 3  # need[x]:=2**x個重複している要素の必要数
if h % 2 == 0:
    if w % 2 == 0:
        need[2] = h * w
    else:
        need[2] = h * w - h
        need[1] = h
else:
    if w % 2 == 0:
        need[2] = h * w - w
        need[1] = w
    else:
        need[2] = h * w - (h + w - 1)
        need[1] = h + w - 2
        need[0] = 1

for power in range(2, -1, -1):
    for char in ctr:
        if not need[power]:
            break
        p2 = pow(2, power)
        while ctr[char] >= p2:
            ctr[char] -= p2
            need[power] -= p2

if any(p > 0 for p in need):
    print('No')
else:
    print('Yes')

# ee
# 4: h*w

# eo, even=h
# 2: h
# 4: h*w - h

# oo
# 1: 1
# 2: h+w-1
# 4: h*w-(h+w)

Submission status: Accepted

Solution code:

from collections import defaultdict

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

# Aが一文字だけの場合
if H == 1 and W == 1:
    print("Yes")
    exit()

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

# 普通の回分の場合
if H == 1 or W == 1:
    # 文字列が偶数個の場合は、それぞれの文字が偶数回出現していればOK
    if H % 2 == 0 or W % 2 == 0:
        f = True
        for i in d.values():
            if i % 2 != 0:
                f = False
        print("Yes" if f else "No")
    # 文字列が奇数個の場合、一つだけ奇数個の文字がある
    else:
        cnt_odd = 0
        for i in d.values():
            if i % 2 != 0:
                cnt_odd += 1
        print("Yes" if cnt_odd == 1 else "No")
# 行列の回分の場合
# 奇数×奇数のとき、行列の縦と横の真ん中の線の交点に来る文字は奇数個でOK。交点以外の真ん中のライン上の文字は２の倍数個いる。それ以外の位置は４の倍数個いる。
# 奇数×偶数でもおんなじ感じ
# 偶数×偶数は全部４の倍数個ずつ必要
else:
    #
    cnt_m1 = 0
    cnt_m2 = 0
    cnt_m3 = 0
    for i in d.values():
        if i % 4 == 1:
            cnt_m1 += 1
        elif i % 4 == 2:
            cnt_m2 += 1
        elif i % 4 == 3:
            cnt_m3 += 1
            
    f = True
    if H % 2 == 1 and W % 2 == 1:
        if cnt_m1 + cnt_m3 != 1:
            f = False
        if cnt_m2 + cnt_m3 > (H-1)//2 + (W-1)//2:
            f = False

    elif H % 2 == 1 or W % 2 == 1:
        if cnt_m1 != 0:
            f = False
        if H % 2 == 1:
            if cnt_m2 > (W//2):
                f = False
        else:
            if cnt_m2 > (H//2):
                f = False
        if cnt_m3 != 0:
            f = False
    else:
        if cnt_m1 != 0:
            f = False
        if cnt_m2 != 0:
            f = False
        if cnt_m3 != 0:
            f = False

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    cnt = [0]*26
    for _ in range(H):
        for s in ST():
            cnt[ord(s)-ord("a")] += 1
    
    cnt_cnt = defaultdict(int)
    for c in cnt:
        cnt_cnt[c%4] += 1


    #2個セットのは,2ペア集めると4の倍数個ある文字を採用することが出来るのでそれを考慮する

    if H%2==0 and W%2==0: #even even
        if cnt_cnt[0]==26:
            print("Yes")
        else:
            print("No")
    elif H&1 and W&1: #odd odd
        flag1 = (cnt_cnt[1]+cnt_cnt[3]==1)
        cnt_cnt[2]+=cnt_cnt[3] ## 3のやつは真ん中に一つと2個ペアに2つ使う
        flag2 = (cnt_cnt[2]%2==((H//2)+(W//2))%2 and cnt_cnt[2]<=(H//2)+(W//2))
        if flag2 and flag1:
            print("Yes")
        else:
            print("No")
    else: #others
        if cnt_cnt[1] or cnt_cnt[3]:
            print("No")
            return
        if H&1:
            if cnt_cnt[2]%2==(W//2)%2 and cnt_cnt[2]<=(W//2):
                print("Yes")
            else:
                print("No")
        else:
            if (cnt_cnt[2])%2==(H//2)%2 and (cnt_cnt[2])<=(H//2):
                print("Yes")
            else:

                print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
H,W=map(int,input().split())
A=[]
for _ in range(H):
    A+=list(input())

#基本的に4個ずつないとダメ
#行数・列数が奇数の場合、真ん中の行・列は2個ずつでよい
#行数・列数が両方とも奇数の場合、全体の中心は1個でよい

C=Counter(A)
g4=0
g2=0
g1=0
for n in C.values():
    g4+=n//4
    g2+=(n%4)//2
    g1+=(n%4)%2

ans='No'
if (g1==1 and H&1 and W&1) or g1==0:
    if g4 >= (H//2)*(W//2):
        if (g2 + (g4 - (H//2)*(W//2))*2) == (H//2 if W&1 else 0) + (W//2 if H&1 else 0):
            ans='Yes'
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
char = [0 for _ in range(26)]
rem = [0,0,0,0]

for i in range(H):
    a = input()
    for j in range(W):
        char[ord(a[j])-97] += 1

for i in range(26):
    rem[char[i]%4] += 1
    
if H%2==0 and W%2==0:
    print('Yes' if rem[0]==26 else 'No')
    
elif H%2!=0 and W%2!=0:
    print('Yes' if rem[1]+rem[3]==1 and rem[2]+rem[3]<=(H-1)//2+(W-1)//2 else 'No')
    
else:
    print('Yes' if rem[1]+rem[3]==0 and rem[2]<=(H%2)*(W//2)+(W%2)*(H//2) else 'No')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
X = [0] * 26
for _ in range(H):
    for a in input():
        X[ord(a)-97] += 1

Y = [0] * 2 # 1, 2
for x in X:
    if x%4 == 1:
        Y[0] += 1
    elif x%4 == 2:
        Y[1] += 1
    elif x%4 == 3:
        Y[0] += 1
        Y[1] += 1

if Y[0] <= (H%2) * (W%2) and Y[1] <= (H%2) * (W//2) + (W%2) * (H//2):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
h,w=map(int,input().split())
graph=[[]*w for i in range(h)]
for i in range(h):
  graph[i]=list(input())
A=0
B=0
C=0
D=0
E=0
F=0
G=0
H=0
I=0
J=0
K=0
L=0
M=0
N=0
O=0
P=0
Q=0
R=0
S=0
T=0
U=0
V=0
W=0
X=0
Y=0
Z=0
for i in range(h):
  A=A+graph[i].count("a")
for i in range(h):
  B=B+graph[i].count("b")
for i in range(h):
  C=C+graph[i].count("c")
for i in range(h):
  D=D+graph[i].count("d")
for i in range(h):
  E=E+graph[i].count("e")
for i in range(h):
  F=F+graph[i].count("f")
for i in range(h):
  G=G+graph[i].count("g")
for i in range(h):
  H=H+graph[i].count("h")
for i in range(h):
  I=I+graph[i].count("i")
for i in range(h):
  J=J+graph[i].count("j")
for i in range(h):
  K=K+graph[i].count("k")
for i in range(h):
  L=L+graph[i].count("l")
for i in range(h):
  M=M+graph[i].count("m")
for i in range(h):
  N=N+graph[i].count("n")
for i in range(h):
  O=O+graph[i].count("o")
for i in range(h):
  P=P+graph[i].count("p")
for i in range(h):
  Q=Q+graph[i].count("q")
for i in range(h):
  R=R+graph[i].count("r")
for i in range(h):
  S=S+graph[i].count("s")
for i in range(h):
  T=T+graph[i].count("t")
for i in range(h):
  U=U+graph[i].count("u")
for i in range(h):
  V=V+graph[i].count("v")
for i in range(h):
  W=W+graph[i].count("w")
for i in range(h):
  X=X+graph[i].count("x")
for i in range(h):
  Y=Y+graph[i].count("y")
for i in range(h):
  Z=Z+graph[i].count("z")
List=[A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z]
if w%2==0 and h%2==0:
  for i in range(26):
    if List[i]%4==0:
      if i==25:
        print("Yes")
    else:
      print("No")
      sys.exit()
elif w%2==0 :
  a_2=0
  a_4=0
  for i in range(26):
    if List[i]%4==1 or List[i]%4==3:
      print("No")
      sys.exit()
    elif List[i]%4==0:
      a_4=a_4+1
    else:
      a_2=a_2+1
  if a_2%2==(w//2)%2 and a_2<=(w//2):
    print("Yes")
  else:
    print("No")
elif h%2==0 :
  a_2=0
  a_4=0
  for i in range(26):
    if List[i]%4==1 or List[i]%4==3:
      print("No")
      sys.exit()
    elif List[i]%4==0:
      a_4=a_4+1
    else:
      a_2=a_2+1
  if a_2%2==(h//2)%2 and a_2<=(h//2):
    print("Yes")
  else:
    print("No")
else:
  a_1=0
  a_2=0
  a_3=0
  a_4=0
  for i in range(26):
    if List[i]%4==1:
      a1=List[i]
      a_1=a_1+1
      if a_1==2:
        print("No")
        sys.exit()
    elif List[i]%4==2:
      a_2=a_2+1
    elif List[i]%4==3:
      a3=List[i]
      a_3=a_3+1
      if a_3==2:
        print("No")
        sys.exit()
    else:
      a_4=a_4+1
  if a_1==1 and a_3==0:
    if a_2%2==(((h-1)//2)+((w-1)//2))%2 and a_2<=((h-1)//2)+((w-1)//2)-max(0,2*(((a1-1)//4)-(((h-1)//2)*((w-1)//2)))):
      print("Yes")
    else:
      print("No")
  elif a_1==0 and a_3==1:
    if a_2%2==(((h-1)//2)+((w-1)//2)+1)%2 and a_2<=((h-1)//2)+((w-1)//2)-1-max(0,2*(((a3-3)//4)-(((h-1)//2)*((w-1)//2)))):
      print("Yes")
    else:
      print("No")
  else:
    print("No")

Submission status: Accepted

Solution code:
from collections import Counter

H,W=map(int,input().split())
a=[]
for i in range(H):
    a.extend(input())

v=list(Counter(a).values())
# print(v) #DB

f=True
if H%2==0 and W%2==0:    
    for e in v:
        if e%4!=0:
            f=False
            break
elif H%2==0 and W%2==1:
    q=0
    for e in v:
        if e%2!=0:
            f=False
            break
        elif e%4!=0:
            q+=1
            if q>H//2:
                f=False
                break
elif H%2==1 and W%2==0:
    q=0
    for e in v:
        if e%2!=0:
            f=False
            break
        elif e%4!=0:
            q+=1
            if q>W//2:
                f=False
                break
elif H%2==1 and W%2==1:
    p,q=0,0
    for e in v:
        if e%4==1:
            p+=1
            if p>1:
                f=False
                break
        elif e%4==3:
            f=False
            break
        elif e%4!=0:
            q+=1
            if q>(H-1)//2+(W-1)//2:
                f=False
                break
    if p==0:
        f=False

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

Submission status: Accepted

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

if H > W:
    H, W = W, H

count = [0] * 26
for i in a:
    for j in i:
        count[ord(j) - ord('a')] += 1

# print (count)
lst = [0] * 5
for c in count:
    lst[4] += c // 4
    c %= 4
    lst[2] += c // 2
    c %= 2
    lst[1] += c

# print (lst)
flag = False
if H >= 2 and W >= 2:
    if (H // 2) * (W // 2) <= lst[4]:
        lst[2] += (lst[4] - (H // 2) * (W // 2)) * 2 
        # print ('A')
        # print (lst)
        if ((H % 2) * (W // 2)) + ((W % 2) * (H // 2)) == lst[2] and (H % 2) * (W % 2) == lst[1]:
            flag = True
            # print ('B')

if H == 1 and W % 2 == 0:
    if lst[1] == 0:
        flag = True
if H == 1 and W % 2 == 1:
    if lst[1] == 1:
        flag = True

if flag:
    print ('Yes')
else:
    print ('No')

Submission status: Accepted

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

def check(n4, n2):

  for i in range(27):
    if n4 == 0:
      break
    while alpha[i] >= 4:
      alpha[i] -= 4
      n4 -= 1
      if n4 == 0:
        break

  for i in range(27):
    if n2 == 0:
      break
    while alpha[i] >= 2:
      alpha[i] -= 2
      n2 -= 1
      if n2 == 0:
        break
      
  if n4 == 0 and n2 == 0:
    print("Yes")
  else:
    print("No")      

alpha = [0] * 27
for i in range(H):
  for j in range(W):
    alpha[ord(A[i][j]) - ord("a")] += 1

if H % 2 and W % 2:
  n4 = (H * W - (H + W) + 1) // 4
  n2 = (H + W - 2) // 2
elif H % 2 == 0 and W % 2 == 0:
  n4 = H * W // 4
  n2 = 0
else:
  if H % 2:
    H, W = W, H
  n4 = (W - 1) * H // 4
  n2 = H // 2
check(n4, n2)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
str_array = [input() for i in range(h)]
count = [0 for i in range(26)]
for i in range(h):
    for j in range(w):
        count[ord(str_array[i][j]) - ord('a')] += 1

flag = True
count_odd = 0
count_two = 0
if h == 1 and w == 1:
    # 必ずよい
    pass
elif h == 1 or w == 1:
    # 奇数が1種類のみあればいい
    for i in range(26):
        if count[i] % 2 != 0:
            count_odd += 1
            if count_odd > 1:
                flag = False
elif h % 2 == 0 and w % 2 == 0:
    # 全て4の倍数であればよい
    for i in range(26):
        if count[i] % 4 != 0:
            flag = False
elif h % 2 != 0 and w % 2 != 0:
    for i in range(26):
        if count[i] % 2 != 0:
            count_odd += 1
            if count_odd > 1:
                flag = False
        elif count[i] % 4 != 0:
            count_two += 2
            if count_two > h + w - 2:
                flag = False
elif h % 2 != 0:
    for i in range(26):
        if count[i] % 2 != 0:
            flag = False
        elif count[i] % 4 != 0:
            count_two += 2
            if count_two > w:
                flag = False
elif w % 2 != 0:
    for i in range(26):
        if count[i] % 2 != 0:
            flag = False
        elif count[i] % 4 != 0:
            count_two += 2
            if count_two > h:
                flag = False

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

H, W = rl()
l = []
for _ in range(H):
    l.extend(list(rs()))

c = Counter(l)
count = W//2 * H
pair = 0
four = 0
for x in c.values():
    four += x // 4
    pair += x // 2

f = H // 2 * (W // 2)
if f > four:
    print('No')
    exit()

pair -= f * 2 #残りのペア
p = W // 2 if H&1 else 0
p += H // 2 if W&1 else 0
if p > pair:
    print('No')
    exit()

print('Yes')
# 16

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
table = [0] * 26
a = ord("a")
for _ in range(H):
  s = list(input())[: -1]
  for j in range(W):
    table[ord(s[j]) - a] += 1
#print(table)
t = []
for i in range(26):
  if table[i] > 0: t.append(table[i])

x = 0
y = 0
c = 0
if H % 2 and (W % 2):
  c = 1
if H % 2: y += (W - c) // 2
if W % 2: x += (H - c) // 2
#print(x, y, c)
if H > 1 and (W > 1):
  for p in t:
    if p % 2:
      if c > 0:
        c -= 1
        p -= 1
      else:
        print("No")
        exit(0)
    if p % 4:
      if x > 0:
        x -= 1
      elif y > 0:
        y -= 1
      else:
        print("No")
        exit(0)
else:
  for p in t:
    if p % 2:
      if c > 0:
        c -= 1
      else:
        print("No")
        exit(0)
print("Yes")

Submission status: Accepted

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

for i in range(H):
    a.extend(list(input()))

b=[0]*26
abc="abcdefghijklmnopqrstuvwxyz"

for i in a:
    b[abc.index(i)]+=1

if max(b)==H*W:
    print("Yes")
    exit()


num_odd=0
num_4=0
num_2=0

for i in range(26):
    if b[i]%4!=0:
        if b[i]%2==1:
            if num_odd!=0:
                print("No")
                exit()
            else:
                num_odd=b[i]
        else:
            num_4+=4*(b[i]//4)
            num_2+=b[i]%4
    else:
        num_4+=b[i]

if H%2==0 and W%2==0:
    if num_odd!=0 or num_2!=0:
        print("No")
    else:
        print("Yes")
elif H%2==1 and W%2==0:
    if num_4-(H-1)*W>=0 and num_4-(H-1)*W+num_2==W:
        print("Yes")
    else:
        print("No")
elif H%2==0 and W%2==1:
    if num_4-(W-1)*H>=0 and num_4-(W-1)*H+num_2==H:
        print("Yes")
    else:
        print("No")
elif H%2==1 and W%2==1:
    if num_4+4*(num_odd//4)>=(H-1)*(W-1):
        print("Yes")
    else:print("No")

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict


def main():
    h, w = map(int, input().split())

    d = defaultdict(int)
    for _ in range(h):
        for i in input():
            d[i] -= 1
    char = list(d.values())
    heapq.heapify(char)

    hd, hm = divmod(h, 2)
    wd, wm = divmod(w, 2)
    pair = [-2] * hd + [-1] * hm
    pair = [i * 2 for i in pair]*wd + pair*wm
    heapq.heapify(pair)

    while char:
        tmp = heapq.heappop(char) - heapq.heappop(pair)
        if tmp > 0:
            return "No"
        if tmp == 0:
            continue
        heapq.heappush(char, tmp)
    return "Yes"


if __name__ == "__main__":
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = {chr(i):0 for i in range(97,123)}
for _ in range(H):
    s = input().strip()
    for j in range(W):
        C[s[j]] += 1
ind1 = 0
for i in range(97,123):
    if C[chr(i)]==1:
        ind1 = C[chr(i)]
D = {0:0, 1:0, 2:0,3:0}
D1 = {0:0,1:0,2:0,3:0}
for c in C:
    D[C[c]%4] += 1
    D1[C[c]%4] += C[c]
if H%2==0 and W%2==0:
    if D[1]==0 and D[2]==0 and D[3]==0:
        flag = "Yes"
    else:
        flag = "No"
elif H%2==0 and W%2==1:
    if D[1]+D[3]>0:
        flag = "No"
    else:
        m = H//2
        if m>=D[2]:
            flag = "Yes"
        else:
            flag = "No"
elif H%2==1 and W%2==0:
    if D[1]+D[3]>0:
        flag = "No"
    else:
        m = W//2
        if m>=D[2]:
            flag = "Yes"
        else:
            flag = "No"
else:
    if D[1]+D[3]!=1:
        flag = "No"
    else:
        m = (H+W-1)//2
        if m>=D[2]:
            flag = "Yes"
        else:
            flag = "No"
print(flag)

Submission status: Accepted

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


def f(A, n):
    A.sort()
    if A[-1] >= n:
        A[-1] -= n
    else:
        print("No")
        exit()


def main():
    H, W = map(int, input().split())
    import collections
    D = collections.defaultdict(int)
    for _ in range(H):
        s = input().strip()
        for c in s:
            D[c] += 1
    A = list(D.values())

    for i in range(H//2):
        for j in range(W//2):
            f(A, 4)
    if H % 2 == 1:
        for j in range(W//2):
            f(A, 2)
    if W % 2 == 1:
        for i in range(H//2):
            f(A, 2)
    if W % 2 == 1 and H % 2 == 1:
        f(A, 1)

    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
char = [0 for _ in range(26)]
rem = [0,0,0,0]

for i in range(H):
    a = input()
    for j in range(W):
        char[ord(a[j])-97] += 1

for i in range(26):
    rem[char[i]%4] += 1
    
if H%2==0 and W%2==0:
    print('Yes' if rem[0]==26 else 'No')
    
elif H%2!=0 and W%2!=0:
    print('Yes' if rem[1]+rem[3]==1 and rem[2]+rem[3]<=(H-1)//2+(W-1)//2 else 'No')
    
else:
    print('Yes' if rem[1]+rem[3]==0 and rem[2]<=(H%2)*(W//2)+(W%2)*(H//2) else 'No')

Submission status: Accepted

Solution code:
t="abcdefghijklmnopqrstuvwxyz"
h,w=map(int,input().split())
a=[list(input())for _ in range(h)]
b=[0]*26
for i in a:
  for j in i:b[t.index(j)]+=1
x,y,z=(h//2)*(w//2),(h%2)*(w//2)+(h//2)*(w%2),(h%2)*(w%2)
for i in b:
  j=i
  while x and j>3:
    x-=1
    j-=4
  while y and j>1:
    y-=1
    j-=2
  z-=j
if not(x==y==z==0):print("No")
else:print("Yes")
"""#一例出力、問題誤読して実装した
c=[w*[0]for _ in range(h)]
fi=ti=0
for i in range(27):
  while b[i]:
    if b[i]>=4:
      j,k=fi//(w//2),fi%(w//2)
      c[j][k]=c[j][w-k-1]=c[h-j-1][k]=c[h-j-1][w-k-1]=t[i]
      fi+=1
      b[i]-=4
    if b[i]==2:
      if ti<h//2 and w%2:c[ti][w//2]=c[h-ti-1][w//2]=t[i]
      else:c[h//2][ti]=c[h//2][w-1-ti]=t[i]
      ti+=1
      b[i]-=2
    if b[i]==1:
      c[h//2][w//2]=t[i]
      b[i]-=1
for i in c:print("".join(i))
"""