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:
ai = lambda: list(map(int,input().split()))

h,w = ai()
m = ''
for _ in range(h):
    m += input()

from collections import Counter
k = list(Counter(m).values())

c1 = 0
c2 = 0
for kk in k:
    if kk % 2:
        c1 += 1
        kk -= 1
    if kk % 4:
        c2 += 1

ans = 0
if h&1 and w&1:
    if c1 <= 1 and c2 <= h//2 + w/2:
        ans = 1
elif h&1:
    if c1 <= 0 and c2 <= w//2:
        ans = 1
elif w&1:
    if c1 <= 0 and c2 <= h//2:
        ans = 1
else:
    if c1 <= 0 and c2 <= 0:
        ans = 1

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

Submission status: Accepted

Solution code:
import sys


ans = 'No'
h, w = [int(_) for _ in input().split()]
s = ''
for i in range(h):
    s += input()

dict = {}
for i in range(len(s)):
    if s[i] in dict.keys():
        dict[s[i]] += 1
    else:
        dict[s[i]] = 1

list = list(dict.values())

if h % 2 != 0 and w % 2 != 0:
    for i in range(len(list)):
        if list[i] % 2 != 0:
            list[i] -= 1
            break

for i in list:
    if i % 2 != 0:
        print('No')
        sys.exit()

c = 0
if h % 2 == 1:
    if w % 2 == 0:
        c += w / 2
    else:
        c += (w - 1) / 2
if w % 2 == 1:
    if h % 2 == 0:
        c += h / 2
    else:
        c += (h - 1) / 2

