CSAcademy Beta Round #8 : F. Cube Coloring

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

問題

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

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

解法

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

以下の和を求める。

• 全面異なる色
  • ６色を選ぶので通り。5*3*2は６色の並べ方。1色目を配置し、その対面を残り5色から選び、残り4色をどう配置するか考えるとこうなる。
• ２面だけ同じ色
  • ２面ずつ使う１色、残り４色を決めるので通り。最後の×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;
	
}

まとめ

よく一発で通ったな。