モノイド
競プロで幾何じゃない数学で結構序盤から触れることになる割に結構難しい概念のひとつだが、ここでは競プロで最低限必要な部分だけしか触れないので、肩の力を抜いて読んでほしい。
モノイドとは
例えば、扱う範囲を非負整数に限って、bitwise XOR について考える。なお、bitwise XOR のことを以降$ \oplusと表記する。 ここで、任意の非負整数$ a, b, cについて
$ (a \oplus b) \oplus c = a \oplus (b \oplus c)
が成り立つ。このことを結合律という。
また、$ 0と任意の非負整数$ aについて
$ 0 \oplus a = a = a \oplus 0
が成り立つ。この時$ 0のことを単位元という。
このような時に、
(扱う値の範囲、演算そのもの、単位元)
の組をまとめてモノイドと呼ぶ。つまり
(非負整数, bitwise XOR, $ 0)
はモノイドである。
ちなみに「補演算があること」は条件に含まれない。稀に誤解されているケースを見かけるが。 モノイドの例
じゃあ掛け算とか足し算もモノイドだろ、と思ったかもしれない。
事実、それらはモノイドに出来る。
以下(値の範囲, 演算, 単位元)の形式でモノイドの例を挙げる。
(実数, 加算, $ 0)
(実数, 乗算, $ 1)
(非負整数, GCD, $ 0※$ \mathrm{gcd}(0, a) = a, a \neq 0と定める時)
(実数, $ \mathrm{min}, $ \inf) もちろん逆も然り
(非負整数, bitwise OR, $ 0)
使いどころ
競プロにおいては、もうほぼこの一点に限られる。