kmjp's blog

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

CSAcademy Beta Round #8 : F. Cube Coloring

サンプルのテストケースが弱すぎて怖い。
https://csacademy.com/contest/beta-round-8/#task/cube-coloring

問題

6面体の各面を塗りたい。
使える色はN通りで、i番目の色はC[i]個の面を塗ることができる。
辺を共有する面は同じ色を使うことができない。

全体で色の塗り方は何通りか。
ただし回転して同じ塗り方になる複数の塗り方は1通りと見なす。

解法

1つの色は高々対面の2か所までしか塗れない。
よってC[i]は1か2以上かしか違いがない。
C[i]=1である色の数をP、2以上である色の数をQとしよう。

以下の和を求める。

  • 全面異なる色
    • 6色を選ぶので {}_N C_6 *5*3*2 通り。5*3*2は6色の並べ方。1色目を配置し、その対面を残り5色から選び、残り4色をどう配置するか考えるとこうなる。
  • 2面だけ同じ色
    • 2面ずつ使う1色、残り4色を決めるので {}_Q C_1 *{}_{N-1} C_3 *3 通り。最後の×3は、4色を円周上に並べる並べ方。ただし裏返したものも同一と判断される点に注意。
  • 4面だけ2面ずつ同じ色
    • 2面ずつ使う2色、残り2色を決めるので {}_Q C_2 *{}_{N-2} C_2 通り。残り2色の配置は回転すると同じになるので2重カウントしない。
  • 6面すべて2面ずつ同じ色
    • 使う3色を決めるとどう塗っても回転すれば同じ塗り方になるので {}_Q C_3通り。
int N;
int N1,N2;
int F[1010];
ll ret;

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		if(x==1) N1++;
		else N2++;
	}
	
	// all dif
	ret = comb(N,6)*5*3*2;
	// one same
	if(N2) ret += N2*comb(N-1,4)*3;
	// two same
	if(N2>=2) ret += comb(N2,2)*comb(N-2,2);
	// three same
	if(N2>=3) ret += comb(N2,3);
	
	cout<<ret<<endl;
	
}

まとめ

よく一発で通ったな。

広告を非表示にする