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:
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)


    if H & 1 and W & 1:
        if num_chars[0] != -1:
            return
    print('Yes')
    return
    






main()

Submission status: Accepted

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

d = {}
for _ in range(h):
    a = input()
    for i in range(w):
        a1 = a[i]
        if a1 in d:
            d[a1] += 1
        else:
            d[a1] = 1

if h % 2 == 0 and w % 2 == 0:
    for v in d.values():
        if v % 4 != 0:
            print('No')
            exit()
    print('Yes')

elif h % 2 == 0 or w % 2 == 0:
    cnt_4 = (h // 2) * (w // 2)
    if h % 2 == 0:
        cnt_2 = h // 2
    else:
        cnt_2 = w // 2
    tmp_2 = 0
    tmp_4 = 0
    for v in d.values():
        if v % 4 == 0:
            tmp_4 += v // 4
        elif v % 2 == 0:
            tmp_4 += v // 4
            tmp_2 += 1
        else:
            print('No')
            exit()
    if tmp_4 >= cnt_4 and cnt_2 == tmp_2 + (tmp_4 - cnt_4) * 2:
        print('Yes')
    else:
        print('No')

else:
    cnt_4 = (h // 2) * (w // 2)
    cnt_2 = h // 2 + w // 2
    cnt_1 = 1
    tmp_1 = 0
    tmp_2 = 0
    tmp_4 = 0

    for v in d.values():
        if v % 4 == 0:
            tmp_4 += v // 4
        elif v % 2 == 0:
            tmp_4 += v // 4
            tmp_2 += 1
        else:
            tmp_4 += v // 4
            tmp_2 += (v % 4) // 2
            tmp_1 += 1
    if tmp_4 >= cnt_4 and cnt_2 <= tmp_2 + (tmp_4 - cnt_4) * 2 and cnt_1 == tmp_1 + tmp_2 + (tmp_4 - cnt_4) * 2 - cnt_2:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
from collections import Counter


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    H, W = read_ints()
    counter = Counter()
    for _ in range(H):
        counter += Counter(input())
    C = list(counter.values())
    fours = H//2*W//2
    twos = W//2*(H%2)+H//2*(W%2)
    ones = (H%2)*(W%2)
    for c in C:
        while c != 0:
            if c >= 4 and fours > 0:
                fours -= 1
                c -= 4
            elif c >= 2 and twos > 0:
                twos -= 1
                c -= 2
            elif c >= 1 and ones > 0:
                ones -= 1
                c -= 1
            else:
                return 'No'
    return 'Yes'


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
used=[[0]*w for _ in range(h)]

grid=[]

for i in range(h):
    for j in range(w):
        if used[i][j]==0:
            grid.append([(i,j)])
            used[i][j]=1
            if used[h-i-1][j]==0:
                grid[-1].append((h-i-1,j))
                used[h-i-1][j]=1
            if used[h-i-1][w-j-1]==0:
                grid[-1].append((h-i-1,w-j-1))
                used[h-i-1][w-j-1]=1
            if used[i][w-j-1]==0:
                grid[-1].append((i,w-j-1))
                used[i][w-j-1]=1

num=[len(x) for x in grid]
num=sorted(num, reverse=True)
from collections import defaultdict

d=defaultdict(int)
for i in range(h):
    S=list(input())
    for s in S:
        d[s]+=1

for i in range(len(num)):
    for x in range(26):
        if d[chr(97+x)]>=num[i]:
            d[chr(97+x)]-=num[i]
            break

for x in range(26):
    if d[chr(97+x)]>=1:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import Counter
def check():
  H, W = map(int, input().split())
  A = []
  for i in range(H):
    A.extend(list(input()))
  c = Counter(A)
  one = 0
  two = 0
  for v in c.values():
    if v%2==1:
      one += 1
    if v%4==2:
      two += 1
  if H%2==0 and W%2==0:
    if one+two>0:
      return 'No'
  if H%2==0 and W%2==1:
    if two>H//2 or one>0:
      return 'No'
  if H%2==1 and W%2==0:
    if two>W//2 or one>0:
      return 'No'
  if H%2==1 and W%2==1:
    if two>W//2+H//2 or one>1:
      return 'No'
  return 'Yes'
print(check())

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int, input().split())
C = []
for i in range(H):
  C = C + (list(input()))
  
C = Counter(C)
if len(C) == 1:
  print("Yes")
  exit(0)
  
V = sorted(C.values())

"""
H:odd, W:odd
  H+W-1 が奇数一つと2の倍数で組成
  残りH*W - sakkino が4の倍数で組成
H:even, W:odd
  H が2の倍数で組成
  残りが4の倍数で組成
H:even, W:even
  すべて4の倍数で組成
"""
oddFlg = True if H%2 == 1 and W%2 == 1 else False
res = 1 if H%2 == 1 and W%2 == 1 else 0
res += H if W%2 == 1 else 0
res += W if H%2 == 1 else 0

als = H*W - res

A2 = []
A4 = []
for i in range(len(V)):
  v = V[i]
  if v == 0:
    continue
  elif v % 2 == 1:
    if oddFlg:
      oddFlg = False
      res -= 1
      A2.append(v-1)
    else:
      print("No")
      exit(0)
  elif v%4 == 0:
    A4.append(v)
  else:
    A2.append(v)
  
"""
print(res)
print(A2)
print(A4)
"""

for a in A2:
  res -= 2
  A4.append(a-2)
  if res < 0:
    print("No")
    exit(0)
    
res += als
if res == sum(A4):
  print("Yes")
else:
  print("No")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
alp_d = {chr(ord('a') + i): 0 for i in range(26)}

for _ in range(h):
    s = list(input())
    for si in s:
        alp_d[si] += 1
        alp_d[si] %= 4

r4 = [0]*4
for v in alp_d.values():
    r4[v] += 1

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

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

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

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
h,w = readInts()
S = ""
for i in range(h):
    S += input()
LIST = Counter(S)
if h%2 == 0 and w%2 == 0:
    for k,v in LIST.items():
        if v%4:
            print('No')
            exit()
elif (h%2 == 0 and w%2) or (h%2 and w%2 == 0):
    two = 0
    for k,v in LIST.items():
        if v%2 or v%4 == 3:
            print('No')
            exit()
        if v%4 == 2:
            two += 1
    if h%2 == 0:
        if two > h//2:
            print('No')
            exit()
    else:
        if two > w//2:
            print('No')
            exit()
else:
    odd = 0
    two = 0
    for k,v in LIST.items():
        if v%4 == 1:
            odd += 1
        if v%4 == 2:
            two += 1
        if v%4 == 3:
            print('No')
            exit()
    if odd != 1:
        print('No')
        exit()
    if two > ((h-1)//2 + (w-1)//2):
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

H, W = inm()


def solve():
    sc = Counter()
    for i in range(H):
        s = ins()
        for c in s:
            sc[c] += 1
    sv = sorted(sc.values(), reverse=True)
    fours = (H // 2) * (W // 2)
    for i in range(len(sv)):
        while fours > 0 and sv[i] >= 4:
            sv[i] -= 4
            fours -= 1
    if fours > 0:
        return False
    maxtwos = 0
    if H % 2 == 1:
        maxtwos += W // 2
    if W % 2 == 1:
        maxtwos += H // 2
    for i in range(len(sv)):
        while maxtwos > 0 and sv[i] >= 2:
            sv[i] -= 2
            maxtwos -= 1
    if maxtwos > 0:
        return False

    if (H * W) % 2 == 1:
        maxodds = 1
    else:
        maxodds = 0
    return sum(sv) == maxodds


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

Submission status: Accepted

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

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

odd = len([1 for v in ctr.values() if v%2])
pair = len([1 for v in ctr.values() if (v//2)%2==1])
if H%2 and W%2:
    if odd != 1:
        print('No')
    else:
        print('Yes' if pair <= H//2 + W//2 else 'No')
else:
    if odd:
        print('No')
    else:
        if H%2: H,W = W,H
        assert W%2
        print('Yes' if pair <= H//2 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter
def check():
  H, W = map(int, input().split())
  A = ''
  for i in range(H):
    A += input()
  c = Counter(A)
  if H%2==0:
    if W%2==0:
      for v in c.values():
        if v%4!=0:
          return 'No'
      return 'Yes'
    cnt = 0
    for v in c.values():
      if v%2==1:
        return 'No'
      if v%4==2:
        cnt += 1
        if cnt>H//2:
          return 'No'
    return 'Yes'
  if W%2==0:
    cnt = 0
    for v in c.values():
      if v%2==1:
        return 'No'
      if v%4==2:
        cnt += 1
        if cnt>W//2:
          return 'No'
    return 'Yes'
  one,two = 0,0
  for v in c.values():
    if v%2==1:
      one += 1
    if v%4==2:
      two += 1
    if one>1 or two>W//2+H//2:
      return 'No'
  return 'Yes'
print(check())

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
maze = [input() for i in range(H)]

dict = defaultdict(int)
for i in range(H):
    for s in maze[i]:
        dict[s] += 1

one_cnt = 0
two_cnt = 0
for i in dict.items():
    opt = i[1] % 4
    if opt == 1:
        one_cnt += 1
    elif opt == 2:
        two_cnt += 1
    elif opt == 3:
        one_cnt += 1
        two_cnt += 1

# 両方奇数
if H % 2 != 0 and W % 2 != 0:
    if one_cnt > 1 or two_cnt > H // 2 + W // 2:
        print('No')
        exit()
# Hが奇数
elif H % 2 != 0 and W % 2 == 0:
    if one_cnt > 0 or two_cnt > W // 2:
        print('No')
        exit()
# Wが奇数
elif H % 2 == 0 and W % 2 != 0:
    if one_cnt > 0 or two_cnt > H // 2:
        print('No')
        exit()
# 両方偶数
else:
    if one_cnt > 0 or two_cnt > 0:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
from string import ascii_lowercase


def new_val(cnt, base, target):
    diff = min(cnt // base, target)
    cnt -= diff * base
    target -= diff
    return cnt, target


def main():
    h, w = map(int, input().split())
    count = {s: 0 for s in ascii_lowercase}
    for _ in range(h):
        row = input()
        for j in range(w):
            count[row[j]] += 1
    target_4 = (h // 2) * (w // 2)
    target_1 = (h % 2) * (w % 2)
    target_2 = (w // 2) * (h % 2) + (h // 2) * (w % 2)
    ans = "Yes"
    for chr, cnt in count.items():
        count[chr], target_4 = new_val(cnt, 4, target_4)
    if target_4:
        ans = "No4"
    for chr, cnt in count.items():
        count[chr], target_2 = new_val(cnt, 2, target_2)
    if target_2:
        ans = "No2"
    if sum(count.values()) != target_1:
        ans = "No"
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


table = {}
for i in range(h):
    a = input()
    for c in a:
        if c not in table:
            table[c] = 1
        else:
            table[c] += 1

mod0 = []
mod1_3 = []
mod2 = []
for key, value in table.items():
    if value % 4 == 0:
        mod0.append(key)
    elif value % 4 == 2:
        mod2.append(key)
    else:
        mod1_3.append(key)


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

elif w % 2 == 0 or h % 2 == 0:
    if h % 2 == 0:
        w, h = h, w

    if w // 2 < len(mod2):
        print("No")
    elif len(mod1_3) > 0:
        print("No")
    else:
        print("Yes")
else:
    if len(mod1_3) == 1 and len(mod2) <= h // 2 + w // 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

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


table = {}
for i in range(h):
    a = input()
    for c in a:
        if c not in table:
            table[c] = 1
        else:
            table[c] += 1

mod0 = []
mod1 = []
mod2 = []
mod3 = []
for key, value in table.items():
    if value % 4 == 0:
        mod0.append(key)
    elif value % 4 == 1:
        mod1.append(key)
    elif value % 4 == 2:
        mod2.append(key)
    else:
        mod3.append(key)


if w % 2 == 0 and h % 2 == 0:
    if len(mod1) > 0 or len(mod2) > 0 or len(mod3) > 0:
        print("No")
    else:
        print("Yes")

elif w % 2 == 0 or h % 2 == 0:
    if h % 2 == 0:
        w, h = h, w

    if w // 2 < len(mod2):
        print("No")
    elif len(mod1) > 0 or len(mod3) > 0:
        print("No")
    else:
        print("Yes")
else:
    if len(mod1) == 1 and len(mod2) <= (h + w - 1) // 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    D = defaultdict(int)
    H, W = [int(x) for x in input().strip().split()]
    four_pair = (H // 2) * (W // 2)
    two_pair = H % 2 * W // 2 + W % 2 * H // 2
    one = H % 2 * W % 2
    for h in range(H):
        for s in list(input().strip()):
            D[s] += 1
    
    for d, i in D.items():
        while four_pair and i >= 4:
            four_pair -= 1
            i -= 4
        D[d] = i
    if four_pair:
        print('No')
        return False

    for d, i in D.items():
        while two_pair and i >= 2:
            two_pair -= 1
            i -= 2
        D[d] = i
    if two_pair:
        print('No')
        return False
    
    if one == sum(D.values()):
        print('Yes')
        return True
    else:
        print('No')
        return False

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
h, w = map(int, input().split())
A = []
for i in range(h):
    A.extend(list(input()))
cA = Counter(A)

l1 = h*w%2
l2 = (h//2)*(w%2) + (w//2)*(h%2)
l3 = (h//2)*(w//2)
if l1:
    for key, val in cA.items():
        if val%2==1:
            cA[key] -= 1
            break
for _ in range(l2):
    for key, val in cA.items():
        if val%4==2:
            cA[key] -= 2
            break
print('Yes' if sum(val%4 for val in cA.values()) == 0 else 'No')

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
a = [input() for i in range(h)]
abc = [0]*26
import heapq

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

heap=[]
heapq.heapify(heap)
for i in range(26):
  if abc[i]!=0:
    heapq.heappush(heap, -1*abc[i])
    
num4 = (h//2)*(w//2)
num2 = 0
if h%2==1:
  num2+=w//2
if w%2==1:
  num2+=h//2
    
while num4>0:
  temp=-1*heapq.heappop(heap)
  if temp>=4:
    if temp > 4:
      heapq.heappush(heap, -1*(temp-4))
    num4-=1
  else:
    print("No")
    quit()
    
while num2>0:
  temp=-1*heapq.heappop(heap)
  if temp>=2:
    if temp > 2:
      heapq.heappush(heap, -1*(temp-2))
    num2-=1
  else:
    print("No")
    quit()  
print("Yes")

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
alphcnt = [0] * 26
for _ in range(h):
    a = list(input())
    for x in a:
        alphcnt[ord(x) - 97] += 1
p1, p2, p4 = 0, 0, 0
for i in range(26):
    x = alphcnt[i] // 4
    alphcnt[i] -= 4 * x
    p4 += x
for i in range(26):
    x = alphcnt[i] // 2
    alphcnt[i] -= 2 * x
    p2 += x
for i in range(26):
    x = alphcnt[i]
    alphcnt[i] -= x
    p1 += x
t = 0
if h % 2 == w % 2 == 0:
    if p1 == p2 == 0:
        t = 1
elif h % 2 == w % 2 == 1:
    if p1 == 1 and p4 >= (h // 2) * (w // 2):
        t = 1
else:
    if p1 == 0 and p4 >= (h // 2) * (w // 2):
        t = 1
print("Yes" if t == 1 else "No")

Submission status: Accepted

Solution code:
import sys
from collections import Counter

H, W = map(int, sys.stdin.readline().split())

string = ""
for _ in range(H):
    string += sys.stdin.readline().strip()

counter = Counter(string)
e_one = 0
e_two = 0
e_four = 0
for key, count in counter.items():
    tmp = count // 4
    e_four += tmp
    count -= 4 * tmp
    tmp = count // 2
    e_two += tmp
    count -= 2 * tmp
    e_one += count

one = 0
two = 0
four = 0
if H % 2 == 0 and W % 2 == 0:
    four = H * W // 4
# 奇数の場合、中心の文字は1つしかなくても回文になる
elif H % 2 == 1 and W % 2 == 1:
    one = 1
    two = H // 2 + W // 2
    four = (H * W - (one + two * 2)) // 4
else:
    # 縦を奇数とする
    if W % 2 == 1:
        H, W = W, H

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

# print("exists", e_four, e_two, e_one)
# print("needs", four, two, one)

if four > e_four:
    print("No")
else:
    e_four -= four
    e_two += e_four * 2
    if two > e_two:
        print("No")
    else:
        e_two -= two
        e_one += e_two * 2
        if e_one == one:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
import sys
from collections import Counter

H, W = map(int, sys.stdin.readline().split())

string = ""
for _ in range(H):
    string += sys.stdin.readline().strip()

counter = Counter(string)
e_one = 0
e_two = 0
e_four = 0
for key, count in counter.items():
    tmp = count // 4
    e_four += tmp
    count -= 4 * tmp
    tmp = count // 2
    e_two += tmp
    count -= 2 * tmp
    e_one += count

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

# print("exists", e_four, e_two, e_one)
# print("needs", four, two, one)

if four > e_four:
    print("No")
else:
    e_four -= four
    e_two += e_four * 2
    if two > e_two:
        print("No")
    else:
        e_two -= two
        e_one += e_two * 2
        if e_one == one:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]
    n, m = [int(x) for x in input().split()]
    d = defaultdict(int)
    for i in range(n):
        s = input()
        for e in s:
            d[e] += 1
    odd = 0
    q = 0
    for c in d:
        odd += d[c] % 2
        q += d[c] // 4
    if n % 2 and m % 2:
        if odd == 1 and q * 4 >= (n * m - (n + m - 1)):
            print("Yes")
        else:
            print("No")
    elif n % 2 != m % 2:
        ev = n
        if m % 2 == 0: ev = m
        if q * 4 < n * m - ev or odd:
            print("No")
        else:
            print("Yes")
    else:
        if q * 4 != n * m:
            print("No")
        else:
            print("Yes")


t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
a b a
d c d
a b a
"""

Submission status: Accepted

Solution code:
import collections
h,w = map(int, input().split())
s = ''.join([''.join(input().split()) for _ in range(h)])

ctr = collections.Counter(s)
if h % 2 == 0 and w % 2 == 0:
    four, two = h*w//4, 0
elif h % 2 == 0:
    four, two = (h*w-h)//4, h//2
elif w % 2 == 0:
    four, two = (h*w-w)//4, w//2
else:
    four, two = (h*w-h-w+1)//4, (h+w-1)//2

cf = sum([c//4 for c in ctr.values()])
ct = sum([(c%4)//2 for c in ctr.values()])

if cf >= four and ct + 2*(cf-four) >= two:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import Counter
h,w=map(int,input().split())
s=""
for i in range(h):
  s+=input()
sc=Counter(s)
d=[0,0,0]
for v in sc.values():
    d[0]+=(v//4)*4
    d[1]+=2 if v%4>=2 else 0
    d[2]+=v%2

if w%2==0 and h%2==0:
  print("Yes" if d[0]==h*w else "No")
elif (w%2)*(h%2)==1:
  print("Yes" if d[1]<=(w-1)+(h-1) and d[2]==1 else "No")
elif w%2==0:
  print("Yes" if d[1]<=w and d[2]==0 else "No")
elif h%2==0:
  print("Yes" if d[1]<=h and d[2]==0 else "No")

Submission status: Accepted

Solution code:
# 要求されるカルテットを条件ごとに求めて、その後要求されるペアを求めているが２つWA

from collections import Counter
w = ''
H,W = map(int,input().split())
for _ in range(H):
    w += input()
freq = Counter(list(w))
#print(freq)

quartet = 0
pair = 0
if H%2 == 0 and W%2 == 0:
    for v in freq.values():
        if v%4 != 0:
            print('No')
            exit()
    print('Yes')
    exit()

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

    for k,v in freq.items():
        #if freq[k] %4 ==0:
        if freq[k]>=4:
            quartet += v//4
            freq[k] -= 4*(v//4)
    if quartet < (H//2)*(W//2): # change slash //
        print('No')
        exit()
    else:
        pair += 2*(quartet-(H//2)*(W//2)) # 余分なカルテットをペアに分解

    for k,v in freq.items():
        if freq[k] >= 2:
            pair += v//2
            freq[k] -= 2*(v//2)
    if pair != H//2:
        print('No')
        exit()
    else:
        print('Yes')
        exit()


elif H%2 != 0 and W%2 == 0:
    for k, v in freq.items():
        #if freq[k] % 4 == 0:
        if freq[k] >= 4:
            quartet += v // 4
            freq[k] -= 4 * (v // 4)
    if quartet < (H // 2) * (W // 2):
        print('No')
        exit()
    else:
        pair += 2 * (quartet - (H // 2) * (W // 2))  # 余分なカルテットをペアに分解

    for k, v in freq.items():
        if freq[k] >= 2:
            pair += v // 2
            freq[k] -= 2 * (v // 2)
    if pair != W // 2:
        print('No')
        exit()
    else:
        print('Yes')
        exit()

else:
    for k, v in freq.items():
        if freq[k] >= 4:
            quartet += v // 4
            freq[k] -= 4 * (v // 4)
    if quartet < (H // 2) * (W // 2):
        print('No')
        exit()
    else:
        pair += 2 * (quartet - (H // 2) * (W // 2))  # 余分なカルテットをペアに分解

    for k, v in freq.items():
        #if freq[k] % 2 == 0:
        if freq[k] >=2:
            pair += v // 2
            freq[k] -= 2 * (v // 2)
    if pair != (W//2 + H//2):
        print('No')
        exit()
    else:
        print('Yes')
        exit()

Submission status: Accepted

Solution code:
from collections import defaultdict

def f(n):
    a,b,c = 0,0,0
    a = n//4
    r = n%4
    b = r//2
    c = r%2
    return (a,b,c)

h,w = map(int,input().split())
a = defaultdict(lambda:0)
for _ in range(h):
    for i in input():
        a[i] += 1
need = []
need.append((h//2)*(w//2))
need.append((h%2)*(w//2)+(w%2)*(h//2))
need.append((h%2)*(w%2))
data = [0]*3
for i in a.values():
    j,k,l = f(i)
    data[0] += j
    data[1] += k
    data[2] += l
if data[0] >= need[0]:
    data[1] += (data[0]-need[0])*2
    if data[1] == need[1] and data[2] == need[2]:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
cnt=[0]*26
for i in range(h):
	a=input()
	for j in range(w):
		cnt[ord(a[j])-ord("a")]+=1
if h%2==1 and w%2==1:
	f=0
	for i in range(26):
		if cnt[i]%2==1:
			cnt[i]-=1
			break
	four=0
	for i in range(26):
		if cnt[i]>=4:
			four+=cnt[i]//4*4
		elif cnt[i]%2==1:
			f=-1
			break
	if four>=h*w-(h//2+w//2)*2-1 and f==0:
		f=1
	else:
		f=0
elif h%2==0 and w%2==0:
	f=1
	for i in range(26):
		if cnt[i]%4!=0:
			f=0
			break
else:
	if h%2==0:
		h,w=w,h
	two=0;f=0
	for i in range(26):
		if cnt[i]%4==2:
			two+=2
		elif cnt[i]%2==1:
			f=-1
			break
	if two<=w and f==0:
		f=1
	else:
		f=0
print("Yes" if f else "No")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
D = {}
center_of_center = (H % 2) * (W % 2)
center_of_H = (H % 2) * (W >> 1)
center_of_W = (W % 2) * (H >> 1)
for i in range(H):
  for j in range(W):
    if S[i][j] in D:
      D[S[i][j]] += 1
    else:
      D[S[i][j]] = 1
odd, half_odd, four = 0, 0, 0
odds = []
half_odds = []
fours = []
for i in D:
  if D[i] % 2:
    odd += 1
    odds.append(i)
  else:
    if (D[i] >> 1) % 2:
      half_odds.append(i)
      half_odd += 1
    else:
      four += 1
      fours.append(i)
if odd != center_of_center:
  print("No")
else:
  if odd != 0:
    D[odds[0]] -= 1
    if D[odds[0]] % 4 == 2:
      half_odd += 1
    else:
      four += 1
  if (center_of_H + center_of_W) % 2 != half_odd % 2 or center_of_H + center_of_W < half_odd:
    print("No")
  else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()

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

A = Counter(a).values()
cnt_1 = 0
cnt_2 = 0
cnt_4 = 0

for x in A:
	if x%4 == 0:
		cnt_4 += 1
	elif x%2 == 0:
		cnt_2 += 1
	else:
		cnt_1 += 1

if H%2 and W%2 and cnt_1 == 1 and cnt_2 <= H//2 + W//2:
	print("Yes")
elif H%2 + W%2 == 0 and cnt_1 + cnt_2 == 0:
	print("Yes")
elif H%2 and cnt_1 == 0 and cnt_2 <= W//2:
	print("Yes")
elif W%2 and cnt_1 == 0 and cnt_2 <= H//2:
	print("Yes")
else:
	print("No")