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 sys
input = sys.stdin.buffer.readline

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

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

from collections import defaultdict

def main():
	h,w=MI()
	d=defaultdict(int)

	for _ in range(h):
		s=RD()
		for i in s:
			d[i]+=1

	dd=defaultdict(int)

	for k,v in d.items():
		q,r=divmod(v,4)
		dd[4]+=q
		qq,rr=divmod(r,2)
		dd[2]+=qq
		dd[1]+=rr
	#print(dd)


	ans="Yes"

	if h%2==0 and w%2==0:
		if dd[2]!=0 or dd[1]!=0:
			ans="No"

	elif h%2==0:
		if dd[1]!=0 or dd[2]>h//2:
			ans="No"

	elif w%2==0:
		if dd[1]!=0 or dd[2]>w//2:
			ans="No"

	else:
		if dd[1]!=1:
			ans="No"
		else:
			if dd[2]>h//2+w//2:
				ans="No"

	print(ans)


















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import Counter

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

if H % 2 and W % 2:
    has_one = False
    twos = 0
    for v in cntr.values():
        if v % 2:
            if has_one:
                print("No")
                exit()
            else:
                has_one = True
                twos += 2 if v == 3 else 0
        else:
            twos += v % 4
    print("Yes") if twos // 2 <= H // 2 + W // 2 and has_one else print("No")
elif H % 2 or W % 2:
    if H % 2:
        H, W = W, H
    twos = 0
    for v in cntr.values():
        if v % 2:
            print("No")
            exit()
        else:
            twos += v % 4
    print("Yes") if twos <= H else print("No")
else:
    print("Yes") if all(v % 4 == 0 for v in cntr.values()) else print("No")

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    H, W = MAP()
    a = [input() for _ in range(H)]
    d = defaultdict(int)

    for i in range(H):
        for j in range(W):
            d[a[i][j]] += 1
    
    mod4 = 0
    mod2 = 0
    for x in d.values():
        mod4 += x % 4
        mod2 += x % 2
    
    ans = "No"
    if H % 2 == 0:
        if W % 2 == 0:
            if mod4 == 0:
                ans = "Yes"
        else:
            if mod4 <= H and mod2 == 0:
                ans = "Yes"
    elif H % 2 == 1:
        if W % 2 == 0:
            if mod4 <= W and mod2 == 0:
                ans = "Yes"
        else:
            if mod4 <= W+H-1 and mod2 == 1:
                ans = "Yes"

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter

# sys.setrecursionlimit(100000)
from heapq import heappop, heappush, heapify


