Problem:


Score : 700 points

Problem Statement

Takahashi is hosting an sports meet.
There are N people who will participate. These people are conveniently numbered 1 through N.
Also, there are M options of sports for this event. These sports are numbered 1 through M.
Among these options, Takahashi will select one or more sports (possibly all) to be played in the event.

Takahashi knows that Person i's j-th favorite sport is Sport A_{ij}.
Each person will only participate in his/her most favorite sport among the ones that are actually played in the event, and will not participate in the other sports.

Takahashi is worried that one of the sports will attract too many people.
Therefore, he would like to carefully select sports to be played so that the number of the participants in the sport with the largest number of participants is minimized.
Find the minimum possible number of the participants in the sport with the largest number of participants.

Constraints

1 \leq N \leq 300

1 \leq M \leq 300

A_{i1} , A_{i2} , ... , A_{iM} is a permutation of the integers from 1 to M.

Input

Input is given from Standard Input in the following format:

N M
A_{11} A_{12} ... A_{1M}
A_{21} A_{22} ... A_{2M}
:
A_{N1} A_{N2} ... A_{NM}

Output

Print the minimum possible number of the participants in the sport with the largest number of participants.

Sample Input 1

4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1

Sample Output 1

2

Assume that Sports 1, 3 and 4 are selected to be played. In this case, Person 1 will participate in Sport 1, Person 2 in Sport 3, Person 3 in Sport 3 and Person 4 in Sport 4.
Here, the sport with the largest number of participants is Sport 3, with two participants.
There is no way to reduce the number of participants in the sport with the largest number of participants to 1. Therefore, the answer is 2.

Sample Input 2

3 3
2 1 3
2 1 3
2 1 3

Sample Output 2

3

Since all the people have the same taste in sports, there will be a sport with three participants, no matter what sports are selected.
Therefore, the answer is 3.



Sample input:
4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

input1 = input("").split(" ")
N = int(input1[0])
M = int(input1[1])
temp = [ input() for _ in range(N) ]
A = []
for i in range(N):
	A.append(list(map(int,temp[i].split(" "))))

A = np.array(A)
result = N

for j in range(M):
	top = A[:,0]
	c = Counter(list(top))
	most = c.most_common(1)
	mode = most[0][0]
	count = most[0][1]

	if result > count:
		result = count
	if count == 1:
		break

	for i in range(N):
		temp = np.delete(A[i], np.where(A[i] == mode)[0])
		A[i] = np.append(temp,0)

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

input1 = input("").split(" ")
N = int(input1[0])
M = int(input1[1])
temp = [ input() for _ in range(N) ]
A = []
for i in range(N):
	A.append(list(map(int,temp[i].split(" "))))

A = np.array(A)
result = N

for j in range(M):
	top = A[:,0]
	c = Counter(list(top))
	most = c.most_common(1)
	mode = most[0][0]
	count = most[0][1]

	if result > count:
		result = count

	for i in range(N):
		temp = np.delete(A[i], np.where(A[i] == mode)[0])
		A[i] = np.append(temp,0)

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, M=map(int, input().split())
m=[]
ans = 300

for i in range(N):
    m.append(list(map(int,input().split())))


def search(ln):
    #l = []
    cnt = Counter()
    for r in m:
        for col in r:
            if col in ln:
                cnt[col] += 1
                break
    s,c = cnt.most_common(1)[0]
    global ans
    if c < ans:
        ans = c
    ln.remove(s)
    if len(ln) == 0:
        return 
    search(ln)
search(list(range(1, M+1)))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, M=map(int, input().split())
m=[]
ans = 300

for i in range(N):
    m.append(list(map(int,input().split())))


def search(ln):
    l = []
    for r in m:
        for col in r:
            if col in ln:
                l.append(col)
                break
    s,c = Counter(l).most_common(1)[0]
    global ans
    if c < ans:
        ans = c
    ln.remove(s)
    if len(ln) == 0:
        return 
    search(ln)
search(list(range(1, M+1)))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = input().split(' ');
n = int(n)
m = int(m)
a = [[int(num) for num in input().split(' ')] for _ in range(n)]

sports = [i + 1 for i in range(m)]

