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:
H, W = map(int, input().split())
ctr = [0] * 26
for _ in range(H):
    s = str(input())
    for a in s:
        ctr[ord(a) - 97] += 1

# print(ctr)

def count(ctr):
    odd = 0
    two = 0
    four = 0
    for n in ctr:
        if n == 0: continue
        if n % 2 == 1: odd += 1
        elif n % 4 == 0: four += 1
        elif n % 2 == 0: 
            two += 1
            if n >= 4:
                four += 1
    return odd, two, four  

def f():
    odd, two, four = count(ctr)
    # print(odd, two, four)
    if (H * W) % 2 == 1:
        if odd > 1: return False
        if two > (H - 1) // 2 + (W - 1) // 2: return False
        return True
    if H % 2 == 0 and W % 2 == 0:
        if odd > 0 or two > 0: return False
        return True
    else:
        if odd > 0: return False
        if H % 2 == 1:
            tmp = W
        else:
            tmp = H
        if two > tmp // 2: return False
        return True

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

Submission status: Accepted

Solution code:
from collections import Counter
H,W = map(int,input().split())
A = [input() for i in range(H)]
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()

if H%2 and W%2:
    for k,v in ctr.items():
        if v%2:
            ctr[k] -= 1
            break
if any(v%2 for v in ctr.values()):
    print('No')
    exit()

if H%2 and W%2:
    two = W+H-1
elif H%2:
    two = W
else:
    two = H

for k,v in ctr.items():
    if v%4==0: continue
    if two <= 0:
        print('No')
        exit()
    two -= 2

print('No' if two%4==2 else 'Yes')

Submission status: Accepted

Solution code:
import sys
def main():
    H,W,*B=sys.stdin.read().split()
    H,W=int(H),int(W)
    A=[]
    for b in B: A+=list(b)
    from collections import Counter
    C=Counter(A)
    a4,a2,a1=0,0,0
    for v in C.values():
        d,m=divmod(v,4)
        a4+=d
        d,m=divmod(v,2)
        a2+=d
        a1+=m
    if a4 * 4 >= (H-(H&1))*(W-(W&1)) and a1 <= H&W&1:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    need1 = 0
    need2 = 0
    need4 = 0
    for i in range(h):
        for j in range(w):
            if (h % 2 == 1 and i * 2 + 1 == h) and (w % 2 == 1 and j * 2 + 1 == w):
                need1 += 1
            elif (h % 2 == 1 and i * 2 + 1 == h) or (w % 2 == 1 and j * 2 + 1 == w):
                need2 += 1
            else:
                need4 += 1

    count = dict()
    for x in a:
        for y in x:
            if y not in count:
                count[y] = 1
            else:
                count[y] += 1

    for _, num in count.items():
        while num >= 4 and need4 > 0:
            num -= 4
            need4 -= 4
        while num >= 2 and need2 > 0:
            num -= 2
            need2 -= 2
        while num >= 1 and need1 > 0:
            num -= 1
            need1 -= 1

    if need4 == 0 and need2 == 0 and need1 == 0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for _ in range(H):
    cntA += Counter(list(input()))

