kmjp's blog

競技プログラミング参加記です

AtCoder ARC #062 : E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

Eはそこそこの時間で解けたんだけどね。
http://arc062.contest.atcoder.jp/tasks/arc062_c

問題


N個のタイルがあり、i番目のタイルの四つ角は色C[i][j]で塗られている。
このタイルを6個組み合わせて立方体を作りたい。
その時立方体の角に来る色が3タイルでそろうようにしたい。

そのようなタイルの選び方及び組み合わせ方は何通りか。

解法

底面と上面を総当たりし、さらに底面に対する上面の向きを総当たりしよう。
そうすると立方体の8頂点の色がすべて定まるので、残り4面にどの4色が角に来るタイルが存在しうるか数え上げればよい。
これは4つ角の色からハッシュ値を計算できるようにしておけば高速に処理できる。

int N;
vector<ll> C[404];
ll VV[404];
int R[404];
map<ll,int> B[5];

ll getkey(vector<ll> v) {
	ll r=1LL<<60;
	int i;
	FOR(i,4) {
		rotate(v.begin(),v.begin()+1,v.end());
		r=min(r,v[0]*1000000000+v[1]*1000000+v[2]*1000+v[3]);
	}
	return r;
}

ll dfs(int cur,int n1,int n2,int n4) {
	if(cur==0) return 1;
	ll ret=0;
	if(n1) ret += n1*dfs(cur-1,n1-1,n2,n4);
	if(n2) ret += 2*n2*dfs(cur-1,n1,n2-1,n4);
	if(n4) ret += 4*n4*dfs(cur-1,n1,n2,n4-1);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N;
	FOR(i,N) {
		vector<ll> V(4,0);
		FOR(j,4) cin>>V[j];
		C[i]=V;
		VV[i]=getkey(C[i]);
		R[i]=1;
		if(C[i][0]==C[i][2]&&C[i][1]==C[i][3]) {
			R[i]=2;
			if(C[i][0]==C[i][1]) R[i]=4;
		}
		B[R[i]][VV[i]]++;
	}
	ll ret=0;
	FOR(x,N) {
		B[R[x]][VV[x]]--;
		for(y=x+1;y<N;y++) {
			B[R[y]][VV[y]]--;
			FOR(z,4) {
				
				map<ll,int> mp;
				mp[getkey({C[x][1],C[x][0],C[y][1],C[y][0]})]++;
				mp[getkey({C[x][2],C[x][1],C[y][0],C[y][3]})]++;
				mp[getkey({C[x][3],C[x][2],C[y][3],C[y][2]})]++;
				mp[getkey({C[x][0],C[x][3],C[y][2],C[y][1]})]++;
				
				ll tmp=1;
				FORR(r,mp) {
					tmp *= dfs(r.second,B[1][r.first],B[2][r.first],B[4][r.first]);
					if(tmp==0) break;
				}
				ret += tmp;
				
				rotate(C[y].begin(),C[y].begin()+1,C[y].end());
				
			}
			B[R[y]][VV[y]]++;
		}
	}
	cout<<ret<<endl;
}

まとめ

これはすんなり思いつけてよかった。

広告を非表示にする