min = 300
for _ in range(m):
    dict = {i: 0 for i in sports}
    for player in a:
        for num in player:
            if num in sports:
                dict[num] += 1
                break
    p = 0
    q = 0
    for i in sports:
        if dict[i] > q:
            p = i
            q = dict[i]
    if q < min:
        min = q
    sports.remove(p)

print(min)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = input().split(' ');
n = int(n)
m = int(m)
a = [[int(num) for num in input().split(' ')] for _ in range(n)]

sports = [list(itertools.combinations([num + 1 for num in range(m)], i + 1))
          for i in range(m)]

min = 300
for combs in sports:
    for comb in combs:
        dist = {i: 0 for i in comb}
        for player in a:
            for num in player:
                if num in comb:
                    dist[num] += 1
                    break
        max = 0
        for key in dist:
            if dist[key] > max:
                max = dist[key]
        if max < min:
            min = max

print(min)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))

heap = [(N, (i,)) for i in range(1,M+1)]
heapq.heapify(heap)

def maxparticipants(l):
	L = [[A[j].index(i) for i in l] for j in range(N)]
	L = [A[j][min(L[j])] for j in range(N)]
	m = 0
	for i in range(1,M+1):
		m = max(m, L.count(i))
	return m

participants = N
searched = []
while len(heap) > 0:
	case = heapq.heappop(heap)
	p = case[0]
	c = case[1]

	if c in searched:
		continue

	searched.append(c)
	tmp = list(c)

	for i in range(1,M+1):
		l = [x for x in tmp]
		if i in c:
			continue
		l.append(i)
		l.sort()
		n = maxparticipants(l)
		if n <= p:
			if n < participants:
				participants = n
			heapq.heappush(heap, (n, tuple(l)))

print(participants)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
arys = []
for i in range(N):
    tmp = input()
    ary = [int(a) - 1 for a in tmp.split()]
    arys.append(ary)


s = set([i for i in range(M)])
min_num = None
while len(s) > 0:
    dic = {}
    for ary in arys:
        del_i = None
        for i, a in enumerate(ary):
            if a in s:
                if a not in dic:
                    dic[a] = 1
                else:
                    dic[a] += 1
                break
            del_i = i
        if del_i is not None:
            ary = ary[del_i + 1:]
    max_v = None
    max_k = None
    for k, v in dic.items():
        if max_v is None or max_v < v:
            max_v = v
            max_k = k
    if min_num is None or min_num > max_v:
        min_num = max_v
    s.remove(max_k)
print(min_num)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

R = {}
ans = N
cnt = [0] * N

for i in range(M):
  L = [0] * (M + 1)
  for j in range(N):
    while A[j][cnt[j]] in R:
      cnt[j] += 1
    L[A[j][cnt[j]]] += 1
  ma = 0
  man = L[0]
  for j in range(M + 1):
    if man < L[j]:
      ma = j
      man = L[j]
  ans = min(ans, man)
  R[ma] = 1

print(ans)

Submission status: Accepted

Solution code:
# chokudaiブログの典型力の話を意識しつつ考えたら思いついた!

# 「ある集合の部分集合の中で、〜〜〜の値が最小になるものを求めよ」のパターン
# 愚直にやると2^Nを調べねばならず無理。
# したがって「一部を調べればよい」に帰着するのが多いだろう。
# 何らかの形でソートしておいて、空集合から1つずつ付け加えるとか。全体集合から1つずつ取り去るとか。

# 今回は全体集合から1つずつ取り去るのを考えるとできる。
# 全体集合である競技m0が最多の人数p0人を集めたとする。
# すると、全ての部分集合のうち「m0を含む集合」を考えると、競技m0は必ずp0人以上集まるので解もp0以上。
# ここで「m0を含む集合」について一気に計算できていることに注意! 一撃で多数の集合について計算が終わる。
# 次に全体集合からm0を取り去ったものを考える。
# ここである競技m1が最多の人数p1人を集めたとする。すると……以下同様。
# なお複数種目の競技が同率1位になった場合は全て一度に取り除いて良い。
# これで空集合までやって、最大が最小のものを出力すればOK! 