p = (h // 2) * (w // 2)
for j in range(p):
    for i in range(len(list)):
        if list[i] >= 4:
            list[i] = list[i] % 4
            break

k = 0
for i in list:
    k += i / 2

if k == c:
    ans = 'Yes'

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

H, W = map(int,input().split())
A = ""
for _ in range(H): A += input()
C_A = Counter(A)
g1 = (H*W)%2
g2 = (H%2)*(W//2) + (W%2)*(H//2)
g4 = (H//2)*(W//2)
g1_est = 0; g2_est = 0; g4_est = 0;

for n in C_A.values():
    g4_est += n//4
    g2_est += (n%4)//2
    g1_est += n%2
if g4_est>=g4:
    g2_est += 2*(g4_est - g4)
    if g2==g2_est and g1==g1_est:
        print("Yes")
        exit()
print("No")

Submission status: Accepted

Solution code:
from collections import Counter

H, W = map(int,input().split())
A = ""
for _ in range(H): A += input()

a_count = Counter(A)
sym4 = [0, 0]
sym2 = [0, 0]
sym1 = [0, 0]
sym4[0] = (H//2) * (W//2)
sym2[0] = (H%2) * (W//2) + (H//2) * (W%2)
sym1[0] = (H%2) * (W%2)

for i in a_count.values():
    sym4[1] += i // 4
    sym2[1] += (i % 4) // 2
    sym1[1] += i % 2

if sym4[1] >= sym4[0]:
    sym2[1] += 2 * (sym4[1] - sym4[0])
    if sym2[1] == sym2[0]:
        print('Yes')
        exit()

print('No')

Submission status: Accepted

Solution code:
def no():
    print("No")
    exit()
H, W = map(int, input().split())
L = [0]*26
for i in range(H):
    for a in input():
        L[ord(a)-97] += 1
t4 = (H//2)*(W//2)
t2 = (H//2)*(W%2)+(H%2)*(W//2)
t1 = (H%2)*(W%2)
#print(L, t4, t2, t1)
for i, n in enumerate(L):
    q, m = divmod(n, 2)
    L[i] = q
    if m==1:
        t1 -= 1
if t1 != 0:
    no()
for i, n in enumerate(L):
    q, m = divmod(n, 2)
    L[i] = q
    if m==1:
        t2 -= 1
if t2 < 0 or t2%2 != 0:
    no()
t4 += t2//2

print("Yes")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from collections import Counter

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()


H, W = in_intlist()
a_list = []
for _ in range(H):
    s = in_strings()
    a_list.extend(list(s))

a_count = Counter(a_list)
sym4 = [0, 0]
sym2 = [0, 0]
sym1 = [0, 0]
sym4[0] = (H//2) * (W//2) 
sym2[0] = (H%2) * (W//2) + (H//2) * (W%2)
sym1[0] = (H%2) * (W%2)

for i in a_count.values():
    sym4[1] += i // 4
    sym2[1] += (i % 4) // 2
    sym1[1] += i % 2

if sym4[1] >= sym4[0]:
    sym2[1] += 2 * (sym4[1] - sym4[0])
    if sym2[1] == sym2[0]:
        print('Yes')
        exit()

print('No')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

h,w = li()

cnt = Counter([])
for _ in range(h):
    tmp = lc()
    for c in tmp:
        cnt[c] += 1

exist = True

if h%2 == 0 and w%2 == 0:
    for key,value in cnt.items():
        if value%4 != 0:
            exist = False
            break
        
elif h%2 == 1 and w%2 == 1:
    odd = 0
    mod4_2 = 0
    for key,value in cnt.items():
        if value % 2 == 1:
            odd += 1
        elif value % 4 == 2:
            mod4_2 += 1
            
    if odd > 1:
        exist = False
    elif mod4_2 > (h+w-2)//2:
        exist = False
        
else:
    odmax = 0
    if h%2 == 0:
        odmax = h//2
    else:
        odmax = w//2
        
    
    mod4_2 = 0
    for key, value in cnt.items():
        if value%2 != 0:
            exist = False
            break
        elif value%4 == 2:
            mod4_2 +=1
            
    if mod4_2 > odmax:
        exist = False
        
        
if exist:
    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()
CS = Counter(S)
ans = 'Yes'
two = 0
one = 1
if H%2 == 1:
    two += W//2
if W%2 == 1:
    two += H//2
if H%2 == 1 and W%2 == 1:
    one = 1

nowtwo = 0
nowone = 0
for x in CS:
    if CS[x]%4 == 0:
        continue
    else:
        if CS[x]%2 == 0:
            nowtwo += 1
            if nowtwo > two:
                ans = 'No'
                break
        else:
            nowone += 1
            if nowone > one:
                ans = 'No'
                break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
counter = Counter(s for li in a for s in li)
g1 = g2 = 0
g4 = (H // 2) * (W // 2)
if H % 2 and W % 2:
    g1 = 1
    g2 = (H // 2) + (W // 2)
elif H % 2 == 0 and W % 2:
    g2 = H // 2
elif H % 2 and W % 2 == 0:
    g2 = W // 2

if g1:
    for c in counter:
        if counter[c] % 4 in {1, 3}:
            counter[c] -= 1
            break
for _ in range(g2):
    for c in counter:
        if counter[c] % 4 == 2:
            counter[c] -= 2
            break
if all(v % 4 == 0 for v in counter.values()):
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
    A.extend(list(input()))
A.sort()
a = [0, 0, 0]
if H % 2 != 0 and W % 2 != 0:
    a[0] = 1
    a[1] = int(H / 2) + int(W / 2)
    a[2] = int((H * W - a[0] - a[1] * 2) / 4)
elif H % 2 != 0:
    a[0] = 0
    a[1] = int(W / 2)
    a[2] = int((H * W - a[0] - a[1] * 2) / 4)
elif W % 2 != 0:
    a[0] = 0
    a[1] = int(H / 2)
    a[2] = int((H * W - a[0] - a[1] * 2) / 4)
else:
    a[0] = 0
    a[1] = 0
    a[2] = int(H * W / 4)
c = 1
cnt = [0, 0, 0]
for i in range(1, H * W):
    if A[i] == A[i - 1]:
        c += 1
    else:
        if c == 1:
            cnt[0] += 1
        elif c == 2:
            cnt[1] += 1
        elif c == 3:
            cnt[0] += 1
            cnt[1] += 1
        elif c == 4:
            cnt[2] += 1
        elif c > 4:
            cnt[2] += int(c / 4)
            c %= 4
            if c == 3:
                cnt[0] += 1
                cnt[1] += 1
            if c == 2:
                cnt[1] += 1
            if c == 1:
                cnt[0] += 1
        c = 1
        
if c == 1:
    cnt[0] += 1
elif c == 2:
    cnt[1] += 1
elif c == 3:
    cnt[0] += 1
    cnt[1] += 1
elif c == 4:
    cnt[2] += 1
elif c > 4:
    cnt[2] += int(c / 4)
    c %= 4
    if c == 3:
        cnt[0] += 1
        cnt[1] += 1
    if c == 2:
        cnt[1] += 1
    if c == 1:
        cnt[0] += 1

ans = 1
#print(a, cnt, ans)
if a[2] > cnt[2]:
    ans = -1
cnt[2] -= a[2]
cnt[1] += cnt[2] * 2
#print(a, cnt, ans)
if a[1] > cnt[1]:
    ans = -1
cnt[1] -= a[1]
cnt[0] += cnt[1] * 2
#print(a, cnt, ans, 2)
if cnt[0] != a[0]:
    ans = -1
if ans == 1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
h,w = map(int, sys.stdin.readline().split())
a = [[[c] for c in l.strip()] for l in sys.stdin]
from itertools import chain
a = list(chain.from_iterable(a))
a = list(chain.from_iterable(a))
import collections
c = collections.Counter(a)
counts,values = zip(*c.most_common())
if (h %2 == 0 and w %2 == 0):
    for i in values:
        if i %4 != 0:
            print("No")
            break
    else:
        print("Yes")
elif (h%2 == 1 and w %2 == 1):
    yu = (w-1 + h-1)/2
    iko = 1
    for i in values:
        if i %4 == 0:
            continue
        elif i %2 == 0:
            yu -= 1
            if yu < 0:
                print("No")
                break
        elif i %4 == 1:
            iko -= 1
            if iko < 0:
                print('No')
                break
        else:
            iko-= 1
            yu-=1
            if iko < 0:
                print('No')
                break
            if yu < 0:
                print("No")
                break
    else:
        print('Yes')
else:
    if h %2 == 0:
      yu = h/2
    else:
      yu = w/2
    for i in values:
        if i %4 == 0:
            continue
        elif i %2 == 0:
            yu -= 1
            if yu < 0:
                print("No")
                break
        else:
            print("No")
            break
    else:
        print('Yes')

Submission status: Accepted

Solution code:
h,w = list(map(int, input().split()))
data = {}
mod = {0:0,1:0,2:0,3:0}
for i in range(h):
    temp = input()
    for x in temp:
        if x in data:data[x]+=1
        else:data[x] = 1
for x in data.values():
    temp = x%4
    mod[temp] += temp

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

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())

    cnt_dict = {}
    for i in range(h):
        for j in range(w):
            cnt_dict[a[i][j]] = cnt_dict.get(a[i][j], 0) + 1

    cnt_odd, cnt_even, cnt_f, max_odd = 0, 0, 0, 0
    for i in cnt_dict:
        if cnt_dict[i] % 4 == 0:
            cnt_f += 1
        if cnt_dict[i] % 2 == 0:
            cnt_even += 1
        else:
            cnt_odd += 1
            max_odd = max(max_odd, cnt_dict[i]) % 4

    if h % 2 == 0 and w % 2 == 0:
        if cnt_odd == 0 and cnt_even == cnt_f:
            print("Yes")
        else:
            print("No")
    elif h % 2 and w % 2:
        if cnt_odd == 1 and cnt_even - cnt_f <= h // 2 + w // 2 - max_odd // 2:
            print("Yes")
        else:
            print("No")
    else:
        if h % 2 == 0:
            u = h
        else:
            u = w
        if cnt_odd == 0 and cnt_even - cnt_f <= u // 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())
S = []
for h in range(H):
    tmp = list(input())
    for w in tmp:
        S.append(w)

S = Counter(S)
square = (H // 2) * (W // 2)
line = (H // 2) * (W % 2 == 1) + (W // 2) * (H % 2 == 1)

if H % 2 == 1 and W % 2 == 1:
    for key, value in S.items():
        if value % 2 == 1:
            S[key] -= 1
            break

for key, value in S.items():
    if value >= 4:
        while value >= 4 and square != 0:
            square -= 1
            value -= 4
            S[key] -= 4


for key, value in S.items():
    if value >= 2:
        while value >= 2:
            line -= 1
            value -= 2
            S[key] -= 2

print("Yes" if square == 0 and line == 0 else "No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

H, W = map(int, input().split())
a = ""
for i in range(H):
    a += input()

# count = {}
count_all = len(a)
count_4 = 0
count_2 = 0
count_1 = 0

for s in "abcdefghijklmnopqrstuvwxyz":
    # count[s] = a.count(s)
    c = a.count(s)
    count_4 += c//4
    c = c%4
    count_2 += c//2
    c = c%2
    count_1 += c

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

# sys.stderr.write(str(321))
if W%2 == 0 and H%2 == 0:
    sys.stderr.write(str((count_4, W*(H-1)//4)))
    if count_4 < W*H//4:
        print("No")
    else:
        print("Yes")
elif W%2 == 0 and H%2 == 1:
    if count_4 < W*(H-1)//4:
        # print(count_4, W*(H-1)//4)
        sys.stderr.write(str((count_4, W*(H-1)//4)))
        print("No")
    elif 2*(count_4 - W*(H-1)//4) + count_2 < W//2:
        print("No")
    else:
        print("Yes")
else:
    if count_4 < (W-1)*(H-1)//4:
        print("No")
    elif 2*(count_4 - (W-1)*(H-1)//4) + count_2 < (W+H-2)//2:
        print("No")
    else:
        print("Yes")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

H, W = map(int, input().split())
a = ""
for i in range(H):
    a += input()

# count = {}
count_all = len(a)
count_4 = 0
count_2 = 0
count_1 = 0

for s in "abcdefghijklmnopqrstuvwxyz":
    # count[s] = a.count(s)
    c = a.count(s)
    count_4 += c//4
    c = c%4
    count_2 += c//2
    c = c%2
    count_1 += c

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

if W%2 == 0 and H%2 == 0:
    if count_4 < W*H//4:
        print("No")
    else:
        print("Yes")
elif W%2 == 0 and H%2 == 1:
    if count_4 < W*(H-1)//4:
        # print(count_4, W*(H-1)//4)
        print("No")
    elif 2*(count_4 - W*(H-1)//4) + count_2 < W//2:
        print("No")
    else:
        print("Yes")
else:
    if count_4 < (W-1)*(H-1)//4:
        print("No")
    elif 2*(count_4 - (W-1)*(H-1)//4) + count_2 < (W+H-2)//2:
        print("No")
    else:
        print("Yes")

Submission status: Accepted

Solution code:
from collections import Counter
h,w = (int(i) for i in input().split())
a = [input() for i in range(h)]
s,num,f = "",0,[0,0,0,0]
for i in a: s+=i
c = Counter(s).most_common()
for i in c: f[i[1]%4]+=1
if h==1 or w==1:
	if f[1]+f[3]==len(s)%2: print("Yes")
	else: print("No")
elif h%2==w%2==0:
	if f[1]+f[2]+f[3]==0: print("Yes")
	else: print("No")
elif h%2==w%2==1:
	x = (h+w-2)//2
	if f[1]+f[3]!=1: print("No")
	elif f[1]==1:
		if f[2]>x or f[2]%2!=x%2: print("No")
		else: print("Yes")
	else:
		if f[2]+1>x or (f[2]+1)%2!=x%2: print("No")
		else: print("No")
else:
	if h%2==0: h,w=w,h
	x = w//2
	if f[1]+f[3]!=0: print("No")
	elif f[2]>x or f[2]%2!=x%2: print("No")
	else: print("Yes")

Submission status: Accepted

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

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

A = []
for i in range(H):
    for c in list(input()):
        A.append(c)

dict = {}
for a in A:
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1


if H % 2 != 0 and W % 2 != 0:
    g1 = 1
    g2 = int(H//2) + int(W//2)
    g3 = int(H//2) * int(W//2)
else:
    g1 = 0
    if H % 2 == 0 and W % 2 == 0:
        g2 = 0
    else:
        if H % 2 == 0:
            g2 = int(H//2)
        else:
            g2 = int(W//2)
    g3 = int((H * W - g1 - g2 * 2) // 4)

for _ in range(g1):
    stack = []
    for c in dict:
        if dict[c] % 4 == 1 or dict[c] % 4 == 3:
            stack.append(c)
    if len(stack) > 1:
        x = stack.pop(random.randint(0, len(stack)-1))
        dict[x] -= 1
    elif len(stack) == 1:
        dict[stack[0]] -= 1
    else:
        pass


for _ in range(g2):
    stack = []
    for c in dict:
        if dict[c] % 4 == 2:
            stack.append(c)
    if len(stack) > 1:
        x = stack.pop(random.randint(0, len(stack)-1))
        dict[x] -= 2
    elif len(stack) == 1:
        dict[stack[0]] -= 2
    else:
        pass


for _ in range(g3):
    stack = []
    for c in dict:
        if dict[c] % 4 == 0 and dict[c] != 0:
            stack.append(c)
    if len(stack) > 1:
        x = stack.pop(random.randint(0, len(stack)-1))
        dict[x] -= 4
    elif len(stack) == 1:
        dict[stack[0]] -= 4
    else:
        pass

count = 0
for c in dict:
    if dict[c] % 4 != 0:
        count += 1
if count == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import Counter


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

char_to_cnt = Counter()
for h in range(H):
    for w in range(W):
        char_to_cnt.update(A[h][w])

if H % 2 != 0 and W % 2 != 0:
    g1 = 1
    g2 = H // 2 + W // 2
    g4 = (H // 2) * (W // 2)
else:
    g1 = 0
    if H % 2 == 0 and W % 2 == 0:
        g2 = 0
    else:
        if H % 2 == 0:
            g2 = H // 2
        else:
            g2 = W // 2
    g4 = (H * W - g1 - g2 * 2) // 4

for _ in range(g1):
    for char in char_to_cnt.keys():
        cnt = char_to_cnt[char]
        if cnt % 4 == 1 or cnt % 4 == 3:
            char_to_cnt[char] -= 1
            break

for _ in range(g2):
    for char in char_to_cnt.keys():
        cnt = char_to_cnt[char]
        if cnt % 4 == 2:
            char_to_cnt[char] -= 2
            break

for _ in range(g4):
    for char in char_to_cnt.keys():
        cnt = char_to_cnt[char]
        if cnt != 0 and cnt % 4 == 0:
            char_to_cnt[char] -= 4
            break

for _, cnt in char_to_cnt.items():
    if cnt % 4 != 0:
        print("No")
        exit()

print("Yes")

Submission status: Accepted

Solution code:
# coding: utf-8
h,w=map(int,input().split())
dic={}
for i in range(h):
    for c in input():
        if c in dic:
            dic[c]=(dic[c]+1)%4
        else:
            dic[c]=1
d=list(dic.values())
if h%2 and w%2:
    if d.count(1)+d.count(3)==1 and d.count(2)<=h//2+w//2:
        print('Yes')
    else:
        print('No')
elif (h%2 and not w%2) or (w%2 and not h%2):
    if not (d.count(1)+d.count(3)>0):
        if h%2:
            if d.count(2)<=w//2 :#and d.count(2)%2==(w//2)%2:
                print('Yes')
            else:
                print('No')
        elif w%2:
            if d.count(2)<=h//2 :#and d.count(2)%2==(h//2)%2:
                print('Yes')
            else:
                print('No')
    else:
        print('No')
else:
    if sum(d)==0:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    H, W = map(int, input().split())
    d = defaultdict(int)
    for y in range(H):
        for c in input():
            d[c] += 1

    counter = [0] * 5
    counter[4] = (H // 2) * (W // 2)

    if H % 2 == 0 and W % 2 == 0:
        pass
    elif H % 2 != 0 and W % 2 == 0:
        counter[2] = W // 2
    elif H % 2 == 0 and W % 2 != 0:
        counter[2] = H // 2
    elif H % 2 != 0 and W % 2 != 0:
        counter[2] = H // 2 + W // 2
        counter[1] = 1

    for x in [4, 2, 1]:
        for k, v in d.items():
            if v >= x and counter[x] > 0:
                n = v // x
                counter[x] -= n
                d[k] -= x * n

    if sum(counter) == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    H, W = map(int, input().split())
    d = defaultdict(int)
    for y in range(H):
        for c in input():
            d[c] += 1

    four, two, one = (H // 2) * (W // 2), 0, 0
    if H % 2 == 0 and W % 2 == 0:
        pass
    elif H % 2 != 0 and W % 2 == 0:
        two = W // 2
    elif H % 2 == 0 and W % 2 != 0:
        two = H // 2
    elif H % 2 != 0 and W % 2 != 0:
        two = H // 2 + W // 2
        one = 1

    for k, v in d.items():
        if v >= 4 and four > 0:
            n = v // 4
            four -= n
            d[k] -= 4 * n
    for k, v in d.items():
        if v >= 2 and two > 0:
            n = v // 2
            two -= n
            d[k] -= 2 * n
    for k, v in d.items():
        if v >= 1 and one > 0:
            one -= 1
            d[k] -= 1

    if one == 0 and two == 0 and four == 0 and sum(d.values()) == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, raw_input().split())
d = {}
for i in range(h):
    ai = raw_input()
    for j in ai:
        d[j] = d.get(j, 0) + 1

o = len(filter(lambda a:a%2==1, d.values()))
t = len(filter(lambda a:a%4==2, d.values()))

ol = 0
if w % 2 == 1 and h % 2 == 1:
    ol = 1
    tl = (w-1)/2 + (h-1)/2
elif w % 2 == 1:
    tl = h/2
elif h % 2 == 1:
    tl = w/2
else:
    tl = 0

if ol < o:
    print 'No'
elif tl < t:
    print 'No'
else:
    print 'Yes'

Submission status: Accepted

Solution code:
h, w = map(int, raw_input().split())
d = {}
for i in range(h):
    ai = raw_input()
    for j in ai:
        if j in d:
            d[j] += 1
        else:
            d[j] = 1

once = 0
two = 0
ONCE_LIMIT = 0
if w % 2 == 1 and h % 2 == 1:
    ONCE_LIMIT = 1
    TWO_LIMIT = (w-1)/2 + (h-1)/2
elif w % 2 == 1:
    TWO_LIMIT = h/2
elif h % 2 == 1:
    TWO_LIMIT = w/2
else:
    TWO_LIMIT = 0
for v in d.values():
    if v % 2 == 1 and once == ONCE_LIMIT:
        print 'No'
        exit()
    if v % 4 == 2 and two == TWO_LIMIT:
        print 'No'
        exit()
    if v % 4 == 2:
        two += 1
    if v % 2 == 1:
        once += 1
print 'Yes'

Submission status: Accepted

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

from collections import Counter
cnt = Counter()
for i in range(H):
    cnt.update(input())

num = [0 for i in range(3)]
for c in cnt.values():
    num[2] += c // 4
    if c % 4 == 1:
        num[0] += 1
    elif c % 4 == 2:
        num[1] += 1
    elif c % 4 == 3:
        num[0] += 1
        num[1] += 1

h2 = H // 2
w2 = W // 2
if H % 2 == 0 and W % 2 == 0:
    numOK = [0, 0, h2 * w2]

elif H % 2 != 0 and W % 2 != 0:
    numOK = [1, h2 + w2, h2 * w2]

else:
    if H % 2 == 0: e2 = h2
    else: e2 = w2
    numOK = [0, e2, h2 * w2]

num[2] -= numOK[2]
if num[2] < 0:
    print('No')
else:
    num[1] += num[2] * 2
    if num[1] == numOK[1] and num[0] == numOK[0]:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    h,w = LI()
    d = collections.defaultdict(int)
    for _ in range(h):
        for c in S():
            d[c] += 1

    t = 0
    t2 = 0
    for v in d.values():
        t += v//4
        t2 += (v%4) // 2

    f = (h//2) * (w//2)
    if t < f:
        return 'No'
    t2 += (t-f) * 2
    if w%2 == 1:
        t2 -= h//2
    if h%2 == 1:
        t2 -= w//2
    if t2 < 0:
        return 'No'
    return 'Yes'



print(main())

Submission status: Accepted

Solution code:
def fourcount(List):

	num = 0
	tmp = 1
	l = len(List)

	for i in range(1,l):

		if (List[i-1] == List[i]) and (tmp < 4):
			tmp += 1

		elif tmp == 4:
			num += 1
			tmp = 1

		else:
			tmp = 1

	if tmp == 4:
		num += 1
		
	return num
		

def twocount(List):

	num = 0
	tmp = 1
	l = len(List)

	for i in range(1,l):

		if (List[i-1] == List[i]) and (tmp < 2):
			tmp += 1

		elif tmp == 2:
			num += 1
			tmp = 1

		else:
			tmp = 1

	if tmp == 2:
		num += 1
		
	return num

def decision(H,W,num4,num2):

	if H == 1:
		if (W % 2 == 0) and (num2 == W/2):
			print("Yes")
		elif (W % 2 == 1) and (num2 == (W-1)/2):
			print("Yes")
		else:
			print("No")

	elif W == 1:
		if (H % 2 == 0) and (num2 == H/2):
			print("Yes")
		elif (H % 2 == 1) and (num2 == (H-1)/2):
			print("Yes")
		else:
			print("No")

	elif H == 0 or W == 0:
		print("Yes")

	elif H > W:
		if (H % 2 == 0) and (H / 2 <= num4):
			same = H/2
			decision(H,W-2,num4-same,num2-same*2)
		elif (H % 2 == 1) and ((H-1) / 2 <= num4 ) and (num2-(H-1) >= 1):
			same =  (H-1) /2
			decision(H,W-2,num4-same,num2-same*2-1)
		else:
			print("No")

	elif W > H:
		if (W % 2 == 0) and (W / 2 <= num4):
			same= W/2
			decision(H-2,W,num4-same,num2-same*2)
		elif (W % 2 == 1) and ((W-1) / 2 <= num4) and (num2-(W-1) >= 1):
			same =  (W-1) /2
			decision(H-2,W,num4-same,num2-same*2-1)
		else:
			print("No")

	elif W == H:
		if (H % 2 == 0) and (H - 1) <= num4 :
			same = H-1
			decision(H-2,W-2,num4-same,num2-same*2)
		elif (H % 2 == 1) and (H - 2) <= num4 and (num2-2*(H-2) >= 2):
			same = H-2
			decision(H-2,W-2,num4-same,num2-same*2-2)
		else :
			print("No")



H,W = map(int,input().split(" "))
a = []
b = []

for i in range(H):
	a = list(input())
	a = a[0:W]
	for string in a:
		b.append(string)

b.sort()

num4 = fourcount(b)
num2 = twocount(b) 

decision(H,W,num4,num2)

Submission status: Accepted

Solution code:
from collections import defaultdict

h,w=map(int,input().split())
dd = defaultdict(int)
for _ in range(h):
    s = list(input())
    for c in s:
        dd[c]+=1
rr=[0,0,0,0]
for k in dd.keys():
    rr[dd[k]%4]+=1

if h%2+w%2==0:  # even even
    if rr[1]>0 or rr[2]>0 or rr[3]>0:
        print('No')
    else:
        print('Yes')
elif h%2+w%2==1:  # even odd
    if rr[1]>0 or rr[3]>0:
        print('No')
    elif h%2==0:
        if rr[2]<=h//2:
            print('Yes')
        else:
            print('No')
    elif w%2==0:
        if rr[2]<=w//2:
            print('Yes')
        else:
            print('No')
else:  # odd odd
    if rr[1]+rr[3]!=1:
        print('No')
    elif rr[1]==1:
        if rr[2]<=(h+w-2)//2:
            print('Yes')
        else:
            print('No')
    elif rr[3]==1:
        if rr[2]+1<=(h+w-2)//2:
            print('Yes')
        else:
            print('No')

Submission status: Accepted

Solution code:
def func() :
    n,m=map(int,input().split())
    a={}
    for i in range(n) :
        s = input()
        for c in list(s):
            if c in a:
                a[c]+=1
            else :
                a[c] = 1
    c1=sum(map(lambda x : x%2 , a.values()))
    c2=sum(map(lambda x : x//4*4, a.values()))
    if c1 != n*m%2 or c2 < (n//2*2)*(m//2*2) :
        print('No')
    else :
        print('Yes')
func()

Submission status: Accepted

Solution code:
H,W = list(map(int, input().split()))
moji = ''
char = {}
for i in range(H):
    moji += input()
for m in moji:
    if m in char:
        char[m] += 1
    else:
        char.update({m:1})

four = 0
two = 0
one = 0
for c in char:
    four += int(char[c] / 4)
    two += int(char[c]%4/2)
    one += int(char[c]%2)

ans = [(H//2)*(W//2), (H//2)*(W%2)+(H%2)*(W//2), (H%2)*(W%2)]
four -= ans[0]
while(four > 0):
    four -= 1
    ans[1] -= 2
if two == ans[1] and one == ans[2]:
    print("Yes")
else:
    print("No")

Submission status: Accepted

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

d = {}

def quat(l):
    a=0
    for b in l:
        a += b % 4
    return a

def odd(l):
    a=0
    for b in l:
        a += b % 2
    return a

for i in range(h):
    s = raw_input()
    for j in range(w):
        if s[j] in d:
            d[s[j]] += 1
        else:
            d[s[j]] = 1
l=[]
for k in d:
    l += [d[k]]

if h*w % 2 == 1:
    if odd(l) != 1 or h+w-1 < quat(l):
        print "No"
    else:
        print "Yes"
elif h % 2 == 1:
    if odd(l) != 0 or w < quat(l):
        print "No"
    else:
        print "Yes"
elif w % 2 == 1:
    if odd(l) != 0 or h < quat(l):
        print "No"
    else:
        print "Yes"
else:
    if 0 == quat(l):
        print "Yes"
    else:
        print "No"

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    h, w = map(int, input().split())
    wd = dict(Counter(list("".join([input() for _ in range(h)]))))

    g1 = (w % 2) & (h % 2)
    g2 = (w % 2) * h//2 + (h % 2) * w//2
    g4 = h//2 * w//2
    
    for k in wd.keys():
        if (g1 > 0) and wd[k] % 4 == 1 or wd[k] % 4 == 3:
            g1 -= 1
            wd[k] -= 1
        while (g4 > 0) and wd[k] >= 4:
            g4 -= 1
            wd[k] -= 4
        while (g2 > 0) and wd[k] >= 2:
            g2 -= 1
            wd[k] -= 2
            
    print("No" if sum(wd.values()) else "Yes")
    
if __name__=="__main__":
    solve()