競プロerのための群論 (swapと順列と対称群) - little star's memory

お知らせ 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 $ 以下のすべ

[jeeema08]

か…神か！？

[razokulover]

今群論やってるからどう実践に活きるかがわかってモチベが湧く

[yarumato]

“swapも順列も、1,2,…,Nを並べ替える操作を表しています。順列とは X から X への全単射とみることができます。偶置換全体からなる SN の部分群を AN と表し、N 次交代群と呼びます。”

[Insite]

、