n, m = list(map(int, input().split()))
preference = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)] # 1-index → 0-index

ans = n
held_sports = set(range(m))

while held_sports:
    # 各競技に参加する人数を求める
    parti = [0] * m
    for pref in preference:
        for s in pref:
            if s in held_sports:
                parti[s] += 1
                break
    
    temp = max(parti)
    ans = min(ans, temp)
    # 集合から最大人数を取った要素を除外
    indices = [i for i,val in enumerate(parti) if val == temp]
    held_sports = held_sports - set(indices)

print(ans)

Submission status: Accepted

Solution code:
# chokudaiブログの典型力の話を意識しつつ考えたら思いついた!

# 「ある集合の部分集合の中で、〜〜〜の値が最小になるものを求めよ」のパターン
# 愚直にやると2^Nを調べねばならず無理。
# したがって「一部を調べればよい」に帰着するのが多いだろう。
# 何らかの形でソートしておいて、空集合から1つずつ付け加えるとか。全体集合から1つずつ取り去るとか。

# 今回は全体集合から1つずつ取り去るのを考えるとできる。
# 全体集合である競技m0が最多の人数p0人を集めたとする。
# すると、全ての部分集合のうち「m0を含む集合」を考えると、競技m0は必ずp0人以上集まるので解もp0以上。
# ここで「m0を含む集合」について一気に計算できていることに注意! 一撃で多数の集合について計算が終わる。
# 次に全体集合からm0を取り去ったものを考える。
# ここである競技m1が最多の人数p1人を集めたとする。すると……以下同様。
# なお複数種目の競技が同率1位になった場合は全て一度に取り除いて良い。
# これで空集合までやって、最大が最小のものを出力すればOK! 

n, m = list(map(int, input().split()))
preference = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)] # 1-index → 0-index

ans = n
held_sports = set(range(m))

while held_sports:
    # 各競技に参加する人数を求める
    parti = [0] * m
    for pref in preference:
        for s in pref:
            if s in held_sports:
                parti[s] += 1
                break
    
    temp = max(parti)
    ans = min(ans, temp)
    # 集合から最大人数を取った要素を除外
    for idx, par in enumerate(parti):
        if par == temp:
            held_sports.remove(idx)

print(ans)

Submission status: Accepted

Solution code:
# chokudaiブログの典型力の話を意識しつつ考えたら思いついた!

# 「ある集合の部分集合の中で、〜〜〜の値が最小になるものを求めよ」のパターン
# 愚直にやると2^Nを調べねばならず無理。
# したがって「一部を調べればよい」に帰着するのが多いだろう。
# 何らかの形でソートしておいて、空集合から1つずつ付け加えるとか。全体集合から1つずつ取り去るとか。

# 今回は全体集合から1つずつ取り去るのを考えるとできる。
# 全体集合である競技m0が最多の人数p0人を集めたとする。
# すると、全ての部分集合のうち「m0を含む集合」を考えると、競技m0は必ずp0人以上集まるので解もp0以上。
# ここで「m0を含む集合」について一気に計算できていることに注意! 一撃で多数の集合について計算が終わる。
# 次に全体集合からm0を取り去ったものを考える。
# ここである競技m1が最多の人数p1人を集めたとする。すると……以下同様。
# なお複数種目の競技が同率1位になった場合は全て一度に取り除いて良い。
# これで空集合までやって、最大が最小のものを出力すればOK! 

n, m = list(map(int, input().split()))
preference = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)] # 1-index → 0-index

ans = n
held_sports = set(range(m))

while held_sports:
    # 各競技に参加する人数を求める
    parti = [0] * m
    for pref in preference:
        for s in range(m):
            if pref[s] in held_sports:
                parti[pref[s]] += 1
                break
    
    temp = max(parti)
    ans = min(ans, temp)
    # 集合から最大人数を取った要素を除外
    for idx, par in enumerate(parti):
        if par == temp:
            held_sports.remove(idx)

print(ans)

Submission status: Accepted

Solution code:
# chokudaiブログの典型力の話を意識しつつ考えたら思いついた!

