Статья Автор: Лебедев Дмитрий Алексеевич

Находим MEX

Определение
† MEX (minimum excludant) массива целых чисел определяется как наименьшее целое неотрицательное число,
которое не встречается в массиве. Например:

MEX массива [2,2,1] равен 0, потому что 0 не принадлежит массиву.
MEX массива [3,1,0,1] равен 2, потому что 0 и 1 принадлежат массиву, а 2 — нет.
MEX массива [0,3,1,2] равен 4, потому что 0, 1, 2 и 3 принадлежат массиву, а 4 — нет.

Из определения несложно понять, что

\(MEX(A) \leq len(A)\)
\(MEX(A) \leq max(A) + 1\)
\(B \in A => MEX(B) \leq MEX(A)\)
\(MEX (A) = MEX(set(A))\) - то есть, удаление повторов не изменяет MEX

Это позволяет для нахождения MEX использовать два подхода:

from random import randint as rnd
from time import process_time as prt
def MEX_1(A):
  k  = min(len(A), max(A) + 1) # определяем ограничения на MEX(A) 
  B = [0] * (k+1) # создаем список для маркировки
  for x in A :
    if x < k : B[x] += 1
  for i in range(k+1) : 
    if B[i] == 0 : return i
def MEX_2a(A):
  B = sorted(set(A)) # удаление дублей, MEX(A) = MEX(B), сортировка
  if B[0] > 0 : return 0 # проверка левого края
  k = len(B) # МЕХ(B) не больше k-1
  if B[k-1] == k - 1 : return k # проверка правого края
  L, R = 0, k # бинарный поиск
  while R - L > 1:
    i = (L + R) // 2
    if B[i] > i : R = i
    else: L = i
  return L + 1    
def MEX_2b(A):
  B = set(A) # удаление дублей, MEX(A) = MEX(B)
  k = len(B) # МЕХ(B) не больше k-1
  return min(set(range(k+1)) - B) # из набора 0, 1, ... k-1 удалили набор B и взяли минимальный 
def fx(k, Z):
  while True :
    x = rnd(0,k) 
    if not x in Z : return x
k, n = map(int, input().split()) # k - мощность алфавита, n - длина последовательности
Z = set(int(i) for i in input().split()) # запреты, определяет ответ (если n >> k)
A = [fx(k, Z) for _ in range(n)]
t0 = prt(); ans1 = MEX_1(A); t1 = prt()- t0
t0 = prt(); ans2a = MEX_2a(A); t2a = prt()- t0
t0 = prt(); ans2b = MEX_2b(A); t2b = prt()- t0
print(f'{ans1 == ans2a == ans2b} {t1=} {t2a=} {t2b=} {ans1=} {ans2a=} {ans2b=}')

Рассмотрим следующую задачу (Задача на codeforces. MEX. Игра -1)

Алиса и Боб играют в очередную игру на массиве a длины n. Алиса начинает с пустого массива c. Оба игрока ходят по очереди, причем Алиса начинает первой.

В свой ход Алиса выбирает один элемент из a, добавляет его в c, а затем удаляет из a.

В свой ход Боб выбирает один элемент из a, а затем удаляет его из a.

Игра заканчивается, когда массив a становится пустым. Счет игры определяется как MEX† элементов c. Алиса хочет максимизировать счет игры, а Боб — минимизировать его. Найдите итоговый счет игры, если оба игрока играют оптимально.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤2⋅104) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число n (1≤n≤2⋅105).

Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (0≤ai<n).

Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105.

Выходные данные

Для каждого набора входных данных найдите счет игры, если оба игрока играют оптимально.

Для решения попробуем определить

Множество уникальных элементов A
МЕХ(A)

Найдем ответ, сравнивая эти объекты

from random import randint as rnd
def solve(A) :
  B, C = set(), set() # B - множество всех, C - множество повторных
  for x in A :
    if x in B : C.add(x)
    else : B.add(x)
  k = len(B) + 1    
  D = set(x for x in B - C if x < k) # D - множество уникальных
  print(f'{B=}\n{C=}\n{D=}')
  ma = min(set(range(len(B)+1)) - B)
  if len (D) < 2 : return ma
  
  D = sorted(D)
  return min(ma, D[1])

k, n = rnd (0, 10), rnd (5, 20)
A = [rnd(0, k) for _ in range(n)]
try :
  ans = solve(A)
  print(f'Для набора {A} {ans=}')
except:
  print(f'{n=} {k=} {A}')

from random import randint as rnd
from time import process_time as prt
def solve(A) :
  B, C = set(), set() # B - множество всех, C - множество повторных
  for x in A :
    if x in B : C.add(x)
    else : B.add(x)
  k = len(B) + 1    
  D = set(x for x in B - C if x < k) # D - множество уникальных
  print(f'{B=}\n{C=}\n{D=}')
  ma = min(set(range(len(B)+1)) - B)
  if len (D) < 2 : return ma
  
  D = sorted(D)
  return min(ma, D[1])

k, n = rnd (0, 10), rnd (5, 20)
k, n = 10**3, 2*10**7
A = [rnd(0, k) for _ in range(n)]
t =prt()
b = sorted(set(A))
print(f' {prt() - t}')

Печать