読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CodeChef July Challenge 2016: Chef and Polyhedron

CodeChef 平面埋め込み 対称群 バーンサイドの補題

https://www.codechef.com/JULY16/problems/CHEFPOL

問題

すべての面が正多面体であるような凸多面体が与えられる。この凸多面体を C 色で塗る方法は何通りあるか。ただし回転や鏡像反転によって同じになるものは同一視する。

  • 4≦N≦25
  • 1≦C≦109

やったこと

  • 凸多面体の面の繋がりのリストが時計回りになっていれば面の置換を列挙できる。
  • 置換を列挙できればサイクル数 i の置換の個数が分かるのでバーンサイド補題が使える。
  • サンプルを見る限りだと、凸多面体の面の繋がりのリストの並びに規則性はないように見える。
  • となると何かしらの方法でソートする必要がありそう。
  • ソート方法がぱっと思いつかないので、正多面体サイコロをクルクル回して正多面体のグラフを手作業で構築。
  • これで部分点 30 点を獲得。
  • 本当にソート必要?→分からない。
  • 凸多面体は平面に埋め込めるので、平面グラフのアルゴリズムを使って辺の並びをソートできそう。
  • 愚直な方法を考えていたが、どうも怪しい方法ばかり思いついてしまい正当性も示せなくて困っていたので調べる。
  • この手の問題は planar embedding というらしい。ちょっと調べると色々見つかる。
  • 一番最後のアルゴリズムは自分が考えていたアルゴリズムに近かったためか割とすぐに理解できた。
  • O(n) である必要はないので愚直に実装。
  • 大体あってるんだけどたまにバグる。
  • たまにバグる程度なので乱数でごまかして AC した(その後バグは修正してきちんと AC させた)。