2003/Contest/マニラ大会

Problem D : Generating the Subgroups of a Finite Group †

問題概要 †

群論のオハナシ。

要素数最大 24 の群の群表が与えられて、その群の部分群を全て求めよ、という問題です。

四問解いたチームのうち、唯一 Donghua University のチーム GreyGhost (Second Place) のみが解いていました。

大会中挑戦するも、 Exhaustive Search では Time-Limit Exceeded となる。 (三廻部)

解法 †

本番以来敬遠していた Problem D を解いてやろう、と思ってコンピュータの前に座る。問題を開く。本番で解けなかった悔しさが思い出される。三十秒後。ふとピンと来た。与えられた群表の各要素から、その要素を含む極小の部分群表を生成するようなことができそうな...。

1. 集合 R := φ を用意し、群表の各要素 G[ i , j ] に対して以下の処理を行う。
   1. 集合 S := { i , j } と T := φ を用意する。
   2. 以下を S = T となるまで繰り返す。
      1. D := S - T
      2. T := S
      3. ∀x ∈ T, ∀y ∈ D に対して S := S ∪ { G[ x , y ] }
   3. R := R ∪ { S }
2. R を返す。

要するに、「群であるためには必ず含んでいなければならない要素」を追加していくことで、要素 G[ i , j ] から部分群の群表を構成していく。

何故これだけのことを本番で思いつかなかったのか。本当に強いチームというのは、やはりこういう問題をすらっと解けるチームなのでしょう。実質的に自分達の負けだったな...、と強く思い知らされました。

ちなみに、マニラ大会側から送られた正解データとは食い違いがありました。しかしこの正解データは、例えば

1 + 3 = 15

となっている群表に対して、

{1, 3, 5, 7, 8, 10, 13, 14, 16, 19, 20, 23}

を部分群として返しているので、おそらく間違いでしょう。 (食い違いはこの部分のみでした) (三廻部)

探索で行くときに枝を刈るのに使えそうなポイント

ある群（要素数n）に部分群が存在したとすると、

部分群の要素数はnの約数。

単位元（零元）は部分群に必ず含まれる。（この元は部分群においても単位元である）

ちなみに入力から単位元はすぐにわかる（演算の表で0,1,2,3...となっている行）。(D.java)（谷口）

議論・その他 †

ファイルを添付する †

taniguchi_D.java

mikurube_D.cpp

mikurube_groups.out