アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Regular Contest 062 - E - AtCoDeerくんと立方体づくり

arc062.contest.atcoder.jp

 

正方形がN個(N≦400)与えられ、それぞれの正方形の四隅には異なる色C[i,j] (C[i, j]≦999)がついている。この正方形を6個使って立方体を作るとき、隅の色を合わせる組み合わせは何通りあるか。ただし、回転したものは同一のものとみなす。

 

方針はすぐ立つ。まず1個の面を方向を含めて1個固定、対面の面を回転を含めて4通り考える。こうすると側面に置きべき色が決定されるので、その組み合わせをカウントすればよい。これだけ書くと簡単であるが、カウントするためのデータ構造が複雑。

 

まず正方形に対し、回転を同一視したハッシュ関数を用意する。例えば数値をくっつけて単純ハッシュにしたもののうち、回転させた場合の最小値など。これで次のMapを作成。

map1[ハッシュ] = ハッシュ値の正方形の数

map2[ハッシュ]=このハッシュ値を持つ正方形が回転したときにまた同じ形になる組み合わせ。1,2,4のいずれかの値

 

次に前後が決められて、4隅の色が決まった状態でその4隅のハッシュを計算し、ret *= map1[hash] * map2[hash] などという計算をする。その後 map1[hash]をデクリメントして次の面の組み合わせを同様に計算する。

 

もちろん次の前後の面の組み合わせに行くときには引いたりしたmap1を元に戻す必要がある。あと、確認の最初は既に使用済みの前後の面のぶんをmap1からデクリメントしておくのを忘れないようにしたい。

 

計算量はO(N^2 logN)なのであるが、その中に16回のループがあり、しかもmapの初期化等が入るので定数倍が重い。