MEX のリンク集
MEX について、参考になる記事や資料をまとめました。
MEX(minimum excluded value)は、非負整数の集合に含まれない最小の非負整数です。たとえば 、、 です。長さ の列の MEX は 以下なので、 より大きい値は無視してよく、長さ の配列で「どの値が含まれるか」を数えれば で求まります。問題によっては「含まれない最小の正の整数」を MEX と呼ぶこともあるので、0 始まりか 1 始まりかを問題文で確かめてください。
MEX はゲームの問題にもよく出てきます。不偏ゲームの各局面の Grundy 数は「1 手で移れる局面の Grundy 数の MEX」で定義され、Sprague-Grundy の定理により、いくつかのゲームを並べたゲームの Grundy 数は各ゲームの Grundy 数の XOR になります。
値の追加・削除をしながら MEX を求めたいときは、各値の個数を数えておき、 から までの「含まれない値」を set に入れて最小値を取る方法や、値を添字にしたセグメント木の上で二分探索する方法があります。区間 の MEX を答えるクエリは、右端の順に処理して各値の最後の出現位置をセグメント木で持つ方法(オフライン)や、永続セグメント木(オンライン)で解けます。セグメント木そのものについては セグメント木のリンク集 も見てください。
まず読むもの
Section titled “まず読むもの”- Mexを計算する(magurofly、Scrapbox)
- 追加・削除をしながら MEX を求める方法として、区間 min のセグメント木を使う方法(含まれる値の位置を 、含まれない値の位置を自分自身の値にして全体の min を取る)と、下で紹介する「区間を set で管理するテク」の 2 つを短くまとめています。多重集合にするときは値ごとに個数を持つことにも触れています。コードはありません。
- mex のライブラリ化(saka_pon、Qiita)
- 要素数が 以下なら MEX も 以下なので、 のうち含まれない値だけを順序つき集合で持てばよい、という考え方から、追加・削除と MEX の取得を で行うクラスを作っています。多重集合版と、順序つき集合の代わりに削除可能な優先度付きキューを使う版もあります。コードは C# です。
MEX の求め方と管理
Section titled “MEX の求め方と管理”- 要素の追加・削除と mex を対数時間で処理するよ(えびちゃんの日記)
- 集合に含まれる連続した整数を 1 つの区間として
set<pair>で持ち、「 以上で集合に含まれない最小の整数」を求める方法です。値の上限に依存せず、区間の追加にも対応できます。手順は文章で説明していて、C++ と Rust のコードは AtCoder の提出へのリンクです。
- 集合に含まれる連続した整数を 1 つの区間として
- 「区間をsetで管理するやつ」をPythonでライブラリ化しました(hibit、Qiita)
- 上の記事の方法を、半開区間で管理する Python のクラスにしています。
sortedcontainersを使います。 - 記事の最後にある区間の追加・削除のコードは、著者が「ChatGPT に書かせた、verify が済み次第反映させる」と書いているもので、検証されていません。
- 上の記事の方法を、半開区間で管理する Python のクラスにしています。
Grundy 数(Sprague-Grundy の定理)
Section titled “Grundy 数(Sprague-Grundy の定理)”- 石取りゲーム(Nim)(いかたこのたこつぼ)
- Nim の必勝法とその証明、最後に取った方が負けの逆形ルール、一度に 個の山から取れる NimK を説明したあと、Grundy 数による一般化と、取れる石の数に上限・下限がある場合などの例を Grundy 数の表で追っています。
- 石の個数の XOR が の状態を「必勝形」(渡した側が勝つ形)と呼んでいます。受け取った側から見ると負けの状態なので、読むときに注意してください。
- tech005:NimとGrundy数(takeo1116)
- Nim の必勝法と Grundy 数の定義、Grundy 数の XOR についての性質を 1 ページで短くまとめています。証明やコードはありません。
- 競技プログラミングにおけるゲーム問題まとめ(はまやんはまやんはまやん)
- Nim、Grundy 数、後退解析、真似をする戦略、ミニマックス法などの手法ごとに、問題の一覧を集めたページです。説明は箇条書きで短いです。
- Grundy 数の定義が「遷移可能な状態の Grundy 数の中で最小の非負整数」となっていますが、正しくは「遷移先の Grundy 数に含まれない最小の非負整数」です。
区間 MEX のクエリ
Section titled “区間 MEX のクエリ”- Offline Range MEX queries in O(log n)(one_autum_leaf、Codeforces、英語)
- クエリを右端の順に処理し、各値の最後の出現位置を区間 min のセグメント木で持ちます。「最後の出現位置が より前」である最小の値をセグメント木の上で降りて探すと、それが区間 の MEX です。C++ のコードがあります。
- 例の数列 は、冒頭の制約 を満たしていません。 より大きい値は MEX に関係しないので、答えは変わりません。
- Collection of little techniques(-is-this-fft-、Codeforces、英語)
- 小さなテクニック集の「2. Avoiding logs in Mo’s algorithm」の節で、区間 MEX のクエリを Mo’s algorithm で解く例を扱っています。区間の端を動かすたびに
setを更新すると になるので、値を 個ずつのブロックに分けて、追加・削除を 、MEX の取得を にする方法を説明しています。
- 小さなテクニック集の「2. Avoiding logs in Mo’s algorithm」の節で、区間 MEX のクエリを Mo’s algorithm で解く例を扱っています。区間の端を動かすたびに
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”MEX や Grundy 数を扱う講座はまだありませんが、関連する講座があります。
- 競技プログラミング基本用語集
- 「4.10. mex」の節に、MEX の定義と例があります。多重集合や列にも同じ記号を使うこと、問題によっては正の整数で定義していることにも触れています。
- 永続セグメント木
- 過去のすべてのバージョンにアクセスできるセグメント木の講座です。MEX には触れていませんが、区間 MEX のクエリにオンラインで答えるときは、下の kopricky さんの実装のように、各接頭辞のバージョンを持つ永続セグメント木を使います。
- StaticRangeMexQuery(kopricky アルゴリズムライブラリ)
- 更新のない列で、区間 の MEX にオンラインで で答える C++ の実装です。
- 説明文ではフラクショナルカスケーディングを使うと書かれていますが、載っているコードは永続セグメント木を使っています。また、ページには「verify していません」と書かれています。
- intervals_set.cpp(drken1215/algorithm、GitHub)
- 区間を
setで管理する C++ の構造体で、get_mex(p)が 以上で含まれない最小の値を返します。区間に値を持たせて更新することもできます。ABC330 E などで verify されています。ドキュメントはなく、コード中のコメントだけです。
- 区間を
百科事典・英語の資料
Section titled “百科事典・英語の資料”- Mex (mathematics)(英語版 Wikipedia)
- 整列集合の部分集合の MEX として定義し、順序数を含む例、Sprague-Grundy の定理での使われ方、グラフの貪欲彩色での使われ方を説明しています。1 つの山の Nim や、一度に 3 個まで取れる Nim の Grundy 数の計算例があります。日本語版の記事はありません。
- Sprague–Grundy theorem(英語版 Wikipedia)
- 不偏ゲームの局面を集合として再帰的に表し、ゲームの和、局面の同値、定理の証明までを扱っています。抽象的な書き方で、記事の冒頭にも「技術的すぎる」という注意書きがあります。
- 日本語版は定理の内容を述べた数行だけの記事です。
- MEX (minimal excluded) of a sequence(cp-algorithms)
setを使う の方法と、真偽値の配列を使う の方法、要素を更新しながら MEX を求める方法(セグメント木で二分探索する方法の説明と、mapと「含まれない値のset」を使う C++ のクラス)を扱っています。長さ の列の MEX が 以下であることにも触れています。最後に練習問題の一覧があります。
- Sprague-Grundy theorem. Nim(cp-algorithms)
- Nim の必勝法の証明、逆形ルール、石を増やせる Nim の補題を使った Sprague-Grundy の定理の証明、ゲームが和に分かれるときの Grundy 数の計算、周期を探すことの有用性を説明しています。例として、1 列のマスに隣り合わないように × を置くゲームを扱っています。
- ABC245 B - Mex:数列の MEX を求める基本問題です。
- HHKB2020 C - Neq Min:先頭から 1 つずつ値を追加しながら、毎回 MEX を出力します。MEX は減らないので、前回の答えから増やしていけば全体で線形時間です。
- ABC290 C - Max MEX: 個の要素を選んだときの MEX の最大値を求めます。MEX が を超えないことに気づくのがポイントです。
- ABC330 E - Mex and Update:1 点更新のたびに数列全体の MEX を出力します。 より大きい値は無視して、含まれない値を
setなどで管理します。 - ABC272 E - Add and Mex:毎回 に を足したあとの MEX を求めます。各 が にいる回数は全体で調和級数の 回なので、その回だけを記録します。
- ABC194 E - Mex Min:長さ のすべての区間の MEX の最小値を求めます。区間を 1 つずつずらしながら、各値の個数を更新します。
- ABC368 F - Dividing Game:整数を自身以外の約数に置き換えるゲームで、各整数の Grundy 数を求めて XOR を取ります。
- ABC297 G - Constrained Nim 2:1 回に 個以上 個以下を取る Nim です。小さい場合の Grundy 数を計算して規則性を見つけます。
- 競プロ典型 90 問 031 - VS AtCoder(★6):白石と青石の個数の組ごとに Grundy 数を DP で求め、山ごとの XOR で勝敗を判定します。
- ABC206 F - Interval Game 2:区間を選ぶと左右の 2 つのゲームに分かれるので、範囲ごとの Grundy 数を区間 DP で求めます。
このブログの記事
Section titled “このブログの記事”- Blitz Round #25 A - Sum vs MEX
- MEX を「含まれない最小の正の整数」とする問題で、全体の MEX が必ず になることから が奇数なら不可能とし、偶数なら を最後に置いて途中の MEX をすべて にする順列を構成しています。