def main():
    h, w = [int(i) for i in input().strip().split()]
    s = ""
    for _ in range(h):
        s += input().strip()
    counts = Counter(s).most_common()
    cands = [-int(i) for v, i in counts]

    def pop(): return -heappop(cands)
    def push(x): return heappush(cands, -x)

    tasks = [4] * (h // 2) * (w // 2)
    tasks += [2] * ((h % 2) * (w // 2) + (w % 2) * (h // 2))
    tasks += [1] * ((h % 2) * (w % 2))

    flag = True
    for e in tasks:
        c = pop()
        if c < e:
            flag = False
            break
        push(c - e)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

one = two = four = 0

for k in s:
    if s[k] % 4 == 0:
        four += 1
    elif s[k] % 2 == 0:
        two += 1
    else:
        one += 1
limit_one = 0
limit_two = 0


def ans():
    if two <= limit_two and one <= limit_one:
        print("Yes")
    else:
        print("No")


if h & 1 and w & 1:
    limit_two = h // 2 + w // 2
    limit_one = 1
    ans()
elif h & 1:
    limit_two = w // 2
    ans()
elif w & 1:
    limit_two = h // 2
    ans()
else:
    limit_two = 0
    ans()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
import heapq

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


def solve():
    h, w = inl()
    counter = Counter()
    for i in range(h):
        for c in ins():
            counter[c] += 1

    p4 = (h // 2) * (w // 2)
    p1 = 1 if h % 2 == 1 and w % 2 == 1 else 0
    p2 = (h * w - p4 * 4 - p1) // 2

    xs = [-x for x in counter.values()]
    hp = []
    for x in xs:
        heapq.heappush(hp, x)

    while hp:
        x = heapq.heappop(hp)
        k = -x
        if p4 > 0:
            if k < 4:
                return False
            m = k // 4
            p = min(m, p4)
            p4 -= p
            k -= p * 4
            if k > 0:
                heapq.heappush(hp, -k)
        elif p2 > 0:
            if k < 2:
                return False
            m = k // 2
            p = min(m, p2)
            p2 -= p
            k -= p * 2
            if k > 0:
                heapq.heappush(hp, -k)
        elif p1 > 0:
            if k == 1:
                return True
            return False
    return True


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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = [list(str(input())) for i in range(h)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]*n
rank = [0]*n

for i in range(h):
    for j in range(w):
        idx1 = i*w+j
        idx2 = i*w+(w-1-j)
        idx3 = (h-1-i)*w+j
        Unite(idx1, idx2, par, rank)
        Unite(idx1, idx3, par, rank)
X = [0]*26
for i in range(h):
    for j in range(w):
        k = ord(A[i][j])-ord('a')
        X[k] += 1
temp = []
for i in range(26):
    if X[i] > 0:
        temp.append(X[i])
S = []
for i in range(h*w):
    if par[i] < 0:
        S.append(-par[i])

#print(temp)
#print(S)
S.sort(reverse=True)
import heapq
temp = [-1*t for t in temp]
heapq.heapify(temp)
for s in S:
    if temp:
        t = heapq.heappop(temp)*(-1)
        if t >= s:
            heapq.heappush(temp, (-1)*(t-s))
        else:
            print('No')
            exit()
    else:
        print('No')
        exit()
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, input().split())
    count = Counter()
    for _ in range(H):
        count += Counter(input())

    four = (H // 2) * (W // 2)
    two = (H // 2) * (W % 2) + (W // 2) * (H % 2)
    one = (H % 2) * (W % 2)

    for value in count.values():
        while value >= 4 and four > 0:
            value -= 4
            four -= 1
        while value >= 2 and two > 0:
            value -= 2
            two -= 1
        while value >= 1 and one > 0:
            value -= 1
            one -= 1

    if four == two == one == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


def main():
    from collections import Counter
    h, w = map(int, readline().split())
    c = Counter()
    res = [[""] * w for _ in range(h)]

    for _ in range(h):
        s = list(input())
        c.update(s)

    d = Counter()

    if h % 2 == 1 and w % 2 == 1:
        d[1] = 1
        d[2] = (h - 1) // 2 + (w - 1) // 2
    elif h % 2 == 1 and w % 2 == 0:
        d[1] = 0
        d[2] = w // 2
    elif h % 2 == 0 and w % 2 == 1:
        d[1] = 0
        d[2] = h // 2
    d[4] = (h * w - d[1] - 2 * d[2]) // 4

    keys = c.keys()

    for key in keys:
        if c[key] % 2 == 1:
            c[key] -= 1
            d[1] -= 1

    for key in keys:
        if c[key] % 4 == 2:
            c[key] -= 2
            d[2] -= 1

    for key in keys:
        if c[key] % 4 == 0:
            d[4] -= c[key] // 4
            c[key] = 0

    while d[2] > 0:
        d[2] -= 2
        d[4] += 1

    if d[1] == d[2] == d[4] == 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = {}
for i in range(h):
    s = input()
    for i in s:
        a.setdefault(i, 0)
        a[i] += 1
a2 = 0
a1 = 0
for i in a.values():
    if i % 2 == 1:
        a1 += 1
    elif i % 4 == 2:
        a2 += 2
if h % 2 == 1:
    if w % 2 == 1:
        b1 = 1
        b2 = h + w - 2
    else:
        b1 = 0
        b2 = w
else:
    if w % 2 == 1:
        b1 = 0
        b2 = h
    else:
        b1 = 0
        b2 = 0
if a1 > b1 or a2 > b2:
    print("No")
else:
    print("Yes")

Submission status: Accepted

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

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

ans1 = 0
ans2 = 0
ans4 = 0
if h % 2 == 1 and w % 2 == 1:
    ans1 = 1
    ans2 = (h - 1) // 2 + (w - 1) // 2
    ans4 = (h * w - ans1 - ans2 * 2) // 4
elif h % 2 == 1:
    ans2 = w // 2
    ans4 = (h * w - ans2 * 2) // 4
elif w % 2 == 1:
    ans2 = h // 2
    ans4 = (h * w - ans2 * 2) // 4
else:
    ans4 = h * w // 4

cnt1 = 0
cnt2 = 0
cnt4 = 0
for i in cnt:
    if i >= 4:
        cnt4 += i // 4
        i %= 4
    if i >= 2:
        cnt2 += i // 2
        i %= 2
    cnt1 += i

# print("ans1 =", ans1)
# print("ans2 =", ans2)
# print("ans4 =", ans4)
# print("cnt1 =", cnt1)
# print("cnt2 =", cnt2)
# print("cnt4 =", cnt4)

if ans4 > cnt4:
    print("No")
else:
    cnt2 += (cnt4 - ans4) * 2
    if ans2 > cnt2:
        print("No")
    else:
        cnt1 += (cnt2 - ans2) * 2
        if ans1 != cnt1:
            print("No")
        else:
            print("Yes")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_c
from collections import defaultdict

H,W = map(int,input().split())
C = defaultdict(int)
for _ in range(H):
    row = list(input())
    for i in range(W):
        C[row[i]] += 1
if H%2==0 and W%2==0:
    flag = 0
    for a in C:
        if C[a]%4!=0:
            flag = 1
            break
    if flag==0:
        print("Yes")
    else:
        print("No")
elif (H%2==0 and W%2==1) or (H%2==1 and W%2==0):
    n = (H//2)*(W//2)
    for a in C:
        if C[a]>=4:
            n -= C[a]//4
            C[a] = C[a]%4
    if n>0:
        print("No")
    else:
        flag = 0
        for a in C:
            if C[a]%2==1:
                flag=1
                break
        if flag==0:
            print("Yes")
        else:
            print("No")
else:
    n = (H//2)*(W//2)
    for a in C:
        if C[a]>=4:
            n -= C[a]//4
            C[a] = C[a]%4
    if n>0:
        print("No")
    else:
        cnt = 0
        for a in C:
            cnt += C[a]%2
        if cnt==1:
            print("Yes")
        else:
            print("No")


# 1つの行において列数が偶数の場合、例えば左端にaを置いた場合は、
# その列がpalindromeになる関係上必然的に右端にもaを置くことになる。
# さらに、列方向に見た場合は、今置いた2つのaに対して、一番下の行で
# それぞれを置く必要がある。したがって、1つのaを置くと、芋づる式に
# 合計４つのaを置くことになる。
# 行・列のどちらかが奇数の場合は、その真ん中のところにおいては
# 2個でよかったり、3個でよかったり、1個で良かったりするので、場合分けする。

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_c
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
C = {chr(i):0 for i in range(97,123)}
for i in range(H):
    for j in range(W):
        C[A[i][j]] += 1
if H%2==0 and W%2==0:
    flag = 0
    for a in C:
        if C[a]%4!=0:
            flag = 1
            break
    if flag==0:
        print("Yes")
    else:
        print("No")
elif (H%2==0 and W%2==1) or (H%2==1 and W%2==0):
    n = (H//2)*(W//2)
    for a in C:
        if C[a]>=4:
            n -= C[a]//4
            C[a] = C[a]%4
    if n>0:
        print("No")
    else:
        flag = 0
        for a in C:
            if C[a]%2==1:
                flag=1
                break
        if flag==0:
            print("Yes")
        else:
            print("No")
else:
    n = (H//2)*(W//2)
    for a in C:
        if C[a]>=4:
            n -= C[a]//4
            C[a] = C[a]%4
    if n>0:
        print("No")
    else:
        cnt = 0
        for a in C:
            cnt += C[a]%2
        if cnt==1:
            print("Yes")
        else:
            print("No")


# 1つの行において列数が偶数の場合、例えば左端にaを置いた場合は、
# その列がpalindromeになる関係上必然的に右端にもaを置くことになる。
# さらに、列方向に見た場合は、今置いた2つのaに対して、一番下の行で
# それぞれを置く必要がある。したがって、1つのaを置くと、芋づる式に
# 合計４つのaを置くことになる。
# 行・列のどちらかが奇数の場合は、その真ん中のところにおいては
# 2個でよかったり、3個でよかったり、1個で良かったりするので、場合分けする。

Submission status: Accepted

Solution code:
from collections import Counter

H,W,*n = open(0).read().split()
H = int(H)
W = int(W)
c = Counter([])
for x in n:
    c += Counter(x)
if H % 2 == 0 and W % 2 == 0:
    for x in c.values():
        if x % 4 != 0:
            print('No')
            break
    else:
        print('Yes')
elif H % 2 == 1 and W % 2 == 1:
    center = 0
    cross = H + W - 1
    corner = (H*W) - cross
    corner_filled = 0
    cross_filled = 0
    for x in c.values():
        if x % 2 == 1:
            if center == 0:
                center = 1
                y = x - 1
            else:
                print('No')
                break
        else:
            y = x
        if y % 4 == 0:
            if corner_filled + x < corner:
                corner_filled += x
            elif corner_filled == corner:
                if cross_filled + x > cross:
                    print('No')
                    break
                else:
                    cross_filled += x
            else:
                cross_filled += corner_filled + x - corner
                corner_filled = corner
        else:
            temp = (x//4) * 4
            if corner_filled + temp < corner:
                corner_filled += temp
            elif corner_filled == corner:
                if cross_filled + temp > cross:
                    print('No')
                    break
                else:
                    cross_filled += temp
            else:
                cross_filled += corner_filled + temp - corner
                corner_filled = corner
            if cross_filled + 2 > cross:
                print('No')
                break
            else:
                cross_filled += 2
    else:
        print('Yes')
else:
    if H % 2 == 1:
        center = W
        sides = (H*W) - W
    else:
        center = H
        sides = (H*W) - H
    center_filled = 0
    sides_filled = 0
    for x in c.values():
        if x % 4 == 0:
            if sides_filled + x < sides:
                sides_filled += x
            elif sides_filled == sides:
                if center_filled + x > center:
                    print('No')
                    break
                else:
                    center_filled += x
            else:
                center_filled += sides_filled + x - sides
                sides_filled = sides
        elif x % 2 == 0:
            temp = (x//4) * 4
            if sides_filled + temp < sides:
                sides_filled += temp
            elif sides_filled == sides:
                if center_filled + temp > center:
                    print('No')
                    break
                else:
                    center_filled += temp
            else:
                center_filled += sides_filled + temp - sides
                sides_filled = sides
            if center_filled + 2 > center:
                print('No')
                break
            else:
                center_filled += 2
        else:
            print('No')
            break
    else:
        print('Yes')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a,l=[list(input())for i in range(h)],[0]*26
for i in a:
 for j in i:l[ord(j)-97]+=1
o,t,f=(h//2)*(w//2),(h//2)*(w%2)+(w//2)*(h%2),(h%2)*(w%2)
for i in l:
 while o and i>3:o-=1;i-=4
 while t and i>1:t-=1;i-=2
 f-=i
print("Yes"if o==t==f==0else"No")

Submission status: Accepted

Solution code:
from collections import Counter

def solve(h, w, a):
    c = Counter(list("".join(a)))
    g = [0] * 3
    for num in c.values():
        g[0] += int(num % 2 == 1)
        g[1] += 2 * int(num % 4 == 2)
        g[2] += (num // 4) * 4
    if (w % 2 == 0) and (h % 2 == 0):
        return "Yes" if (g[2] == h*w) else "No"
    if (w % 2 == 1) and (h % 2 == 1):
        return "Yes" if (g[0] == 1) and g[1] <= (h + w - 2) else "No"
    if w % 2 == 1:
        return "Yes" if (g[0] == 0) and (g[1] <= h) else "No"
    if h % 2 == 1:
        return "Yes" if (g[0] == 0) and (g[1] <= w) else "No"
    return "Yes"

h, w = map(int, input().split())
a = [input() for r in range(h)]
print(solve(h, w, a))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    a = []
    for _ in range(H):
        a.append(SS())
    a = ''.join(a)

    # not 中央行 and not 中央列 の文字は4n個
    # 中央行 xor 中央列 は2n or 4n個
    # 中央行中央列 は1個
    cnt = collections.Counter(a)
    l = list(cnt.values())
    c4 = len([i for i in l if i % 4 == 0])
    c2 = len([i for i in l if i % 4 == 2])
    c1 = len([i for i in l if i % 4 == 1])
    # print(cnt)
    # print(c4, c2, c1)

    if H % 2 == W % 2 == 0:
        if c4 == len(cnt):
            print('Yes')
        else:
            print('No')
    elif H % 2 == W % 2 == 1:
        if c1 == 1 and c2 <= (H + W - 2) // 2 and c4 + c2 + c1 == len(cnt):
            print('Yes')
        else:
            print('No')
    else:
        if H % 2 == 1:
            if c2 <= W // 2 and c4 + c2 == len(cnt):
                print('Yes')
            else:
                print('No')
        if W % 2 == 1:
            if c2 <= H // 2 and c4 + c2 == len(cnt):
                print('Yes')
            else:
                print('No')
            
if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy


def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    h,  w = getList()
    cnt = defaultdict(int)
    for i in range(h):
        for k, v in Counter(getS()).items():
            cnt[k] += v

    yon, ni, ichi = 0,0,0
    # print(cnt)

    for v in cnt.values():
        yon += v // 4
        v %= 4
        ni += v // 2
        v %= 2
        ichi += v
    # print(yon, ni, ichi)

    if h % 2 == 1 and w % 2 == 1:
        if ichi != 1:
            print("No")
            return
        if ni > h // 2 + w // 2:
            print("No")
            return
        print("Yes")
        return

    if h % 2 == 0 and w % 2 == 0:
        if ichi or ni:
            print("No")
            return
        print("Yes")
        return

    if h % 2 == 1:
        # print(yon, ni, ichi)
        if ichi or ni > w // 2:
            print("No")
            return
        print("Yes")
        return

    if ichi or ni > h // 2:
        print("No")
        return

    print("Yes")
    return

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools,heapq
input = sys.stdin.readline

def m(n):
    return -1*n

a = []
H,W=list(map(int,input().split()))
for _ in range(H):
    s = input().rstrip()
    a += list(s)
ac = collections.Counter(a)
acval = sorted(ac.values())

#両方偶数
if H%2 == 0 and W%2==0:
    flag = [4]*((H*W)//4)

#どっちか奇数
elif H%2 ==1 and W %2 == 0:
    flag = [2]*(W//2)+[4]*((H*W-W)//4)
elif W%2 ==1 and H %2 == 0:
    flag = [2]*(H//2)+[4]*((H*W-H)//4)

#両方奇数
if H%2 == 1 and W%2==1:
    flag = [1]+[2]*(H//2)+[2]*(W//2)+[4]*((H*W-1-(W-1)-(H-1))//4)
flag.sort()
acval = list(map(m,acval))
heapq.heapify(acval)
while acval:
    tmpq = -1*heapq.heappop(acval)
    tmpf = flag.pop()
    if tmpq < tmpf:
        print('No')
        exit()
    else:
        tmp = tmpq - tmpf
        if tmp !=0:
            heapq.heappush(acval,-1*tmp)
print('Yes')

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int, input().split())
count = Counter()
for _ in range(H):
    s = input()
    for j in range(W):
        count[s[j]] += 1
four = int(H/2) * int(W/2)
two = (H%2)*int(W/2) + (W%2)*int(H/2)
one = (H%2) * (W%2)
# print(count)
# print(four, two, one)
for i in range(26):
    alpha = chr(ord("a")+i)
    # 4つ組を使えるかどうか
    while count[alpha] >= 4 and four > 0:
        count[alpha] -= 4
        four -= 1
    while count[alpha] >= 2 and two > 0:
        count[alpha] -= 2
        two -= 1
    while count[alpha] >= 1 and one > 0:
        count[alpha] -= 1
        one -= 1
if four == two == one == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict
h, w = map(int, input().split())
A = defaultdict(int)
for _ in range(h):
  for x in str(input()):
    A[x] += 1
#print(A)
for k in A.keys():
  A[k] %= 4
#print(A)
if h%2 == 0 and w%2 == 0:
  if sum(A.values()) == 0:
    ans = 'Yes'
  else:
    ans = 'No'
else:
  cnt2 = 0
  for k in A.keys():
    if A[k] >= 2:
      cnt2 += 2
      A[k] %= 2
  rest = sum(A.values())
  if h%2 == 1 and w%2 == 1:
    if cnt2 <= h + w - 2 and rest == 1:
      ans = 'Yes'
    else:
      ans = 'No'
  else:
    if h%2 == 0 and cnt2 <= h and rest == 0:
      ans = 'Yes'
    elif w%2 == 0 and cnt2 <= w and rest == 0:
      ans = 'Yes'
    else:
      ans = 'No'
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    from heapq import heapify,heappop,heappush
    H,W = map(int,input().split())
    A = ''
    for i in range(H):
        A += input()
    A = list(A)
    num_chars = list(map(lambda x: -x, Counter(A).values()))
    heapify(num_chars)
    # H == 1 or W == 1

    for i in range((H//2)*(W//2)):
        num = heappop(num_chars)
        
        if -4 < num:
            print('No')
            return
        else:
            heappush(num_chars,num+4)

    if H & 1:
        for i in range(W//2):
            num = heappop(num_chars)
            if -2 < num:
                print('No')
                return
            else:
                heappush(num_chars,num+2)

    if W & 1:
        for i in range(H//2):
            num = heappop(num_chars)
            if -2 < num:
                print('No')
                return
            else:
                heappush(num_chars,num+2)

    print('Yes')
    return
    






main()