トップ > AtCoder > ABC272E - Add and Mex

ABC272E - Add and Mex

AtCoder AtCoder-Beginner Contest 計算量 計算量-調和級数 計算量-実は計算できる Mex Python

考え方

Editorial - AtCoder Beginner Contest 272
$N$個の整数に含まれない最小の非負整数は$0,1,...,N$のいずれか．

各$i$を考える．$m$回目の操作のあとで$A_{i} \in [0, N]$となる$m$の個数は，

\begin{aligned}
& 0 \leq A_{i} + m i \leq N \\
& \Leftrightarrow - \frac{A_{i}}{i} \leq m \leq \frac{N - A_{i}}{i}
\end{aligned}
により$O(N / i)$個．

したがって，すべての$i$について$A_{i} \in [0, N]$となる場合を調べると

\begin{aligned}
\sum_{i = 1}^{N} O(N / i)
=O(N\log N)
\end{aligned}
の計算量となる．

よって，

  • $1, 2,...,M$回目に現れる数をすべて調べて，回数ごとに保持しておき（$O(N\log N)$）
  • 各回数で保持した数を順に見ていって，現れないものを見つける（$O(N\log N)$）
とすればよい．

回答例

N, M = map(int, input().split())
A = list(map(int, input().split()))

memo = [set() for _ in range(M)]
for i in range(N):
    a = A[i]
    if a < 0:
        j = (- a // (i + 1)) - 1
        a += (- a // (i + 1)) * (i + 1)
    else:
        j = 0
        a += i + 1

    while j < M:
        if a > N: break
        memo[j].add(a)
        j += 1
        a += i + 1
    
for j in range(M):
    ans = 0
    while ans in memo[j]:
        ans += 1
    print(ans)


参考