お知らせ Zennに移植しました。今後こちらの記事は更新されず、Zennの方のみ更新します。
zenn.dev
この記事では競技プログラミングと群論に関する解説をします。競技プログラミングの問題を群論という立場から見ることで、新たな視点を得ることができるようになると思います。また、群論の入門にもなればいいなと思っています。
swapと順列
競技プログラミングの問題に、swapと順列は多く登場します。swapとは、2つの要素を入れ替える操作のことです。例えば、次のような問題があります。
第二回全国統一プログラミング王決定戦予選 C - Swaps (問題ページ)
$ N $ 要素からなる2つの整数列 $ A_1,\ldots,A_N $ および $ B_1,\ldots,B_N $ が与えられます。以下の操作を $ N-2 $ 回まで(0回でもよい)行うことで、1以上 $ N $ 以下のすべての整数 $ i $ に対して $ A_i\le B_i $ となるようにできるか判定してください。
- 1以上 $ N $ 以下の相異なる整数 $ x,y $ を選び、$ A_x $ の値と $ A_y $ の値を入れ替える。
また、(長さ $ N $ の)順列とは、$ N $ 個のものの並べ替えのことです。例えば、次のような問題があります。
高橋君は $ 1,2,\ldots,N $ の番号のついた $ N $ マスからなるマス目の上で、コマを使ってゲームを行おうとしています。マス $ i $ には整数 $ C_i $ が書かれています。また、$ 1,2,\ldots,N $ の順列 $ P_1,P_2,\ldots,P_N $ が与えられています。
これから高橋君は好きなマスを1つ選んでコマを1つ置き、1回以上 $ K $ 回以下の好きな回数だけ、次のような方法でコマを移動させます。
- 1回の移動では、現在コマがマス $ i \ (1\le i\le N) $ にあるなら、コマをマス $ P_i $ に移動させる。このとき、スコアに $ C_{P_i} $ が加算される。
高橋君のために、ゲーム終了時のスコアとしてあり得る値の最大値を求めてください。(ゲーム開始時のスコアは0です。)
この記事の目標は、swapや順列を群論、特に対称群の立場から捉えることです。
対称群
swapも順列も、$ 1,2,\ldots,N $ を並べ替える操作を表しています。数学的に表現すると、$ X $ を $ N $ 個の元からなる集合 $ \{ 1,2,\ldots,N \} $ とするとき、$ X $ から $ X $ への写像とみることができます。順列もswapも $ 1,2,\ldots,N $ の並べ替えであることから、この写像は一対一に対応していることがわかります。よって、順列とは $ X $ から $ X $ への全単射とみることができます。また、swapは順列の特別なものとみることができます。
$ X=\{1,2,\ldots,N\} $ に対し、$ X $ から $ X $ への全単射全体からなる集合を $ S_N $ とおきます。順列の個数を考えることで、$ S_N $ の元の個数が $ N! $ であることがわかります。$ S_N $ の元 $ f $ に対し、$ f $ を次のような形で表示してみましょう。
$$f=\begin{pmatrix}
1 & 2 & \cdots & N \\
f(1) & f(2) & \cdots & f(N)
\end{pmatrix}$$
これは上に書かれている数を下に書かれている数に移すということを表しています。例えば
$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}$$
は1を2に、2を4に、3を3に、4を1に移す写像を表しています。これは全単射なので $ S_4 $ の元です。
すべての数を動かさない写像、すなわち
$$\begin{pmatrix}
1 & 2 & \cdots & N \\
1 & 2 & \cdots & N
\end{pmatrix}$$
も $ S_N $ の元です。これを $ S_N $ の単位元と呼び、$ \text{id} $ と表すことにします。
$ S_N $ の元は $ X $ から $ X $ への写像なので、合成を考えることができます。例えば
$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}$$
を作用させてから、
$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$$
を作用させると、1は2に移ったあと3に移ります。2は4に移った後1に移り、3は3に移った後2に移り、4は1に移った後4に移ります。これを
$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}
$$
と表します。(一般的な写像の合成の記号と順序が逆ですが、私はこちらの表記の方が好きなので以後こちらを使います。)
2つの全単射を合成しても全単射なので、$ S_N $ の2つの元を合成したものも $ S_N $ の元です。さらに結合法則 $ f(gh)=(fg)h $ をみたしています。
また、$ f $ を $ S_N $ の元とするとき、$ f $ は全単射なので逆写像 $ f^{-1} $ をもち、$ f^{-1} $ も $ S_N $ の元となります。
まとめると、$ S_N $ は次のような性質を持ちます。
- $ f,g\in S_N $ ならば、$ fg\in S_N $
- $ f,g,h\in S_N $ ならば、$ f(gh)=(fg)h $
- $ \text{id}\in S_N $
- $ f\in S_N $ ならば、$ f^{-1}\in S_N $
$ S_N $ には群と呼ばれる代数的構造が入るということになります。このことから、$ S_N $ を $ N $ 次対称群と呼びます。
$ S_N $ の元を順列または置換と呼びます。$ f,g\in S_N $ に対し、合成 $ fg $ を $ f $ と $ g $ の積と呼ぶことにします。以後、$ f\in S_N, x\in X $ に対し $ f(x) $ の代わりに $ x ^ f $ と書くことにします(このように書くと $ x^{fg}=(x ^ f) ^ g $ をみたします)。
対称群の生成元
$ i $ と $ j $ を入れ替えるswap操作のことを互換といい、$ (i,j) $ と表します。互換も対称群の元です。置換を互換の積で表すことを考えます。例えば
$$
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 4 & 1 & 5 & 2 \end{pmatrix}=(1,4)(3,4)(2,6)
$$
のように、この置換は3つの互換の積で表すことができました。実は、$ S_N $ の元はすべて、いくつかの互換の積で表すことができます。まず1を互換で所定の位置に動かし、2を動かし、…と順番にやっていくことで互換の積で表せることがわかります。言い換えると、$ \frac{N(N-1)}{2} $ 個の互換 $ (i,j) $ は $ S_N $ を生成するということになります。
では次のような問題を考えてみましょう。
例題
$ K $ 個の互換 $ (a_i,b_i)\in S_N $ が与えられます。これらの互換が $ S_N $ を生成するかどうか、すなわち $ S_N $ の任意の元はこれらの互換の積として表せるかどうか判定してください。
$ 1,2,\ldots,N $ を頂点とするグラフを考え、$ a_i,b_i $ を辺で結びます。このグラフが連結でなければ、異なる連結成分に属する2数を入れ替えられないので、$ S_N $ を生成しません。
逆にグラフが連結ならば $ S_N $ を生成することを示します。適当に全域木をとり、その上に制限して考えます。すると以下の操作を繰り返すことで $ \pi\in S_N $ を互換の積で表すことができます。
- $ x^{\pi} $ がグラフの葉であるような $ x $ を1つ選ぶ。
- $ x $ が $ x^{\pi} $ に移るように互換をかける。
- グラフから頂点 $ x^{\pi} $ を削除する。
よって、グラフが連結かどうかを判定すればよいです。
このことから、$ S_N $ は隣接互換 $ (1,2),(2,3),\ldots,(N-1,N) $ で生成されることがわかります。これはあみだくじですべての順列を作れるということを表しています。
では次にこのような問題を考えてみましょう。
例題
$ N $ 人が一列に並んでいます。$ K $ 種類の操作があり、$ i $ 番目の操作では、前から $ a_i $ 番目の人と前から $ b_i $ 番目の人を入れ替えることができます。これらの操作を好きな順番で好きな回数行うとき、操作後の人の並び方としてあり得る状態の数は何通りありますか。
数学的には、$ K $ 個の互換 $ (a_i,b_i) $ で生成される $ S_N $ の部分群の位数を求めよという問題になります。これも上と同様にグラフを作ると、各連結成分上で自由に動かせることになります。連結成分の大きさを $ n_1,n_2,\ldots,n_m $ とすると、答えは $ n_1!\times n_2!\times\cdots\times n_m! $ です。UnionFindを用いて連結成分の大きさを求めることができます。
では実際の問題を解いてみましょう。
1から $ N $ までの整数を並び替えた順列 $ p_1,p_2,\ldots,p_N $ があります。また、1以上 $ N $ 以下の整数のペアが $ M $ 個与えられます。これらは $ (x_1,y_1),(x_2,y_2),\ldots,(x_M,y_M) $ で表されます。シカのAtCoDeerくんは順列 $ p $ に次の操作を好きなだけ行って、$ p_i=i $ となる $ i \ (1\le i\le N) $ の数を最大にしようと考えています。
- $ 1\le j\le M $ なる $ j $ を選び、$ p _ {x _ j} $ と $ p _ {y _ j} $ をスワップする。
操作後の $ p_i=i $ となる $ i $ の数として考えうる最大値を求めてください。
$ 1,2,\ldots,N $ を頂点とし、$ x_i,y_i $ を辺で結んでできるグラフを考えると、上で見た通り、連結成分上で好きなように動かすことができます。$ p_i $ と $ i $ が同じ連結成分上にあれば、$ p_i=i $ となるようにすることができます。
高橋君は、誕生日に長さ $ N $ の数列をもらいました。$ i \ (1\le i\le N) $ 番目の要素は整数 $ A_i $ です。どの2つの要素も、互いに異なります。高橋君はこの数列を単調増加になるように並べ替えたいです。高橋君は超能力者なので、以下の2つの操作が任意のタイミングで出来ます。
- 操作1: 数列の連続する2つの要素を選び、その2つの順番を反転する。
- 操作2: 数列の連続する3つの要素を選び、その3つの順番を反転する。
高橋君は操作2は好きですが、操作1は嫌いです。この2種類の操作を使って数列を単調増加になるように並び替えるときの、操作1の最小回数を求めてください。
操作1は互換 $ (i,i+1) $ 、操作2は互換 $ (i,i+2) $ です。操作2だけを行うとき、同様にグラフを考えると、連結成分は($ N\ge 2 $ のとき)2つで、それぞれ偶数・奇数に対応します。ゆえに添字が偶数であるもの同士は自由に並べ替えることができ、添字が奇数であるもの同士も自由に並べ替えることができます。添字の偶数・奇数を変える必要があるものは操作1を使います。よって、添字の偶数・奇数が入れ替わる個数を数えればよいです。
$ S_N $ の元が互換の積で表せることをみましたが、互換の個数は一意ではありません。例えば
$$
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 4 & 1 & 5 & 2 \end{pmatrix}=(1,4)(3,4)(2,6)=(1,2)(1,6)(2,3)(2,4)(1,2)
$$
のように、3個の互換の積で表すことも、5個の互換の積で表すこともできます。このように個数は一意ではありませんが、実は個数の偶奇は一意に定まります。上の例では、常に互換の個数は奇数になります。すなわち偶数個の互換の積で表すことはできないということです。
これを証明してみます。突然ですが、$ f(x_1,\ldots,x_N)=\displaystyle\prod _ {i < j}(x_i-x_j) $ という $ N $ 変数多項式を考えます。$ \pi\in S_N $ に対し、$ f^{\pi}(x_1,\ldots,x_N)=f(x _ {1^{\pi}},\ldots,x _ {N^{\pi}}) $ とおきます。計算すると、$ \pi $ が互換のときは $ f^{\pi}(x_1,\ldots,x_N)=-f(x_1,\ldots,x_N) $ が成り立つことがわかります。ここで、$ \pi $ が $ k $ 個の互換の積として表せるとすると、$ f^{\pi}(x_1,\ldots,x_N)=(-1) ^ k f(x_1,\ldots,x_N) $ となります。一方 $ \pi $ が $ l $ 個の互換の積としても表せたとすると、$ f^{\pi}(x_1,\ldots,x_N)=(-1) ^ l f(x_1,\ldots,x_N) $ となります。これより $ (-1) ^ k=(-1) ^ l $ となり、$ k $ と $ l $ の偶奇が等しいことがわかります。従って、置換を互換の積として表すときの互換の個数の偶奇は常に一定であることが示されました。
よって次のような定義ができます。
- 偶数個の互換の積として表せる置換を偶置換といい、
- 奇数個の互換の積として表せる置換を奇置換という。
偶置換と偶置換の積は偶置換になります。よって $ S_N $ の元のうち偶置換であるもの全体を考えると、これは $ S_N $ の部分群となることがわかります。偶置換全体からなる $ S_N $ の部分群を $ A_N $ と表し、$ N $ 次交代群と呼びます。$ A_N $ の位数(偶置換の個数)は $ \frac12N! $ です。
例題
$ i=1,2,\ldots,N $ に対し、$ i $ を $ P_i $ に移す置換は偶置換か奇置換か決定してください。
ここで転倒数という概念を導入します。置換 $ P $ の転倒数とは、$ i\lt j $ かつ $P_i \gt P_j $ となるような組 $ (i,j) $ の個数です。転倒数はバブルソートにおけるswapの回数と等しくなります。よって、$ P $ は転倒数個の互換の積で表されます。ゆえに転倒数を求めれば、その偶奇をみることで偶置換かどうかがわかります。転倒数はBITを用いることで計算できます。詳しくは以下の記事などを参照してください。
qiita.com
偶置換に関する問題を解いてみましょう。
英小文字からなる2つの長さ $ n $ の文字列 $ s,t $ が与えられます。以下の操作を行うことができます。
- 1以上 $ n $ 以下の整数 $ len $ を1つ選ぶ。
- $ s $ の長さ $ len $ の連続部分文字列を選び、反転させる。
- 同時に、$ t $ の長さ $ len $ の連続部分文字列を選び、反転させる。
何回か操作を行うことで、$ s,t $ を等しくできるでしょうか。
$ t $ の部分文字列を反転させる代わりに $ s $ の部分文字列を反転させることにしてもよいです。よって $ s $ には長さ $ len $ の反転を2回行うことになり、これは偶置換です。逆にすべての偶置換をこれらの操作を組み合わせることで実現可能です。(略証: $ (i,i+1,i+2)=(i+1,i+2)(i,i+1) $ は長さ2の反転2回で実現可能であり、交代群 $ A_N $ はこれらの元で生成されるため。)これを踏まえて問題を解きましょう。
まず出現回数が異なる文字がある場合は不可能です。以下出現回数が等しいとします。等しい文字があるときは可能です。なぜなら、$ s $ を $ t $ にするための操作が奇置換のときは、等しい文字を入れ替えるダミーの互換を加えることで偶置換にできるからです。等しい文字がないとします。このとき、$ s,t $ を等しくできるための必要十分条件は、$ s,t $ の転倒数の偶奇が一致していることです。なお、この場合 $s, t$ の長さは26以下なので、転倒数はBITを用いなくても計算できます。
巡回置換
$ 1,2,\ldots,N $ の順列 $ P $ に対し、$ i, P _ i, P _ {P _ i}, P _ {P _ {P _ i}}, \ldots $ という列を考えるとどのようになるでしょうか。
$ i $ から $ P_i $ へ有向辺を張ります。すると上の問題は、ある点から出発して辺上を動くとどのように動くかという問題になります。
頂点数は有限個なので、移動を続けると途中で既に通った頂点に出会います。このとき経路は6の字型にはなりません。
なぜなら $ P $ は順列(特に単射)だからです。ゆえに、経路はサイクルになります。通らなかった頂点についても同様に考えることで、サイクルになることがわかります。2つのサイクルは交わりません。
よって、このグラフはサイクルがいくつか集まったものになります。
このことを群論的に表現してみましょう。
$ (a_1,a_2,\ldots,a_m) $ を、$ a_1 $ を $ a_2 $ に移し、$ a_2 $ を $ a_3 $ に移し、…、$ a_m $ を $ a_1 $ に移す置換とします。このような置換を巡回置換といいます。互換 $ (i,j) $ は巡回置換の特別なものです。
上で述べたことは、任意の置換が共通文字を含まないいくつかの巡回置換の積として表せるということです。例えば
$$
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
4 & 2 & 5 & 7 & 3 & 8 & 1 & 6
\end{pmatrix} = (1,4,7)(3,5)(6,8)(2)
$$
のようになります。
$ n $ 人の子供たちがおり、それぞれ本を持っています。毎日の終わりに、$ i $ 番目の子供は持っている本を $ p_i $ 番目の子供に渡します。ここで $ p $ は $ 1,2,\ldots,n $ の順列です。子供ごとに、自分の本が自分のところに戻ってくるまでに何日かかるか求めてください。
$ i $ 番目の子供が持っていた本は $ p_i $ 番目の子供に移り、さらにそれは $ p_{p_i} $ 番目の子供に移ります。よって冒頭で述べたシチュエーションと一致しています。
$ p $ を巡回置換の積として表すとき、$ i $ 番目の子供に対する答えは、$ i $ を含む巡回置換の長さです。
高橋君は $ 1,2,\ldots,N $ の番号のついた $ N $ マスからなるマス目の上で、コマを使ってゲームを行おうとしています。マス $ i $ には整数 $ C_i $ が書かれています。また、$ 1,2,\ldots,N $ の順列 $ P_1,P_2,\ldots,P_N $ が与えられています。
これから高橋君は好きなマスを1つ選んでコマを1つ置き、1回以上 $ K $ 回以下の好きな回数だけ、次のような方法でコマを移動させます。
- 1回の移動では、現在コマがマス $ i \ (1\le i\le N) $ にあるなら、コマをマス $ P_i $ に移動させる。このとき、スコアに $ C_{P_i} $ が加算される。
高橋君のために、ゲーム終了時のスコアとしてあり得る値の最大値を求めてください。(ゲーム開始時のスコアは0です。)
これも冒頭のシチュエーションと一致します。よって巡回置換の積に分解して、各巡回置換上で考えればよいことになります。
最初の移動で到達するマスを固定します。このマスを含むサイクルの長さが $ L $ だとします。
- 一周の総和が正のときは回れるだけ回って、残った $ ((K - 1) \bmod{L})+1 $ 個について和の最大値を求めます。
- 一周の総和が0以下で $ K\ge L $ のときは、1個以上 $ L $ 個以下の和の最大値を求めます。
- 一周の総和が0以下で $ K\le L $ のときは、1個以上 $ K $ 個以下の和の最大値を求めます。
これで計算量 $ O(N ^ 2) $ で解くことができました。なお、さらに改善するとより良い計算量で解けるようです。
$ N $ 本の縦線と $ M $ 本の横線からなるあみだくじがあり、上から $ i $ 番目の横線は左から $ A_i $ 番目の縦線と $ A_i+1 $ 番目の縦線を結んでいます。このあみだくじを縦に $ D $ 個つなげます。各整数 $ k=1,2,\ldots,N $ に対し、左から $ k $ 番目の縦線から出発したとき、最終的に左から何番目の縦線に到着するか求めてください。
与えられるあみだくじは対称群 $ S_N $ の元とみることができます。よって共通文字を含まない巡回置換の積 $ (c _ {11},\ldots,c _ {1i_1})(c _ {21},\ldots,c _ {2i_2})\cdots (c _ {k1},\ldots,c _ {ki_k}) $ として表すことができます。あみだくじを $ D $ 個連結したものは、これを $ D $ 乗した $ (c _ {11},\ldots,c _ {1i_1}) ^ D(c _ {21},\ldots,c _ {2i_2}) ^ D\cdots (c _ {k1},\ldots,c _ {ki_k}) ^ D $ となります(一般に置換の積は非可換ですが、これらの巡回置換は共通文字を含まないので積の順番を入れ替えることができます)。
第二回全国統一プログラミング王決定戦予選 C - Swaps (問題ページ)
$ N $ 要素からなる2つの整数列 $ A_1,\ldots,A_N $ および $ B_1,\ldots,B_N $ が与えられます。以下の操作を $ N-2 $ 回まで(0回でもよい)行うことで、1以上 $ N $ 以下のすべての整数 $ i $ に対して $ A_i\le B_i $ となるようにできるか判定してください。
- 1以上 $ N $ 以下の相異なる整数 $ x,y $ を選び、$ A_x $ の値と $ A_y $ の値を入れ替える。
swapを $ N-2 $ 回まで、という条件が気になります。これについて考えてみましょう。
長さ $ m $ の巡回置換 $ (i_1,i_2,\ldots,i_m) $ は $ m - 1 $ 個の互換の積 $ (i_1,i_2)(i_1,i_3)\cdots (i_1,i_m) $ として表すことができます。よって $ S_N $ の元が共通文字を含まない巡回置換 $ k $ 個の積として表せ、巡回置換の長さがそれぞれ $ l_1,l_2,\ldots,l_k $ であったとすると、これは $ (l_1-1)+(l_2-1)+\ldots+(l_k - 1)=N-k $ 個の互換の積として表せます。よって、$ N-2 $ 回までのswapで長さ $ N $ の巡回置換以外をすべて表現できることがわかります。
まず適切に並べ替えておくことで、$ B_1\le B_2\le\cdots\le B_N $ であるとしてよいです。$ A _ {p_1}\le A _ {p_2}\le\cdots\le A _ {p_N} $ となるような置換 $ p $ を1つとります。このとき $ A_{p_i}>B_i $ となるような $ i $ が存在すると、不可能です。以下 $ A _ {p_i}\le B_i $ とします。$ p $ が長さ $ N $ の巡回置換でなければ、$ p $ を $ N-2 $ 個以下の互換の積で表せるので、条件を満たします。$ p $ が長さ $ N $ の巡回置換のとき、$ p $ は $ N-1 $ 個の互換の積で表されます。よって、$ N-2 $ 回までのスワップにより $ A $ は「ソートされた状態の1つ手前」、すなわちソートされた状態にスワップを1回施したものにできます。少し考えるとこのスワップは隣接互換でよいことがわかります。ゆえに $ N-1 $ 個の隣接互換をすべて考え、条件を満たすようにできるか判定します。$ A _ {p _ {i+1}}\le B_i $ を判定すればよいです。
演習問題
参考文献
追記
姉妹記事である「競プロerのための群論 (整数論と群論)」を公開しました。
hackmd.io
