かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC194 E - Mex Min

問題はこちら

問題概要

長さ{N}の整数列{A}が与えられる.{A}の連続する長さ{M}区間すべてについてのmexのうち最小値を求めよ.

{1\leq M\leq N\leq 1.5×10^6}

解説


最初の区間についてmexを求めた後,区間をずらしながらすべての区間についてのmexを求める.区間をずらすとき,変化するのは区間の端の数のみ.したがって区間中の整数の数は区間ごとに{O(1)}でカウントできる.

mexは整数の集合により値が決まるのでsetうまく管理することで求めることができそう.

{\downarrow}

現在の区間の整数の集合を{S}とする.{S}の連続する整数の端をsetで持つ.

例として{S=\{1,2,3,4,6,8,9\}}とするとsetの中身は{1,4,6,8,9}となる.

f:id:kanpurin:20210307023027p:plain

{S}に整数を追加する場合

以下の図のように区間を隣り合った区間を接続する.隣に区間が無いなら追加した整数が区間の端になる.

f:id:kanpurin:20210307023955p:plain

{S}から整数を削除する場合

以下の図のように区間を分割する.削除する整数が区間の端である場合も同様に行う.

f:id:kanpurin:20210307024346p:plain

{S}のmexを求める

{0}がない場合は{0}が答え.

{0}がある場合は{0}を含む区間の右端の整数{+1}が答え.

ほかにも

上の解法のほかにもっと簡単なものとしてsetに{0}から{N}までをつっこんで{S}の整数をsetから削除する.このときset内の最小の整数が答えとなる.全部つっこむ分,上の解法より遅いが間に合う.

どちらも計算量は{O(N\log{N})}

公式解説ではmexとminの性質を用いて直接答えを求めていた.本解説の手法だと計算量は悪くなるがmexの列挙ができる.

提出プログラム

https://atcoder.jp/contests/abc194/submissions/20738573
https://atcoder.jp/contests/abc194/submissions/20740038

感想

問題文から素直な考え方で導かれる解法の解説を行った.実装は重くなるがいろいろ応用できそうな解法だと思う.