SRM 296 DIV1 Hard ColoredBricks

SRM

問題 Editorial

問題

立方体であって、6面がそれぞれ[0..6]の色で塗り分けられているレンガがいくつかある。
2つのレンガが同じであるとは、ある回転をしたときに全ての面が同じ色で塗られていることである。
bricksが与えられる。それらの面を塗り替えて全てを同じにするとき、塗り替える回数を最小化せよ

  • 1 <= |bricks| <= 50

解答

基本的には全探索。
全てのレンガ(bricksに含まれるとは限らない)を考えて、(全ての回転の中で最小の違う色の数)の総和を最小化すればよい。
単純には(7^6*50*24*6)(立方体の回転の仕方は24通りある)となって少し間に合わない。
しかし全てのレンガを試す必要はない。(回転して)同じレンガはそのうちの1つのみを試せばよい。この"同じ"は推移的なので。
さて、そのような"回転して同じ"の代表元を取るにはどうするか？とりあえず最初に全部のレンガに対して、「全ての回転のうち辞書順最小のもの」をsetでやればいい。
こうしてみると実際には5390通りしか無いことが分かる。
その代表元を取る所を普通にやっても(自分の実装では)ギリギリ通ったが、5390通りなら事前に計算して埋め込んでおくこともできる

コメント

代表元を取るのに、それと同値なものが全て列挙できるならばそのうち何らかの関係で最小なものだけを取るという感じ。もっと高速にやる方法はあるだろうか？
回転しながら、既に見たやつをメモっといてそれを飛ばすようにすれば早くなるかな。というかそれならO(元の数)なのでは？そうしたらいいと思う

コード

事前計算を毎回愚直に遅くやっていて、最大1.9sとかギリギリなコード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;  

enum FACE { TOP, BOTTOM, FRONT, BACK, LEFT, RIGHT };
struct Dice {
	Dice() {
		id[TOP] = 0; id[FRONT] = 1; id[LEFT] = 2;
		id[RIGHT] = 3; id[BACK] = 4; id[BOTTOM] = 5;
	}
	void roll_x() { roll(TOP, BACK, BOTTOM, FRONT); }
	void roll_y() { roll(TOP, LEFT, BOTTOM, RIGHT); }
	void roll_z() { roll(FRONT, RIGHT, BACK, LEFT); }
	vector<Dice> all_rolls() {
		vector<Dice> ret;
		for (int k = 0; k < 6; (k&1?roll_y():roll_x()),++k)
			for (int i = 0; i < 4; roll_z(), ++i)
				ret.push_back(*this);
		return ret;
	}
	void roll(FACE a, FACE b, FACE c, FACE d) {
		int tmp = id[a];
		id[a] = id[b]; id[b] = id[c];
		id[c] = id[d]; id[d] = tmp;
	}
	int id[6];
};

set<vi> s;
struct ColoredBricks {
	int minRepaints(vector <string> bricks) {
		vector<Dice> rolls = Dice().all_rolls();
		{
			vi v(6), z(6); vector<vi> w(24, vi(6));
			rep(i, 117649) {
				int x = i;
				rep(j, 6) v[j] = x % 7, x /= 7;
				rep(j, 24) {
					rep(k, 6) w[j][rolls[j].id[k]] = v[k];
				}
				sort(all(w));
				s.insert(w[0]);
			}
		}
		static const FACE aaa[6] = {FRONT,RIGHT,BACK,LEFT,TOP,BOTTOM};
		int r = INF;
		each(i, s) {
			int x = 0;
			vi z(6);
			each(j, bricks) {
				int w = INF;
				rep(k, 6) z[aaa[k]] = (*j)[k]-'0';
				each(l, rolls) {
					int q = 0;
					rep(k, 6) q += (*i)[l->id[k]] != z[k];
					w = min(w, q);
				}
				x += w;
			}
			r = min(r, x);
		}
		return r;
	}
};