# 「ある集合の部分集合の中で、〜〜〜の値が最小になるものを求めよ」のパターン
# 愚直にやると2^Nを調べねばならず無理。
# したがって「一部を調べればよい」に帰着するのが多いだろう。
# 何らかの形でソートしておいて、空集合から1つずつ付け加えるとか。全体集合から1つずつ取り去るとか。

# 今回は全体集合から1つずつ取り去るのを考えるとできる。
# 全体集合である競技m0が最多の人数p0人を集めたとする。
# すると、全ての部分集合のうち「m0を含む集合」を考えると、競技m0は必ずp0人以上集まるので解もp0以上。
# ここで「m0を含む集合」について一気に計算できていることに注意! 一撃で多数の集合について計算が終わる。
# 次に全体集合からm0を取り去ったものを考える。
# ここである競技m1が最多の人数p1人を集めたとする。すると……以下同様。
# なお複数種目の競技が同率1位になった場合は全て一度に取り除いて良い。
# これで空集合までやって、最大が最小のものを出力すればOK! 

n, m = list(map(int, input().split()))
preference = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)] # 1-index → 0-index

ans = n
held_sports = set(range(m))

while held_sports:
    # 各競技に参加する人数を求める
    parti = [0] * m
    for person in range(n):
        for s in range(m):
            if preference[person][s] in held_sports:
                parti[preference[person][s]] += 1
                break
    
    temp = max(parti)
    ans = min(ans, temp)
    # 集合から最大人数を取った要素を除外
    for idx, par in enumerate(parti):
        if par == temp:
            held_sports.remove(idx)

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    A = [LI() for _ in range(N)]

    ctr = [0] * N

    sp = [0] * (M+1)
    for i in range(N):
        sp[A[i][ctr[i]]] += 1
    ans = max(sp)

    for _ in range(M-1):
        mi = sp.index(max(sp))
        sp[mi] = -1
        for i in range(N):
            if A[i][ctr[i]] == mi:
                while sp[A[i][ctr[i]]] < 0:
                    ctr[i] += 1
                sp[A[i][ctr[i]]] += 1
        ans = min(ans,max(sp))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    A = [LI() for _ in range(N)]

    ctr = [0] * N

    sp = [0] * (M+1)
    for i in range(N):
        sp[A[i][ctr[i]]] += 1
    ans = max(sp)

    for _ in range(M-1):
        m = 0
        mi = -1
        for i in range(1,M+1):
            if sp[i] > m:
                m = sp[i]
                mi = i
        sp[mi] = -1
        for i in range(N):
            if A[i][ctr[i]] == mi:
                while sp[A[i][ctr[i]]] < 0:
                    ctr[i] += 1
                sp[A[i][ctr[i]]] += 1
        ans = min(ans,max(sp))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def meguru_bisect(ng, ok):
    """
    初期値のng,okを受け取り, check=>Trueを満たす最大値(最小値)を返す
    条件を満たす最大値を求める場合、初期値は(ng:上限の外, ok:下限の外)   例) 10**9+1, -1
    条件を満たす最小値を求める場合、初期値は(ng:下限の外, ok:上限の外)   例) -1, 10**9+1
    上限の外や下限の外が返ってくる場合は条件を満たす値が範囲内になかったことを示すので、例外処理が必要
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok

def check(x):
    index = defaultdict(int)
    disused = set()
    while True:
        count = defaultdict(int)
        for i in range(n):
            while A[i][index[i]] in disused:
                index[i] += 1
                if index[i] >= m:
                    return False
            count[A[i][index[i]]] += 1
        max_count = max(count.values())
        if max_count <= x:
            return True
        else:
            disused.add([key for key, value in count.items() if value == max_count][0])

n, m = (int(x) for x in input().split())
A = [list(int(x) for x in input().split()) for _ in range(n)]
ans = meguru_bisect(0, n + 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")
for i in range(m):
    c = Counter([a[i][0] for i in range(n)])
    x, y = c.most_common()[0]
    ans = min(ans, y)
    for i in range(n):
        a[i].remove(x)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
count = [0]*(m+1)
for i in a:
    count[i[0]] += 1
l = [0]*n
ans = max(count)
s = set()
for i in range(m-1):
    M = max(count)
    ind = count.index(M)
    s.add(ind)

    for j in range(n):
        if a[j][l[j]] == ind:

            count[ind] -= 1
            while a[j][l[j]] in s:
                l[j] += 1
            count[a[j][l[j]]] += 1
    ans = min(ans,max(count))

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    ans = n
    st = set(i for i in range(1, m+1))
    while len(st) > 1:
        dic = {v:0 for v in st}
        for i in range(n):
            for v in a[i]:
                if v in st:
                    dic[v] += 1
                    break
        tmp = max(dic.values())
        if ans > tmp:
            ans = tmp
        for key in dic.keys():
            if dic[key] == tmp:
                st.remove(key)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
def A_count():
    cnt = [0]*m
    for la in A:
        for a in la:
            if use[a]:
                cnt[a]+=1
                break
    heap = []
    for i in range(m):
        if use[i]:
            hq.heappush(heap,(-cnt[i],i))
    return heap

n,m = ma()
A = []
for i in range(n):
    A.append(list(map(lambda x:int(x)-1,input().split())))
ans = 10**9
use = [True]*m
#print(A)
for i in range(m):
    heap = A_count()
    mx,a = hq.heappop(heap)
    ans = min(ans,-mx)
    use[a]=False
print(ans)

Submission status: Accepted

Solution code:
def isok(k):
  b=[i[::-1] for i in a]
  d=[0]*(m+1)
  while all(b):
    flag=1
    c=[0]*(m+1)
    for i in range(n):
      c[b[i][-1]]+=1
    for i in range(n):
      if c[b[i][-1]]>k or d[b[i][-1]]:
        d[b[i][-1]]=1
        b[i].pop()
        flag=0
    if flag:break
  return all(b)
def bsearch(a):
  ok=n
  ng=-1
  while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if isok(mid):ok=mid
    else:ng=mid
  return ok
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
print(bsearch(a))

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
A=[]
for i in range(N):
  d=list(map(int, input().split()))
  A.append(d)
S=[1]*M
num=[0]*N
ans=N
for i in range(M):
  cnt=[0]*M
  for j in range(N):
    d=A[j][num[j]]
    while S[d-1]==0:
      num[j]+=1
      d=A[j][num[j]]
    cnt[d-1]+=1
  e=max(cnt)
  ans=min(e,ans)
  f=cnt.index(e)
  S[f]=0
print(ans)

Submission status: Accepted

Solution code:
def dfs(s):
    global ans
    if len(s)==M:
        return
    cnt=[0]*M
    for i in range(N):
        for j in range(M):
            if A[i][j] in s:
                continue
            cnt[A[i][j]]+=1
            break
    p=-1
    m=0
    for i in range(M):
        if cnt[i]>m:
            m=cnt[i]
            p=i
    ans=min(ans,m)
    s.add(p)
    dfs(s)
    return
N,M=map(int,input().split())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]

ans=float('inf')
dfs(set())
print(ans)

Submission status: Accepted

Solution code:
import sys

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


def main():
    n, m = map(int, readline().split())
    a = []
    for i in range(n):
        a.append(list(map(int, readline().split())))

    ans = INF
    for _ in range(m):
        cnt = [0] * (m + 1)
        for i in range(n):
            cnt[a[i][0]] += 1
        max_cnt = max(cnt)
        ans = min(ans, max_cnt)
        max_num = cnt.index(max_cnt)
        for i in range(n):
            a[i].remove(max_num)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = f_inf


def resolve():
    def dfs(remove):
        global res
        if len(remove) == m:
            return

        cnt = [0] * m
        ma = -f_inf
        target = None
        for i in range(n):
            for j in range(m):
                if A[i][j] not in remove:
                    cnt[A[i][j] - 1] += 1
                    if ma < cnt[A[i][j] - 1]:
                        ma = cnt[A[i][j] - 1]
                        target = A[i][j]
                    break

        remove.add(target)
        res = min(res, ma)
        dfs(remove)

    n, m = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(n)]

    dfs(set())
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

N,M = map(int,readline().split())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))[::-1]

# 末尾についている数字をカウントするdictionary
from collections import defaultdict
counter = defaultdict(int)

# すでに消去済みのスポーツを管理する集合
removed = set()

# まず末尾の数字をカウントする
for i in range(N):
  counter[A[i][-1]] += 1
  
# 最も登場回数が大きい数字を特定する
target = max(counter, key = counter.get)

ans = max(counter.values()) # 現時点での答え

while len(removed) < M - 1:
  # targetを末尾に持っている数について、取り除く
  for i in range(N):
    if len(A[i]) == 0:
      continue
    if A[i][-1] == target:
      A[i].pop()
      counter[target] -= 1
      while len(A[i]) > 0:
        if A[i][-1] in removed:
          A[i].pop()
        else:
          counter[A[i][-1]] += 1
          break
  removed.add(target)
  
  target = max(counter, key = counter.get)
  now = max(counter.values())
  if ans > now:
    ans = now
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque,Counter
n,m=map(int,input().split())
a=[deque(list(map(int,input().split()))) for _ in range(n)]
ans=n
no=set(())
while len(no)<m:
  for i in range(n):
    while a[i][0] in no:
      a[i].popleft()
  top=[a[i][0] for i in range(n)]
  ctop=Counter(top)
  mm=max(ctop.values())
  ans=min(ans,mm)
  for c in ctop:
    if ctop[c]==mm:
      no.add(c)
print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  N,M=map(int,input().split())
  A=[list(map(int,input().split())) for i in range(N)]
  ans=N
  s=set()
  for i in range(M-1):
    d=[0]*M
    for j in range(N):
      for k in range(M):
        if A[j][k]-1 in s:
          continue
        else:
          d[A[j][k]-1]+=1
          break
    ans=min(ans,max(d))
    s.add(d.index(max(d)))
  print(ans)
main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = [None]*n
d = [None]*n
from collections import Counter
for i in range(n):
    a[i] = list(map(lambda x: int(x)-1, input().split()))
    d[i] = a[i][0]

ans = float("inf")
used = [True] * m
num = m
while True:
    c = Counter(d)
#     print(c, used)
    mv, mk = max((v,k) for k,v in c.items())
#     print(mv, mk)
    ans = min(ans, mv)
    used[mk] = False
    num -= 1
    if num==0:
        break
    for i in range(n):
        if not used[d[i]]:
            for j in range(m):
                if used[a[i][j]]:
                    d[i] = a[i][j]
                    break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from typing import Optional


class DeletableDeque:
    """Deletable Deque: a deque that supports lazy deletion of values."""

    __slots__ = ["_set", "_deque"]

    def __init__(self, *initial_values: int) -> None:
        self._set = set()
        self._deque = deque([])

        if initial_values:
            for v in initial_values:
                self.append(v)

    @property
    def topleft(self) -> Optional[int]:
        """Return the leftmost value from the deque.
        If the deque is empty, None is returned.
        """
        while self._deque and self._deque[0] not in self._set:
            self._deque.popleft()
        if not self._deque:
            return None
        return self._deque[0]

    def append(self, value: int) -> None:
        """Append value to the right side of the deque."""
        if value in self._set:
            return
        self._set.add(value)
        self._deque.append(value)

    def delete(self, value: int) -> None:
        """Delete value from the deque."""
        if value not in self._set:
            return
        self._set.discard(value)


def agc018_b():
    # https://atcoder.jp/contests/agc018/tasks/agc018_b
    import sys
    from collections import Counter

    readline = sys.stdin.buffer.readline

    N, M = map(int, readline().split())
    A = [DeletableDeque(*map(int, readline().split())) for _ in range(N)]

    res = 301
    for _ in range(M):
        cnt = Counter(a.topleft for a in A)
        popular_sport = max(cnt, key=cnt.get)
        res = min(res, cnt[popular_sport])
        for a in A:
            a.delete(popular_sport)

    print(res)


if __name__ == "__main__":
    agc018_b()

Submission status: Accepted

Solution code:
from collections import deque
from typing import Optional


class DeletableDeque:
    """Deletable Deque: a deque that supports lazy deletion of values."""

    __slots__ = ["_set", "_deque"]

    def __init__(self, *initial_values: int) -> None:
        self._set = set()
        self._deque = deque([])

        if initial_values:
            for v in initial_values:
                self.append(v)

    @property
    def topleft(self) -> Optional[int]:
        """Return the leftmost value from the deque.
        If the deque is empty, None is returned.
        """
        while self._deque and self._deque[0] not in self._set:
            self._deque.popleft()
        if not self._deque:
            return None
        return self._deque[0]

    def append(self, value: int) -> None:
        """Append value to the right side of the deque."""
        if value in self._set:
            return
        self._set.add(value)
        self._deque.append(value)

    def delete(self, value: int) -> None:
        """Delete value from the deque."""
        if value not in self._set:
            return
        self._set.discard(value)


def agc018_b():
    # https://atcoder.jp/contests/agc018/tasks/agc018_b
    import sys
    from collections import Counter

    readline = sys.stdin.buffer.readline

    N, M = map(int, readline().split())
    A = [DeletableDeque(*map(int, readline().split())) for _ in range(N)]

    res = 301
    for _ in range(M):
        cnt = Counter([a.topleft for a in A])
        popular_sport = max(cnt, key=cnt.get)
        res = min(res, cnt[popular_sport])
        for a in A:
            a.delete(popular_sport)

    print(res)


if __name__ == "__main__":
    agc018_b()

Submission status: Accepted

Solution code:
from collections import deque
from typing import Optional


class DeletableDeque:
    """Deletable Deque: a deque that supports lazy deletion of values."""

    __slots__ = ["_set", "_deque"]

    def __init__(self, *initial_values: int) -> None:
        self._set = set()
        self._deque = deque([])

        if initial_values:
            for v in initial_values:
                self.append(v)

    def __contains__(self, value: int) -> bool:
        return value in self._set

    def __len__(self) -> int:
        return len(self._set)

    @property
    def is_empty(self) -> bool:
        """Return whether the deque has no values or not."""
        return len(self) == 0

    @property
    def top(self) -> Optional[int]:
        """Return the rightmost value from the deque.
        If the deque is empty, None is returned.
        """
        while self._deque and self._deque[-1] not in self._set:
            self._deque.pop()
        if not self._deque:
            return None
        return self._deque[-1]

    @property
    def topleft(self) -> Optional[int]:
        """Return the leftmost value from the deque.
        If the deque is empty, None is returned.
        """
        while self._deque and self._deque[0] not in self._set:
            self._deque.popleft()
        if not self._deque:
            return None
        return self._deque[0]

    def pop(self) -> Optional[int]:
        """Pop and return the rightmost value from the deque.
        If the deque is empty, None is returned.
        """
        while self._deque and self._deque[-1] not in self._set:
            self._deque.pop()
        if not self._deque:
            return None
        res = self._deque.pop()
        self._set.discard(res)
        return res

    def popleft(self) -> Optional[int]:
        """Pop and return the leftmost value from the deque.
        If the deque is empty, None is returned.
        """
        while self._deque and self._deque[0] not in self._set:
            self._deque.popleft()
        if not self._deque:
            return None
        res = self._deque.popleft()
        self._set.discard(res)
        return res

    def append(self, value: int) -> None:
        """Append value to the right side of the deque."""
        if value in self._set:
            return
        self._set.add(value)
        self._deque.append(value)

    def appendleft(self, value: int) -> None:
        """Append value to the left side of the deque."""
        if value in self._set:
            return
        self._set.add(value)
        self._deque.appendleft(value)

    def delete(self, value: int) -> None:
        """Delete value from the deque."""
        if value not in self._set:
            return
        self._set.discard(value)


def agc018_b():
    # https://atcoder.jp/contests/agc018/tasks/agc018_b
    import sys
    from collections import defaultdict

    readline = sys.stdin.buffer.readline

    N, M = map(int, readline().split())
    A = [DeletableDeque(*list(map(int, readline().split()))[::-1]) for _ in range(N)]

    res = 301
    for _ in range(M):
        cnt = defaultdict(int)
        for a in A:
            cnt[a.top] += 1

        popular_sport = max(cnt, key=cnt.get)
        res = min(res, cnt[popular_sport])
        for a in A:
            a.delete(popular_sport)

    print(res)


if __name__ == "__main__":
    agc018_b()