four = (H // 2) * (W // 2)
for a, c in cntA.items():
    if four <= 0:
        break
    while c >= 4 and four > 0:
        c -= 4
        four -= 1
    cntA[a] = c

if four > 0:
    print('No')
    exit()

if H % 2 == W % 2 == 1:
    for a, c in cntA.items():
        if c % 2 == 1:
            cntA[a] -= 1
            break
    else:
        print('No')
        exit()

print('Yes' if all(c % 2 == 0 for c in cntA.values()) else 'No')

Submission status: Accepted

Solution code:
from collections import Counter
H,W,*L = open(0).read().split()
H,W = map(int, (H,W))
s = ''
for c in L:
  s += c
Cnt = Counter(s)
g1 = 0
g2 = 0
g3 = 0
if H%2==1 and W%2==1:
  g1 = 1
  g2 = H//2+W//2
  g3 = (H//2)*(W//2)
elif H%2==1:
  g1 = 0
  g2 = W//2
  g3 = (H//2)*(W//2)
elif W%2==1:
  g1 = 0
  g2 = H//2
  g3 = (H//2)*(W//2)
else:
  g1 = 0
  g2 = 0
  g3 = (H//2)*(W//2)

while g3:
  for k in Cnt.keys():
    if Cnt[k]>=4:
      Cnt[k] -= 4
      g3 -= 1
      break
  else:
    break
  
while g2:
  for k in Cnt.keys():
    if Cnt[k]>=2:
      Cnt[k] -= 2
      g2 -= 1
      break
  else:
    break
  
while g1:
  for k in Cnt.keys():
    if Cnt[k]>=1:
      Cnt[k] -= 1
      g1 -= 1
      break
  else:
    break

if all(Cnt[k]==0 for k in Cnt.keys()):
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
from collections import Counter
def check():
    H, W = map(int, input().split())
    S = ''
    for i in range(H):
        S += input()
    C = Counter(S)
    vmod4 = list(map(lambda x:x%4,C.values()))
    V = Counter(vmod4)
    two = (H%2)*(W//2)+(H//2)*(W%2)
    odd = (H%2)*(W%2)
    if V[2]<= two and V[1]+V[3]<=odd:
        return True
    return False
if check():
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
# 奇数 * 奇数　の場合
# 1文字 - 1
# 2文字 - H//2 + W//2個
# 4文字 - H//2 * W//2個

# 奇数 * 偶数の場合　（Hが奇数とする）
# 2文字 - W//2個
# 4文字 - W//2個 * H//2個

# 偶数 * 偶数の場合
# 4文字 - w//2 * H//2個

H,W = map(int,input().split())
from collections import defaultdict
chars = defaultdict(int)
for i in range(H):
  for c in input():
    chars[c] += 1
    
# print(chars)
chars = sorted(chars.values())[::-1]
# print(chars)

ok = True

if H%2 == 1 and W%2 == 1:
  # 両方とも奇数の場合
  
  letter4 = (H//2) * (W//2)
#  print(H//2,W//2,letter4)
  ind = 0
  for i in range(letter4):
#    print(i,"in",letter4)
    while ind < len(chars):
      if chars[ind] >= 4:
        chars[ind]-=4
#        print(chars,ind)
        break
      else:
        ind+=1
        if ind == len(chars):
          ok = False
          break
        continue
        
#  print(chars,ok)
        
  letter2 = (H//2) + (W//2)
  ind = 0
  for i in range(letter2):
#    print(i,"in",letter2)
    while ind < len(chars):
      if chars[ind] >= 2:
        chars[ind]-=2
        break
      else:
        ind+=1
        if ind == len(chars):
          ok = False
          break
        continue
#  print(chars)
  if sum(chars) != 1:
    ok = False
elif H%2 == 0 and W%2== 0:
  # 両方とも偶数の場合
  
  # すべてのペアが4の倍数であることを確認
  for c in chars:
    if c%4 != 0:
      ok = False
      
else:
  # 片方が奇数の場合
  odd = -1
  even = -1
  if H%2 == 1:
    odd = H
    even = W
  else:
    odd = W
    even = H
    
  letter4 = (odd//2) * (even//2)
  ind = 0
  for i in range(letter4):
    while ind < len(chars):
      if chars[ind] >= 4:
        chars[ind]-=4
        break
      else:
        ind+=1
        if ind==len(chars):
          ok = False
          break
        continue
#  print(chars)
  for c in chars:
    if c%2 != 0:
      ok = False
#  print(chars)
  
print(("No","Yes")[ok])

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    H, W = map(int, input().split())
    a = ""
    for _ in range(H):
        a += input()
    c = Counter(a)
    cnt = [0] * 4
    for _, v in c.items():
        cnt[v % 4] += 1

    if cnt[3] > 0:
        cnt[1] += 1
        cnt[2] += 1
        cnt[3] -= 1

    if H % 2 == 1 and W % 2 == 1:
        if cnt[3]:
            return "No"
        if cnt[1] != 1:
            return "No"
        if cnt[2] > (H - 1) // 2 + (W - 1) // 2:
            return "No"
        return "Yes"
    elif H % 2 == 0 and W % 2 == 0:
        if cnt[1] or cnt[2] or cnt[3]:
            return "No"
        else:
            return "Yes"
    else:
        # Hが奇数，Wが偶数
        if W % 2 == 1:
            tmp = W
            W = H
            H = tmp
        if cnt[1] or cnt[3]:
            return "No"
        if cnt[2] > W // 2:
            return "No"
        return "Yes"


print(main())

Submission status: Accepted

Solution code:
H, W = [int(i) for i in input().split()]
d = {}
for _ in range(H):
    for a in input():
        if not a in d:
            d[a] = 1
        else:
            d[a] += 1
count = [0, 0, 0, 0, 0]
for v in d.values():
    for i in [4, 2, 1]:
        count[i] += v // i
        v %= i
for i, n in zip([4, 2, 1], [(H // 2) * (W // 2), H % 2 * W // 2 + W % 2 * H // 2, H % 2 * W % 2]):
    if count[i] < n:
        break
    count[i // 2] += (count[i] - n) * 2
else:
    print("Yes")
    exit()
print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    cnt = defaultdict(int)
    for line in S:
        for c in line:
            cnt[c] += 1
    if H % 2 == 0 and W % 2 == 0:
        for c in cnt.values():
            if c % 4 != 0:
                return False
        return True
    t1 = 0
    t2 = 0
    for c in cnt.values():
        if c % 2 == 1:
            t1 += 1
        elif c % 4 == 2:
            t2 += 1
    if H % 2 == 1 and W % 2 == 1:
        if t1 != 1:
            return False
        if t2 <= (H - 1) // 2 + (W - 1) // 2:
            return True
        return False
    else:
        if t1 != 0:
            return False
        if H % 2 == 1:
            if t2 <= W // 2:
                return True
            return False
        else:
            if t2 <= H // 2:
                return True
            return False


def main():
    # sys.stdin = open("sample.txt")
    print('YNeos'[not solve()::2])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

two = 0
one = 0
if H % 2 and W % 2:
    two = H + W - 2
    one = 1
elif H % 2:
    two = W 
elif W % 2:
    two = H


for i in al:
    if i % 2:
        one -= 1
        two -= (i % 4) - 1
    else:
        two -= i % 4

if two >= 0 and one == 0 and two % 4 == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
L = []
for i in range(h):
    L.append(input())
boo = []
for i in range(h):
    F = [False]*w
    boo.append(F)
numlist = []
cnt = 0
tate = 1
yoko = 1
if h == 1:
    if w == 1:
        numlist = [1]
    else:
        if w%2 != 0:
            for i in range(w//2):
                numlist.append(2)
            numlist.append(1)
        else:
            for i in range(w//2):
                numlist.append(2)
elif w == 1:
    if h%2 != 0:
        for i in range(h//2):
            numlist.append(2)
        numlist.append(1)
    else:
        for i in range(h//2):
            numlist.append(2)
else:
    while cnt != h*w:
        if boo[tate-1][yoko-1] == False:
            if h%2 == 1 and tate-1 == h//2:
                if w%2 == 1 and yoko-1 == w//2:
                    boo[tate-1][yoko-1] = True
                    numlist.append(1)
                    cnt += 1
                    yoko += 1
                else:
                    boo[tate-1][yoko-1] = True
                    boo[tate-1][w-yoko] = True
                    numlist.append(2)
                    cnt += 2
                    yoko += 1
            else:
                if w%2 == 1 and yoko-1 == w//2:
                    boo[tate-1][yoko-1] = True
                    boo[h-tate][yoko-1] = True
                    numlist.append(2)
                    cnt += 2
                    yoko += 1
                else:
                    boo[tate-1][yoko-1] = True
                    boo[h-tate][yoko-1] = True
                    boo[tate-1][w-yoko] = True
                    boo[h-tate][w-yoko] = True
                    numlist.append(4)
                    cnt += 4
                    yoko += 1
        else:
            yoko += 1
        if yoko == w:
            if tate != h:
                yoko = 1
                tate += 1
            else:
                break
list_alp = [0]*26
for i in range(h):
    for j in range(w):
        list_alp[ord(L[i][j])-97] += 1
temp = 0
flag = True
list_alp.sort()
list_alp.reverse()
numlist.sort()
numlist.reverse()
for i in range(len(numlist)):
    if list_alp[0] < numlist[temp]:
        flag = False
        break
    else:
        list_alp[0] -= numlist[temp]
        temp += 1
        list_alp.sort()
        list_alp.reverse()
if flag:
    if sum(list_alp) == 0:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Accepted

Solution code:
import collections

H, W = map(int, input().split())
A = []
for _ in range(H):
    A += list(input())
elements = collections.Counter([x % 4 for x in collections.Counter(A).values()])
c = [0]*4
for x in elements.keys():
    c[x] = elements[x]

ans = False
if H % 2 == 0 and W % 2 == 0:
    if c[1:] == [0, 0, 0]:
        ans = True

elif H % 2 != 0 and W % 2 != 0:
    if c[1] + c[3] == 1:
        if c[1] == 1:
            c[0] += 1
            c[1] = 0
        else:
            c[2] += 1
            c[3] = 0

        if c[1:] == [0, 0, 0] or c[2] <= (H + W)//2 - 1:
            ans = True 

elif H % 2 != 0:
    if c[1:] == [0, 0, 0] or (c[2] <= W//2 and c[1] + c[3] == 0):
        ans = True
else:
    if c[1:] == [0, 0, 0] or (c[2] <= H//2 and c[1] + c[3] == 0):
        ans = True

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

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W = map(int, input().split())
a = [input() for i in range(H)]
C = defaultdict(int)
for s in a:
    for c in s:
        C[c] += 1
m = [0]*4
for k in C:
    m[C[k]%4] += 1
if H&1 and W&1:
    if m[1]+m[3] == 1 and m[2] <= H//2+W//2-m[3]:
        print('Yes')
    else:
        print('No')
elif H&1==0 and W&1==0:
    if all([C[x]%4==0 for x in C]):
        print('Yes')
    else:
        print('No')
else:
    if H&1:
        H, W = W, H
    if m[1] == m[3] == 0 and m[2] <= H//2:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

import string
A = [chr(i) for i in range(ord("a"), ord("z")+1)]
B = {}
for i in range(26):
    B[A[i]] = i

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

D = [0] * 26
for i in range(h):
    for j in range(w):
        D[B[AA[i][j]]] += 1

E = [0, 0, 0]
for i in range(26):
    if D[i] % 2 > 0:
        E[2] += 1
    elif D[i] % 4 > 0:
        E[1] += 1

if C[2] == E[2] and C[1] >= E[1]:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int, input().split())
D = []
for _ in range(H):
    D.extend(list([v for v in input()]))
C = Counter(D)
L = list([v for i, v in C.most_common()])

g1 = sum(v % 2 for v in L)
g4 = sum(v//4 for v in L)

if g4 >= (W-(W % 2))*(H-(H % 2))//4 and g1 == H & 1 & W:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans in [True, False]:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    H, W = iip(False)

    A = []
    for i in range(H):
        A.extend([i for i in input()])

    d = count_elements(A)

    a = 0
    b = 0
    for i in d.values():
        if i % 4 == 1:
            a += 1
        elif i % 4 == 2:
            b += 1
        elif i % 4 == 3:
            a += 1
            b += 1

    ans = True

    h = H % 2 == 0
    w = W % 2 == 0

    #print(a, b)

    if h and w:
        if a == 0 and b == 0:
            return True
        else:
            return False

    elif w:
        if b <= W/2 and a == 0:
            return True
        else:
            return False

    elif h:
        if b <= H/2 and a == 0:
            return True
        else:
            return False

    else:
        if b <= (H+W)/2 -1 and a <= 1:
            return True
        else:
            return False


#####################################################ライブラリ集ここから

def iip(listed=True, num_only=True):  # 数字のinputをlistで受け取る
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_c
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


# 回文の二次元版
# 1次元回文→文字数が奇数だったら,一つの文字以外出現回数はすべて2の倍数。偶数だったら出現回数はすべて2の倍数
# 二次元では？
# H,Wがともに偶数なら→すべての文字の出現回数は4の倍数
# Hが奇数、Wが偶数なら→4の倍数でない要素を、真ん中に詰めていきたい(そのような要素がWについても回文になっているか評価)
# つまり4の倍数が(W*(H-1))個分ある かつ それ以外の要素は2の倍数ある
# Wが奇数、Hが偶数→↑WHをひっくり返すだけ
# W,Hがともに奇数→(W-1)*(H-1)個分ある かつ それ以外の要素は1つ以外2の倍数である

# 上記を一般化すると、二次元回文が満たすべき条件は、
# - 同一文字4個セットは(W-(W&1))*(H-(H&1))//4 個以上ある
# - 同一文字奇数個の要素はちょうどH&1&W個ある(両方奇数のとき1になる)
# - その他の要素はすべて2の倍数個である(ただしこの条件は2番めの条件に内包される)

from collections import Counter

H, W = read_ints()
cnt = Counter()
for _ in range(H):
    cnt.update(input())

# コーナーケース処理
# if H == 1 or W == 1:


num4 = 0
num1 = 0
for v in cnt.values():
    if v & 1:  # 条件2
        num1 += 1

    while v >= 4:  # 条件1の4文字セットを作る 4以上なら4個セットを作ることができる
        v -= 4
        num4 += 1

if num4 >= (W - (W & 1)) * (H - (H & 1)) // 4 and num1 == H & 1 & W:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
# CODE FESTIVAL 2017 qual A
# C - Palindromic Matrix
# https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_c
from collections import Counter
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in range(H)]
C = Counter(''.join(S))

a = H//2*W//2
b = H//2*(W % 2) + W//2*(H % 2)
c = (H % 2)*(W % 2)

for _ in range(c):
    for k, v in C.items():
        if v % 2 == 1 and v > 0:
            C[k] -= 1
            c -= 1
            break
b += c//2
for _ in range(b):
    for k, v in C.items():
        if v % 4 == 2 and v > 0:
            C[k] -= 2
            b -= 1
            break
a += b//2
for _ in range(a):
    for k, v in C.items():
        if v % 4 == 0 and v > 0:
            C[k] -= 4
            break
if sum(C.values()) == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import Counter

h,w = na()
c = Counter()

for i in range(h):
    c.update(ns())

c = list(c.values())

for i in range(len(c)):
    c[i] %= 4

v,x,y,z = c.count(0),c.count(1),c.count(2),c.count(3)

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

Submission status: Accepted

Solution code:
backet = [0]*(ord('z') - ord('a') + 1)
h,w = map(int,input().split())
for _ in range(h):
  a = list(input())
  for i in a:
    backet[ord(i) - ord('a')] += 1

mod = [0,0,0,0]
for i in backet:
  mod[i%4] += 1
ans = False
if h%2 and w%2:
  if mod[1] + mod[3] == 1 and (mod[2]+mod[3] - (h//2+w//2))%2 == 0 and mod[2]+mod[3] - (h//2+w//2) <= 0:
    ans = True
elif h%2:
  if mod[1]+mod[3] == 0 and (mod[2]+mod[3]-w//2)%2==0 and mod[2]+mod[3]-w//2<=0:
    ans = True
elif w%2:
  if mod[1]+mod[3] == 0 and (mod[2]+mod[3]-h//2)%2 == 0 and mod[2]+mod[3]-h//2 <= 0:
    ans = True
else:
  if mod[1] == mod[2] == mod[3] == 0:
    ans = True
if ans:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    h, w = LI()
    x = h & 1 and w & 1
    a = SR(h)
    d = defaultdict(int)
    for i in range(h):
        for j in range(w):
            d[a[i][j]] += 1
    one = 0
    two = 0
    for i in d.values():
        one += i & 1
        two += (i >> 1) & 1
    if x:
        if one == 1:
            if h + w - 2 >= two << 1:
                print("Yes")
            else:
                print("No")
        else:
            print("No")
    else:
        if one:
            print("No")
        else:
            x = (h & 1) * (w >> 1) + (w & 1) * (h >> 1)
            if x:
                if x >= two:
                    print("Yes")
                else:
                    print("No")
            else:
                if two:
                    print("No")
                else:
                    print("Yes")

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
h, w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))

tmp = []
for i in range(h):
    for j in a[i]:
        tmp.append(j)
#print(tmp)
c = collections.Counter(tmp)
tmp2 = list(set(tmp))
four = 0
two = 0
odd = 0
for i in tmp2:
    if c[i] % 4 == 0:
        four += 1
    elif c[i] % 2 == 0:
        two += 1
    else:
        odd += 1

if h % 2 == 1 and w % 2 == 1:
    if odd == 1 and two <= (h // 2 + w // 2):
        ans = "Yes"
    else:
        ans = "No"
elif h % 2 == 0 and w % 2 == 0:
    if two == 0 and odd == 0:
        ans = "Yes"
    else:
        ans = "No"
elif h % 2 == 0 and w % 2 == 1:
    if odd == 0 and two <= h // 2:
        ans = "Yes"
    else:
        ans = "No"
elif h % 2 == 1 and w % 2 == 0:
    if odd == 0 and two <= w // 2:
        ans = "Yes"
    else:
        ans = "No"
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dic = {}
for i in range(h):
    for j in range(w):
        if a[i][j] not in dic.keys():
            dic[a[i][j]] = 1
        else:
            dic[a[i][j]] += 1
group = {0:0, 1:0, 2:0, 3:0}
for v in dic.values():
    group[v%4] += 1
ans = 'Yes'
if group[1] + group[3] >= 2:
    ans = 'No'
else:
    if h&1 and w&1:
        if group[2] + group[3] > h//2 + w//2:
            ans = 'No'
    elif h&1 or w&1:
        if group[1] or group[3]:
            ans = 'No'
        elif group[2] > (h*w - ((h//2)*(w//2)*4))//2:
            ans = 'No'
    else:
        if group[1] or group[2] or group[3]:
            ans = 'No'
print(ans)